设有一组关键字(9,01,23,14,55,20,84,27),采用哈希函数:H(key)=key %7 ,表长为10,用开放地址法的二次探测法处理冲突。要求:对该关键字序列构造哈希表,并计算查找成功的平均查找长度。
时间: 2023-11-26 07:02:41 浏览: 169
Hash表存储数据,用再散列来解决地址冲突问题,计算平均查找长度,还可以通过Key值查找对应的value
好的,我来回答你的问题。
首先,我们按照哈希函数 H(key)=key %7 将关键字序列映射到哈希表中:
| 索引 | 哈希值 | 关键字 |
| ---- | ------ | ------ |
| 0 | 9 | |
| 1 | 1 | 01 |
| 2 | 2 | 23 |
| 3 | 3 | 14 |
| 4 | 6 | 20 |
| 5 | 5 | 55 |
| 6 | 0 | |
| 7 | 4 | 27 |
| 8 | 0 | |
| 9 | 4 | 84 |
可以看到,有些索引位置出现了冲突,我们需要使用开放地址法的二次探测法来解决。
对于冲突的关键字 9,我们从索引位置 0 开始探测,发现位置 0 已经被占用,于是我们按照二次探测法的公式,依次探测位置 1、4、2、9,最终在位置 9 找到了一个空闲位置,将关键字 9 存储在该位置。
对于冲突的关键字 20,我们从索引位置 6 开始探测,发现位置 6 已经被占用,于是我们按照二次探测法的公式,依次探测位置 9、4、0、8,最终在位置 8 找到了一个空闲位置,将关键字 20 存储在该位置。
最终哈希表的结果如下:
| 索引 | 哈希值 | 关键字 |
| ---- | ------ | ------ |
| 0 | 9 | 9 |
| 1 | 1 | 01 |
| 2 | 2 | 23 |
| 3 | 3 | 14 |
| 4 | 6 | 20 |
| 5 | 5 | 55 |
| 6 | 0 | |
| 7 | 4 | 27 |
| 8 | 0 | 84 |
| 9 | 4 | |
接下来计算查找成功的平均查找长度。我们假设要查找的关键字为 x,它在哈希表中的位置为 i。
如果 x 存在于表中,则查找成功,平均查找长度为:
ASL = (1 * P1 + 2 * P2 + 3 * P3 + ... + k * Pk) / n
其中,P1、P2、P3 等是查找 x 时经过 1、2、3 次探测的概率,k 是查找 x 时最终经过的探测次数,n 是表中关键字的总数。
根据题目中给出的哈希函数和关键字序列构造哈希表后的结果,我们可以得到以下概率:
P1 = 4/10 = 0.4
P2 = 3/10 = 0.3
P3 = 2/10 = 0.2
P4 = 1/10 = 0.1
如果要查找关键字 23,它的哈希值为 2,经过一次探测就找到了,平均查找长度为 1。
如果要查找关键字 84,它的哈希值为 0,但是位置 0 和位置 8 都存储了关键字,因此需要进行二次探测,最终经过 4 次探测找到了关键字,平均查找长度为:
ASL = (1 * 0.4 + 2 * 0.3 + 3 * 0.2 + 4 * 0.1) / 8 = 1.9 / 8 = 0.2375
因此,查找成功的平均查找长度为 0.2375。
阅读全文