散列表解决冲突的线性探测与平方探测查找成功、失败平均查找长度

默认已经学习过前面内容
m是散列表表长，p是散列函数的取余数，di是处理冲突的增量，H(key)是散列函数

线性探测法

H'(key)=(H(key)+di)%m di=0,1,2,…,m-1
其中H(key)=key%p
则 ASL成功=(插入记录的比较次数总和)/插入记录的次数
ASL失败=([0,p-1]的查找不成功的次数就是直接找关键字到第一个地址上关键字为空的距离 总和)/p

例题1

表长m=14，H(key)=key%11,表中现有4个结点，其中H(15)=4,H(38)=5,H(61)=6,H(84)=7,处理冲突使用线性探测法，求插入关键字49的地址
Ans：
构造散列表

比较次数：

• 15 1
• 38 1
• 61 1
• 84 1
• 49 4

ASL成功 = (1+1+1+1+4)/5 = 8/5

ASL失败 = (1+1+1+1+6+5+4+3+2=1+1)/11 = 26/11

平方探测法

H'(key)=(H(key)+di)%m di= 0, 1^2, -1^2, 2^2, -2^2, …, k^2, -k^2
则 ASL成功=(插入记录的比较次数总和)/插入记录的次数
ASL失败=([0,p-1]的查找不成功的次数就是直接找关键字到第一个地址上关键字为空的距离 总和)/p

例题2

H(key)=key%8 {1,13,12,34,38,33,27,22} 表长11
Ans：
构造散列表

比较次数：

• 33 3
• 1 1
• 34 1
• 27 1
• 12 1
• 13 1
• 38 1
• 22 2
  ASL成功 = (3+1+1+1+1+1+1+2)/8=11/8

失败次数：

• 33 3
• 1 5
• 34 7
• 27 9
• 12 8
• 13 6
• 38 4
• 22 2
  ASL失败 = (3+5+7+9+8+6+4+2)/8 = 11/2

总结

ASL成功= 插入关键字时的比较次数 / 关键字个数
ASL失败 = 查找不成功的比较次数 / 查找不成功时的地址个数
线性探测与平方探测的失败比较次数求法不同