关于哈希表查找不成功时的平均查找长度我找了很多,产生了一个疑问:假设:哈希表长为: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
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/20 15:32:22
关于哈希表查找不成功时的平均查找长度我找了很多,产生了一个疑问:假设:哈希表长为: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
关于哈希表查找不成功时的平均查找长度
我找了很多,产生了一个疑问:
假设:
哈希表长为: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查找不成功的比较次数是为什么?
不应该再求查找不成功时ASL除以表长(16),应该是0~12的查找不成功比较次数,并且除以13,
希望得到权威的回答唉...
关于哈希表查找不成功时的平均查找长度我找了很多,产生了一个疑问:假设:哈希表长为: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
我感觉你可能并没有仔细看那个博客上的讲解,实际上你的理解是对的,而博客上也是那样讲的.博客上是这样说的：
“求查找不成功时的平均查找长度,一般情况下分母为表长,但精确地讲是表长的有效位个数”
（红字部分）
注意这里的表长其实就是你说的16,而有效位个数其实就是12,博客随后还举了个字母表的例子进一步说明这个问题.
计算不成功AVL时,一定是依据具体hash函数计算的,正如你所言,虽然表长为16,但实际查找时最初只可能产生0-12一共13种结果,所以应该除的是13,你的理解是正确的.
有问题欢迎继续讨论.