选取哈希函数H(k)=(3k)%11,采用开放定址法处理冲突,di=i((7k)%10+1),i=1,2,3,4,...在0-10的散列地址空间中,依次存放如下关键字22,41,53,46,30,13,01,67.请画出最后的哈希表。
时间: 2024-03-18 20:45:26 浏览: 110
首先,我们需要对给定的关键字进行哈希,具体方法是将关键字 k 带入哈希函数 H(k),得到散列地址:
- H(22) = (3 * 22) % 11 = 8
- H(41) = (3 * 41) % 11 = 8
- H(53) = (3 * 53) % 11 = 4
- H(46) = (3 * 46) % 11 = 8
- H(30) = (3 * 30) % 11 = 8
- H(13) = (3 * 13) % 11 = 6
- H(01) = (3 * 1) % 11 = 3
- H(67) = (3 * 67) % 11 = 8
我们可以看到,关键字 41、46、30 和 67 都被哈希到了散列地址 8,发生了冲突。因此,我们需要采用开放定址法来处理冲突,具体方法是根据 di 的值依次查找下一个空闲的散列地址,直到找到一个空闲的地址为止。
根据给定的公式 di = i * ((7k % 10) + 1),可以计算出每个关键字的 di 值:
- d22 = 1
- d41 = 2
- d53 = 3
- d46 = 4
- d30 = 5
- d13 = 6
- d01 = 7
- d67 = 8
接下来,我们可以依次将关键字存放到散列表中,具体过程如下:
1. 将关键字 22 存放到散列地址 8 中。
2. 将关键字 41 存放到散列地址 9 中。
3. 将关键字 53 存放到散列地址 4 中。
4. 将关键字 46 存放到散列地址 0 中。
5. 将关键字 30 存放到散列地址 2 中。
6. 将关键字 13 存放到散列地址 6 中。
7. 将关键字 01 存放到散列地址 3 中。
8. 将关键字 67 存放到散列地址 1 中。
最终哈希表的状态如下:
|散列地址|关键字|
|--------|------|
|0 |46 |
|1 |67 |
|2 |30 |
|3 |01 |
|4 |53 |
|5 | |
|6 |13 |
|7 | |
|8 |22 |
|9 |41 |
|10 | |
阅读全文