对下面的关键字集{30,15,21,40,25,26,36,37}若查找表的装填因子为0.8,采用线性探测再散列方法解决冲突,完成下列内容: (1)设计哈希函数; (2)画出哈希表; (3)计算查找成功和查找失败的平均查找长度。
时间: 2023-12-08 22:20:51 浏览: 273
好的,我来解答您的问题。
1. 设计哈希函数
线性探测再散列方法是一种基于哈希函数将关键字映射到哈希表中的解决冲突方法。其中,哈希函数的设计是非常重要的一环。在本题中,我们可以采用简单的取模法来设计哈希函数,具体步骤如下:
首先,确定哈希表的大小为12(根据装填因子0.8计算得到);
其次,选择一个较小的质数p,使得p大于12,例如p=17;
最后,对于任意一个关键字k,我们可以使用以下公式计算其哈希地址:
h(k) = k % p % 12
其中,%表示取模运算。
2. 画出哈希表
根据上述哈希函数的设计,我们可以画出如下的哈希表:
```
0:
1: 15
2:
3: 30
4:
5:
6: 21
7: 25
8: 26
9: 40
10: 36
11: 37
```
3. 计算查找成功和查找失败的平均查找长度
在本题中,我们需要计算查找成功和查找失败的平均查找长度。具体计算公式如下:
- 查找成功的平均查找长度ASL(S) = (n + 1) / 2n - (ln(1 - n / m)) / 2
- 查找失败的平均查找长度ASL(F) = m / (2 * (m - n))
其中,n表示哈希表中已经存储的关键字个数,m表示哈希表的大小,ln表示自然对数。
针对本题中的数据集,我们可以计算得到:
- n = 8, m = 12
- ASL(S) = (8 + 1) / (2 * 8) - (ln(1 - 8 / 12)) / 2 = 1.1
- ASL(F) = 12 / (2 * (12 - 8)) = 1.5
因此,我们可以得出结论:采用线性探测再散列方法,对于本题中的数据集,查找成功的平均查找长度为1.1,查找失败的平均查找长度为1.5。
阅读全文