1

假设我们有一个包含 10 个桶的哈希表，并且最初使用使用线性探测的哈希函数输入符号 S1 到 S7。搜索不存在的项目所需的最大比较次数是多少？哈希图可以解释为：

Index KEY

  • 0 - - S7

  • 1 - - S1

  • 2 - - 空

  • 3 - - S4

  • 4 - - S2

  • 5 - - 空

  • 6 - - S5

  • 7 - - 空

  • 8 - - S6

  • 9 - - S3

假设我想找到一个元素 S8（显然不存在）..在计算 S8 的哈希函数时假设它跳转到索引 8。在索引 8 处找不到元素，通过线性探测它检查下一个索引等等.. Now, the number of comparisons should come out to be total length of the array because by linear probing it should try to look in every index...但实际答案是 5！:| 请任何人解释！

4

1 回答 1

4

线性探测将寻找一个元素，直到它碰到一个空的哈希桶。在这种情况下，它将检查 8、9、0、1 和 2；在 2 它将停止，因为桶是空的。

请注意，删除是通过用特殊的“墓碑”值替换存储桶来处理的，该值将元素标记为已删除，但避免破坏线性探测链。因此，在元素为空的情况下，线性探头仍然可以正常工作。

于 2012-10-04T06:26:07.353 回答