哈希表查找失败平均次数计算

发布网友发布时间：2023-08-17 04:01

共1个回答

热心网友时间：2024-06-12 09:32

查找失败就是说要找的那个值没有在哈希表里面。你放上来的题没给哈希函数没法给你分析，我给你举个例：假如你的哈希函数是key=x mod 10，填充后的哈希表如下所示： 0 1 2 3 4 5 6 7 8 9 10 1110 1 12 15 25 18 19 29 如果你要查找这个哈希表里面有没有0这个数，那你就会去序号0下面找，这个地方被10填充了，那就往后找，后面依次是1、12，都不等于0，再往后就为空，说明这个表里面没有0。总共查找了4次。如果你要查找这个哈希表里面有没有2这个数，那你就会去序号2下面找，做一次比较，下面是12，不相等，往后面找，后面是空，那查找结束。总共查找了2次。如果你要找29，那就会在序号9下面找，这里被19填充了，于是往后，找到29。总共查找了2次。所以，每次查找不成功的查找长度就等于从序号找到第一个空的格子的距离。在我举的这个例子里面，ASL=（4+3+2+1+1+3+2+1+4+3+2+1）/12 不知道你明白了没~追问我懂你说的这些，可能我的问题没有描述清楚。你打开我给的链接，就是当计算地址为6时，单表里不存在，那么为什么不是继续向后与地址7.8.9比较，而是循环回地址0去比较。