设有一组关键字{9,01,23,14,55,20,84,27},采用哈希函数:H(key)=key mod 7 ,表长为10,用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,…,)解决冲突。计算查找成功的平均查找长度为( )。
时间: 2023-09-27 09:04:46 浏览: 232
首先要构建哈希表,根据哈希函数,将关键字映射到对应的位置上:
|位置|关键字|
|--|--|
|0|55|
|1|01|
|2|9|
|3|84|
|4|14|
|5|23|
|6|27|
|7||
|8|20|
|9||
其中,位置7和位置9都没有被占用,这是为了方便计算而添加的。
接下来,我们以关键字14为例,演示一次查找过程:
1. 根据哈希函数计算出该关键字的位置:H(14) = 14 mod 7 = 0;
2. 在位置0处找到关键字55,与要查找的关键字14不一致,需要继续查找;
3. 根据二次探测再散列方法,计算出下一个探测位置:H(14) + d1^2 = 0 + 12 = 1;
4. 在位置1处找到关键字01,与要查找的关键字14不一致,需要继续查找;
5. 根据二次探测再散列方法,计算出下一个探测位置:H(14) + d2^2 = 0 + 22 = 4;
6. 在位置4处找到关键字14,与要查找的关键字一致,查找成功。
由此可见,查找成功的平均查找长度需要考虑两种情况:查找成功和查找失败。在本题中,查找失败的情况是没有找到要查找的关键字,需要一直探测到一个空位置才能结束查找。
设关键字总数为n,则查找成功的概率为1/n,查找失败的概率为(n-1)/n。对于查找成功的情况,平均查找长度为1;对于查找失败的情况,平均查找长度为(1+1/2+1/3+...+1/(n-1))。
根据题目中的数据,n=8,因此查找失败的平均查找长度为(1+1/2+1/3+...+1/7)≈2.8284。综合考虑查找成功和查找失败的情况,平均查找长度为1/n + (n-1)/n * (1+1/2+1/3+...+1/(n-1))。
带入数据,得到平均查找长度为1/8 + 7/8 * 2.8284 ≈ 2.5858。因此,答案为2.5858。
阅读全文