Question

关于哈希表查找不成功时的平均查找长度

我找了很多,产生了一个疑问:
假设:
哈希表长为:16(0~15)
哈希函数为:h(key)=key mod 13
构造哈希表为:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
14 1 68 27 55 19 20 84 79 23 11 10
那么查找不成功时的ASL是计算的是0~15每个哈希地址查找不成功的比较次数
问题是:h(key)=key mod 13 第一次 的值只可能是0~12(也就是说第一次用哈希函数求得的地址不可能是13~15),那计算13,14,15查找不成功的比较次数是为什么?
我找到了这个http://blog.sina.com.cn/s/blog_6c37da0901017bcj.html,感觉老师讲的有错误
不应该再求查找不成功时ASL除以表长(16),应该是0~12的查找不成功比较次数,并且除以13,
希望得到权威的回答唉...

Answer 1

我感觉你可能并没有仔细看那个博客上的讲解，实际上你的理解是对的，而博客上也是那样讲的。博客上是这样说的：
“求查找不成功时的平均查找长度，一般情况下分母为表长，但精确地讲是表长的有效位个数”
（红字部分）

注意这里的表长其实就是你说的16，而有效位个数其实就是12，博客随后还举了个字母表的例子进一步说明这个问题。
计算不成功AVL时，一定是依据具体hash函数计算的，正如你所言，虽然表长为16，但实际查找时最初只可能产生0-12一共13种结果，所以应该除的是13，你的理解是正确的。

有问题欢迎继续讨论。