如何计算哈希表查找失败时的平均查找长度

article/2025/11/9 1:28:34

题目描述：
1.请回答采用线性探测再散列和链地址法处理冲突构建的哈希表中，查找失败时的平均查找长度如何计算?
例:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为: H(key)=key MOD 13,哈希表长为m=15,设每个记录的查找概率相等，采用以上两种方法处理冲突，查找失败时的平均查找长度各是多少?

今天数据结构老师讲的哈希表，留了一个“如何计算哈希表查找失败时的平均查找长度”可是把我给难为住了。（从中午12：00到下午16：00才搞懂，果然还是我太vegetable了

几个小伙儿伴纷纷查资料，又是计算又是讨论，但是始终没有得到一致的结论。

纠结的点主要就是：分母应该是哈希表长还是哈希函数里所给的MOD后面的13呢。查了很多资料发现里面的说法不一，而且查到的每一篇博客所给的题目都是除数（MOD后面的那个数）和哈希表长相等。（啊，可能我找的太少啦吧，找啦两三篇都是这样就去问老师啦）

后来同学告诉我慕课上面讲的就有...anyway~现在是懂了，下面我就用大白话来描述一下我对这个“查找失败时的平均查找长度”的理解

查找失败的次数就是指：根据哈希函数算出来你所要查找的关键字的位置，如果这个位置存的不是你的目标关键字，那么就按照你所定的存储哈希函数的规则，也就是所在位置+1向后寻找，直到找到你所要的关键字，如果遇到了表中的空位，那么就说明这个表中没有这个关键字，那么查找失败的次数就是你从“通过哈希函数算出的位置”到“表中的第一个遇到的空位”所经过的位数

也就是说，分母指的是哈希表所给定的长度！！！

就比如说，你的哈希表如下所示（由上面题目“采用线性探测再散列”生成的哈希表；）：

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
	14	1	68	27	55	19	20	84	79	23	11	10

创建过程为：按照关键字序列顺序依次向哈希表中填入，发生冲突后按照“线性探测”探测到第一个空位置填入

现在我问你：我想要查找关键字“2”，那么我需要比较多少次才能知道失败了呢？

答：根据所生成的表可以很容易的看出，关键字“2”不存在于表中。通过题目所给的哈希函数H(key)=key MOD 13可以算出关键字“2”应该在表中序号为2的位置，而如果2的位置所存的数与关键字“2”不相等，那么我需要按照“线性探测”直到找到关键字“2”。如果我没有找到关键字“2”，反而是遇到了空的位置，那么就说明关键字“2”查找失败了，那么我所走的步数就是查找失败的次数。把所有的位置查找失败的次数加起来除以表的总长度，就是“查找失败时的平均查找长度”

ps：如果有错误欢迎指正，来自一个卑微的计算机大学僧