关联

主要是线性检测失败和链地址法搜索失败。

它们的分母都是mod，就是你取的小于等于m表长度的最大质数。

最好的解释就是问题

给定一组查找关键字(32,15,7,11,4,28,56,61,79)，哈希表长为m=12，请按照除留余数法设计一个哈希函数，设每个记录的查找概率相等。
（1）画出按照线性探测再散列处理冲突得到的哈希表（给出求解过程），并计算等概率情况下查找成功和查找失败时的平均查找长度各是多少。
（2）画出按照链地址法处理冲突得到的哈希表，并计算等概率情况下查找成功和查找失败时的平均查找长度各是多少。

第一步，写线性表

找到正确的概率为

搜索成功时的平均搜索长度为：ASL = (7x1 + 1x2 + 1x3)/9 = 12/9 = 4/3

看括号里的数据

1+1+1+1+2+1+1+2+3+1=12

比如直接输入32，也就是一次，但是如果看4，先输入4不行，但是再走一步输入5就可以了，所以运行两次。

求错误概率为

搜索失败时的平均搜索长度为：ASL = (4+3+2+1+6+5+4+3+2+1+2)/11 = 33/11 = 3

查看括号内

失败的概率是它与空白窗口的距离

分母为 mod=11

所以你想看的是0-10。 如果超过11的范围，就不要看。

括号内=4+3+2+1+

请注意，当您到达序列号 3 时，它距离您为 1。 那么要向后检查序号4的数据15，找到离它最近的空白距离，即到9的距离=6

总计为4+3+2+1+6+5+4+3+2+1+2=33

请参阅下一个问题

链地址法

先画图

如果搜索成功，就垂直看

搜索成功时的平均搜索长度为：ASL = (7x1 + 2x2)/9 = 11/9

再次查看失败的搜索

只看侧面

分母也是 mod=11

因此，只会查看0到10之间的数据，超过它的数据将不会被查看。 例如，序列号为11的元素将不参与。

这里我们学到的是加一个空指针，所以我们需要加1

例如：序号3，横向看没有元素，为0，但是添加了一个空指针+1=1。

总数从0到10

2+2+2+1+3+1+3+2+1+1+2=20

搜索失败时的平均搜索长度为：ASL = (2x5 + 1x4 + 3x2)/11 = 20/11