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

来源：学生作业帮编辑：作业帮分类：数学作业时间：2024/05/15 18:47:27

关于哈希表查找不成功时的平均查找长度
我找了很多,产生了一个疑问:
假设:
哈希表长为: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,而有效位个数其实就是12,博客随后还举了个字母表的例子进一步说明这个问题.
计算不成功AVL时,一定是依据具体hash函数计算的,正如你所言,虽然表长为16,但实际查找时最初只可能产生0-12一共13种结果,所以应该除的是13,你的理解是正确的.
有问题欢迎继续讨论.

关于哈希表查找不成功时的平均查找长度折半查找,不成功的平均搜索长度怎么算的? 折半查找不成功的平均搜索长度怎么求? 关于数据结构二分法查找成功的平均查找长度和失败的查找长度求“在散列表上查找成功与不成功的平均查找长度 ”具体分析过程,关于这点的知识,不懂, 算平均查找长度长度为12的按关键字有序的查找表采用顺序组织方式,若用二分法查找,则在等概率情况下,查找不成功的平均查找长计算各种查找方法在等概率情况下查找成功时的平均查找长度数据结构题目：才用折半查找算法在长度为12的有序表中查找一个元素时,查找成功的平均查找长度为多少?... 在一个长度为n的顺序线性表中顺序查找值为x的元素时,查找成功时平均查找长度为多少顺序表长度为n的折半查找算法的平均查找长度在一个长度为n顺序线性表中顺序查找值为x的元素时,查找的平均长度为对一个长度为10的排好序的表用二分法查找,若查找不成功,至少需要比较的次数是?