设有一组关键字(9,01,23,14,55,20,84,27),采用哈希函数:H(key)=key+%7+,表长为10,用开放地址法的二次探测法处理冲突。要求:对该关键字序列构造哈希表,并计算查找成功
时间: 2024-06-13 17:08:34 浏览: 142
用二次探测再散列法解决冲突建立哈希表并查找
4星 · 用户满意度95%
以下是对该关键字序列构造哈希表的过程:
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。
阅读全文