关于哈希表查找不成功时的平均查找长度我找了很多,产生了一个疑问:假设:哈希表长为: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/06/30 07:22:38
![关于哈希表查找不成功时的平均查找长度我找了很多,产生了一个疑问:假设:哈希表长为: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](/uploads/image/z/8664295-31-5.jpg?t=%E5%85%B3%E4%BA%8E%E5%93%88%E5%B8%8C%E8%A1%A8%E6%9F%A5%E6%89%BE%E4%B8%8D%E6%88%90%E5%8A%9F%E6%97%B6%E7%9A%84%E5%B9%B3%E5%9D%87%E6%9F%A5%E6%89%BE%E9%95%BF%E5%BA%A6%E6%88%91%E6%89%BE%E4%BA%86%E5%BE%88%E5%A4%9A%2C%E4%BA%A7%E7%94%9F%E4%BA%86%E4%B8%80%E4%B8%AA%E7%96%91%E9%97%AE%3A%E5%81%87%E8%AE%BE%3A%E5%93%88%E5%B8%8C%E8%A1%A8%E9%95%BF%E4%B8%BA%3A16%280%7E15%29%E5%93%88%E5%B8%8C%E5%87%BD%E6%95%B0%E4%B8%BA%3Ah%28key%29%3Dkey+mod+13%E6%9E%84%E9%80%A0%E5%93%88%E5%B8%8C%E8%A1%A8%E4%B8%BA%3A0+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
关于哈希表查找不成功时的平均查找长度
我找了很多,产生了一个疑问:
假设:
哈希表长为: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,你的理解是正确的.
有问题欢迎继续讨论.