请问哈希表查找不成功的平均查找长度是怎么算的？

flyingbox

请问下，查找不成功的平均查找长度是怎么算的？
比较愚钝，看书看不太明白。谢谢！

ziggler

似乎应该是(9+8+7+6+5+4+3+2+1+1+1)/11=47/11

某个(哈希表中并不存在的)值n对11取余之后，结果可能是0～10
如果n mod 11的值是8、9、10那么1次查找之后就可以判定表中不存在这个值，
如果n mod 11 = 0，那么还需要偏移，一共9次查找才能判定表中没有这个值，
如果n mod 11 = 1，那么需要8次查找才能判定表中没有这个值，
如果n mod 11 = 2，那么需要7次查找才能判定表中没有这个值，
……
如果n mod 11 = 7，那么需要2次查找才能判定表中没有这个值。
所以不成功的平均查找长度就是上述查找次数取均值。
急！！！求哈希表查找失败的平均查找长度 我理解不了请高手详细解答一下 谢谢！ (13 August 2009)
http://topic.csdn.net/u/20080512 ... c-f31d74da38c2.html

bjruntest

推荐一本书 数据结构与算法
shujujiegou

bjruntest

推荐一本书 数据结构与算法
shujujiegou

ubuntuer

给你举个例子吧,就拿老严的书上的说吧
{19，14，23，01，68，20，84，27，55，11，10，79}

hash = key% 13;
分离链接解决冲突法


key          kash_key          find_numbers
19                6                        1
14                1                        1
23               10                       1
01                1                        2   (  01->14)
68                3                        1
20                7                        1
84                6                        2   (  84->19)  
27                1                        3   (  27->01->14)
55                3                        2   (  55->68)
11                11                      1  
10                10                      2   ( 10->23 )
79                1                        4   (  79->27->01->14)         

ASL(12) = (1*6+2*4+3+4)/12