设有一组关键字(9,01,23,14,55, 20,84,27),采用哈希函数:H(key)=k ey%7,表长为10，用开放地址法的二次探测法处理冲突。要求:对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

1. 构造哈希表，采用二次探测法处理冲突。

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 55|27 |84 | 01|23 |14 | | | 9 |20 |

2. 计算查找成功的平均查找长度。

对于每个关键字，它要么在哈希表中，要么不在哈希表中。如果它在哈希表中，那么它肯定是在哈希表的某个位置上；如果它不在哈希表中，那么最终会找到一个空位置。因此，查找成功的平均查找长度ASL = (1/8)*(1+1+1+1+1+1+2+1) = 1.125。其中，8表示关键字的个数，1/8表示每个关键字被查找到的概率相等。

相关问题

设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key+%7+，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功

以下是对该关键字序列构造哈希表的过程：
1. 初始化哈希表，长度为10，全部赋值为None。
2. 对于每个关键字，计算其哈希值：H(key) = key % 7。
3. 如果对应哈希表位置为空，则直接插入该关键字；否则，进行二次探测，即在位置（H(key) + i^2）% 10处查找，直到找到一个空位置为止。
4. 将所有关键字插入哈希表中。

根据上述过程，可以得到该关键字序列构造的哈希表如下：

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 9 | 55 | 84 | None | 23 | 01 | 14 | 27 | 20 | None |

其中，关键字9、55、84、23、01、14、27、20分别插入了位置0、1、2、4、5、6、7、8。

要计算查找成功的平均查找长度（ASL），需要先计算每个关键字在哈希表中的查找长度，再求平均值。对于该关键字序列，查找成功的关键字有9、01、23、14、55、20、84，它们在哈希表中的查找长度分别为1、1、1、1、1、1、1，因此它们的ASL为(1+1+1+1+1+1+1)/7=1。

2. 设有一组关键字(71,23,73,14,55,89,33,43,48),采用哈希函数:h(key)=key

根据给定的哈希函数h(key)=key，我们可以直接将关键字映射为它自己的值作为哈希地址。即71映射为71，23映射为23，以此类推。

在使用哈希函数时，我们通常需要考虑解决冲突的方法。冲突是指不同的关键字经过哈希函数计算后映射到了相同的地址上。对于本题中的哈希函数h(key)=key而言，由于每个关键字都直接映射到自身，因此不会产生冲突的情况。

在实际应用中，使用h(key)=key这样简单的哈希函数并不常见。通常会采用一些更复杂的哈希函数来确保更好的分布性和更小的碰撞概率。

对于给定的关键字(71,23,73,14,55,89,33,43,48)，将它们分别经过哈希函数计算后得到对应的哈希地址(71,23,73,14,55,89,33,43,48)。这样每个关键字就对应了它自己的哈希地址。当我们需要查找某个关键字时，可以直接通过哈希函数计算出它的哈希地址，从而快速定位到对应的位置。