现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采用线性探查(线性探测再散_

学习人数: 6.4k

正确率: 60%

题目描述

未通过

现有长度为11且初始为空的散列表HT，散列函数是H(key)=key%7，采用线性探查(线性探测再散列)法解决冲突将关键字序列87，40，30，6，11，22，98，20依次插入到HT后，HT查找失败的平均查找长度是

A. 4

B. 5.25

C. 6

D. 6.29

上面问题的答案是：

A 选项

B 选项

C 选项

D 选项

加入错题本

个人笔记

已有23条笔记

2 个回答 (点击展开回答)

2023年12月12日 18:37

散列表的比较次数，和探测次数，是相同还是相差1？谢谢

2023年4月18日 11:44

1. 构造散列表
根据散列函数 H(key) = key %7 以及线性再探测，构造出散列表，如下图在这里插入图片描述

2. 计算失败的平均查找长度

计算失败，可以转换理解，就是在已经构造好的散列表上，我们再去插入一个新的值需要比较多少次。

比如，现在我再插入一个数 21，那么理论上应该存放在地址 0 的位置，但是地址 0 有 98 了，则我们线性再探测（就是依次增加一个地址，看是否为空，空则可以插入），同理地址 1 也存在元素。以此类推，我们一共要比较地址 0~7，发现都有值，直到比较地址 8 才为空。所以一共比较了 9 次。

对其他地址（0~6）用同样的方式去理解，则一共比较的次数是 9+8+7+6+5+4+3 = 42

这里要注意，因为我们的模是 7，所以计算的地址只可能在（0~6）这个范围，所以最后的结果是 42/7 =6

3.计算成功的平均查找长度
计算成功的长度，就是记录下每个数值比较了几次找到可存储的空间。
比如，本题每个数值比较（并存入）对应地址的次数如下图。
在这里插入图片描述

所以其 ASL = 1+1+1+1+1+1+1+1/8=1

note
1.注意失败与成功的查找长度的分母意义是不同的，失败时，分母是模的值；成功时，分母是元素个数。

西瓜不腻回复 13245372484：请问查找成功时，查找20是不是要2次啊

2023年12月8日 19:15

huyufeu1009 回复西瓜不腻：我感觉也是，求解答

2024年7月18日 21:34

小灰机回复 13245372484：为什么查找失败最后没有加2？反而只是到3？

2024年12月1日 17:54