今天数据结构老师讲的哈希表，留了一个“如何计算哈希表查找失败时的平均查找长度”可是把我给难为住了。（从中午12：00到下午16：00才搞懂，果然还是我太vegetable了 几个小伙儿伴纷纷查资料，又是计算又是讨论，但是始终没有得到一致的结论。 纠结的点主要就是：分母应该是哈希表长还是哈希函数里所给的MOD后面的13呢。查了很多资料发现里面的说法不一，而且查到的每一篇博客所给的题目都是除数（MOD后面的那个数）和哈希表长相等。（啊，可能我找的太少啦吧，找啦两三篇都是这样就去问老师啦） 后来同学告诉我慕课上面讲的就有…anyway~现在是懂了，下面我就用大白话来描述一下我对这个“查找失败时的平均查找长度”的理解 就比如说，你的哈希表如下所示（由上面题目“采用线性探测再散列”生成的哈希表；）： 创建过程为：按照关键字序列顺序依次向哈希表中填入，发生冲突后按照“线性探测”探测到第一个空位置填入 现在我问你：我想要查找关键字“2”，那么我需要比较多少次才能知道失败了呢？ 答：根据所生成的表可以很容易的看出，关键字“2”不存在于表中。通过题目所给的哈希函数H(key)=key MOD 13可以算出关键字“2”应该在表中序号为2的位置，而如果2的位置所存的数与关键字“2”不相等，那么我需要按照“线性探测”直到找到关键字“2”。如果我没有找到关键字“2”，反而是遇到了空的位置，那么就说明关键字“2”查找失败了，那么我所走的步数就是查找失败的次数。把所有的位置查找失败的次数加起来除以表的总长度，就是“查找失败时的平均查找长度” ps：如果有错误欢迎指正，来自一个卑微的计算机大学僧 答案（以线性探测再散列为例）：第一行：序号；第二行：关键字；第三行：查找成功时查找长度；第四行：查找失败时查找长度 查找失败时的平均查找长度=（1+13+12+11+10+9+8+7+6+5+4+3+2+1+1）/ 15 = 93 / 15
题目描述：
1.请回答采用线性探测再散列和链地址法处理冲突构建的哈希表中，查找失败时的平均查找长度如何计算?
例:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为: H(key)=key MOD 13,哈希表长为m=15,设每个记录的查找概率相等，采用以上两种方法处理冲突，查找失败时的平均查找长度各是多少?
查找失败的次数就是指：根据哈希函数算出来你所要查找的关键字的位置，如果这个位置存的不是你的目标关键字，那么就按照你所定的存储哈希函数的规则，也就是所在位置+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
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
1
2
1
4
3
1
1
3
9
1
1
3
1
13
12
11
10
9
8
7
6
5
4
3
2
1
1
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)
