分别采用开放地址法的线性探测发及二次探测再散列方法解决冲突,试在0~12的散列地址空间中对该关键字序列构造哈希表
时间: 2024-04-06 20:34:09 浏览: 122
Hash表存储数据,用再散列来解决地址冲突问题,计算平均查找长度,还可以通过Key值查找对应的value
好的,我可以帮你解决这个问题。首先,我们需要根据哈希函数H(key)=key%13,计算出每个关键字的散列地址。计算结果如下:
| 关键字 | 散列地址 |
|--------|----------|
| 19 | 6 |
| 1 | 1 |
| 23 | 10 |
| 14 | 1 |
| 55 | 3 |
| 20 | 7 |
| 84 | 5 |
| 27 | 1 |
| 68 | 4 |
接下来,我们按照开放地址法的线性探测法和二次探测再散列法的方式,依次将关键字插入哈希表中。如果发生冲突,则按照规定的探测方式,寻找下一个可用的散列地址。
1. 开放地址法的线性探测法
我们先使用开放地址法的线性探测法。在该方法中,如果发生冲突,我们会将关键字插入到下一个可用的散列地址上。
| 散列地址 | 关键字 |
|----------|--------|
| 1 | 1 |
| 2 | |
| 3 | 55 |
| 4 | 68 |
| 5 | 84 |
| 6 | 19 |
| 7 | 20 |
| 8 | |
| 9 | |
| 10 | 23 |
| 11 | |
| 12 | |
2. 二次探测再散列法
现在,我们使用二次探测再散列法。在该方法中,如果发生冲突,我们会使用二次探测的方式,计算出下一个可用的散列地址。
| 散列地址 | 关键字 |
|----------|--------|
| 1 | 1 |
| 2 | |
| 3 | 55 |
| 4 | 68 |
| 5 | 84 |
| 6 | 19 |
| 7 | 20 |
| 8 | |
| 9 | |
| 10 | 23 |
| 11 | 14 |
| 12 | 27 |
经过以上两种探测方法的处理,我们就得到了两个不同的哈希表。
阅读全文