已知关键字序列为:(75, 33, 52, 41, 12, 88, 66, 27)哈希表长为10,哈希函数为: H(k)=K MOD 7, 解决冲突用线性探测再散列法,构造哈希表,求等概率下查找成功的平均查找长度。
时间: 2023-07-15 22:12:56 浏览: 211
首先,我们需要用哈希函数将关键字映射到哈希表中的位置。根据题目给定的哈希函数,得到以下结果:
- 75 → H(75) = 75 mod 7 = 3
- 33 → H(33) = 33 mod 7 = 5
- 52 → H(52) = 52 mod 7 = 3 (冲突,需要线性探测)
- 41 → H(41) = 41 mod 7 = 6
- 12 → H(12) = 12 mod 7 = 5 (冲突,需要线性探测)
- 88 → H(88) = 88 mod 7 = 4
- 66 → H(66) = 66 mod 7 = 3 (冲突,需要线性探测)
- 27 → H(27) = 27 mod 7 = 6 (冲突,需要线性探测)
接下来,我们使用线性探测再散列法来解决冲突。具体方法是,当发生冲突时,在哈希表中查找下一个可用位置,直到找到一个空闲位置为止。在这个例子中,我们得到以下哈希表:
| 位置 | 关键字 |
| ---- | ------ |
| 0 | |
| 1 | |
| 2 | |
| 3 | 75 |
| 4 | 88 |
| 5 | 33 |
| 6 | 52 |
| 7 | 41 |
| 8 | 12 |
| 9 | 27 |
接下来,我们可以计算等概率下查找成功的平均查找长度。假设哈希表中有n个关键字,每个位置被查找的概率相等,即为1/n。设查找成功的平均查找长度为ASL,那么:
ASL = (1/n) * (1 + 2 + ... + n-1 + n/m)
其中,m为哈希表长度,n为关键字个数。在这个例子中,m=10,n=8,因此:
ASL = (1/8) * (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8/10)
= 4.375
因此,等概率下查找成功的平均查找长度为4.375。
阅读全文