关于哈希表查找不成功时的平均查找长度
来源:学生作业帮 编辑:搜搜考试网作业帮 分类:数学作业 时间:2024/07/07 07:35:17
关于哈希表查找不成功时的平均查找长度
我找了很多,产生了一个疑问:
假设:
哈希表长为: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
那么查找不成功时的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,你的理解是正确的.
有问题欢迎继续讨论.
“求查找不成功时的平均查找长度,一般情况下分母为表长,但精确地讲是表长的有效位个数”
(红字部分)
注意这里的表长其实就是你说的16,而有效位个数其实就是12,博客随后还举了个字母表的例子进一步说明这个问题.
计算不成功AVL时,一定是依据具体hash函数计算的,正如你所言,虽然表长为16,但实际查找时最初只可能产生0-12一共13种结果,所以应该除的是13,你的理解是正确的.
有问题欢迎继续讨论.
关于哈希表查找不成功时的平均查找长度
折半查找,不成功的平均搜索长度 怎么算的?
折半查找不成功的平均搜索长度怎么求?
关于数据结构二分法查找成功的平均查找长度和失败的查找长度
求“在散列表上查找成功与不成功的平均查找长度 ”具体分析过程,关于这点的知识,不懂,
算平均查找长度长度为12的按关键字有序的查找表采用顺序组织方式,若用二分法查找,则在等概率情况下,查找不成功的平均查找长
计算各种查找方法在等概率情况下查找成功时的平均查找长度
数据结构题目:才用折半查找算法在长度为12的有序表中查找一个元素时,查找成功的平均查找长度为多少?...
在一个长度为n的顺序线性表中顺序查找值为x的元素时,查找成功时平均查找长度为多少
顺序表长度为n的折半查找算法的平均查找长度
在一个长度为n顺序线性表中顺序查找值为x的元素时,查找的平均长度为
对一个长度为10的排好序的表用二分法查找,若查找不成功,至少需要比较的次数是?