【数据结构】哈希表查找失败时的平均查找长度_哈希表查找失败的平均查找长度

作者：不正经 | 2024-06-09 15:09:03

踩

哈希表查找失败的平均查找长度

设有一组关键字{19, 1, 23, 14, 55, 20, 84, 27, 68, 11, 10, 77}
哈希函数为：H(key) = key % 13
采用开放地址法的线性探测法处理冲突
试0~18的哈希表中对该关键字序列构造哈希表，并求成功和不成功时的平均查找长度

在这里插入图片描述
ASL成功 = (1 + 2 +1 + 4 + 3 + 1 + 1 + 3 + 1 + 1 + 3 + 2) / 12 = 1.92

ASL失败 = (1 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) / 13 = 4.46

计算 ASL成功除的是参与散列的元素个数
计算 ASL失败除的是可能散列到的值的个数，这道题是13，而不是19

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/694618