哈希表等概率情况下查找成功和查找不成功的平(2)

key7一次就填入了表中,因此查找次数为1,同理8, 30, 11查找次数均为1; key18 进行了3次放入操作,探测位置分别是5,6,7 ,因此查找次数为3;key9也是3次;key14 进行了两次探测,因此查找次数为2。次数表如表3所示

Key   7   8   30   11   18   9   14  
Count   1   1   1   1   3   3   2  

(表3)

所以ASLsuccess= (1+1+1+1+3+3+2)/ 7 = 12/7。

等概率情况下查找不成功的平均查找长度:

接下来讨论不成功的情况, 看表2,计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可, 但根据哈希函数地址为MOD7,因此初始只可能在0~6的位置。等概率情况下,查找0~6位置查找失败的查找次数为:

看地址0,到第一个关键字为空的地址2的距离为3,因此查找不成功的次数为3.

地址1, 到第一个关键为空的地址2的距离为2,因此查找不成功的次数为2.

地址2,  到第一个关键为空的地址2的距离为1,因此查找不成功的次数为1.

地址3,到第一个关键为空的地址4的距离为2,因此查找不成功的次数为2.

地址4,到第一个关键为空的地址4的距离为1,因此查找不成功的次数为1.

地址5,到第一个关键为空的地址2(注意不是地址9,因为初始只可能在0~6之间,因此循环回去)的距离为5,因此查找不成功的次数为5.

地址6,到第一个关键为空的地址2(注意不是地址9,因为初始只可能在0~6之间,因此循环回去)的距离为4,因此查找不成功的次数为4.

因此查找不成功的次数表如下表所示

Key   7   8   30   11   18   9   14  
Count   3   2   1   2   1   5   4  

(表4)

所以ASLunsuccess= (3+2+1+2+1+5+4)/ 7 = 18/7。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/94aa134bf6e51a722a1aaa4936f5772e.html