algorithm - 使用散列搜索

Question

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

索引 KEY

• 0 - - S7

• 1 - - S1

• 2 - - 空

• 3 - - S4

• 4 - - S2

• 5 - - 空

• 6 - - S5

• 7 - - 空

• 8 - - S6

• 9 - - S3

假设我想找到一个元素 S8(显然不存在)..在计算 S8 的散列函数时假设它跳转到索引 8。找不到索引 8 处的元素，通过线性探测它检查下一个索引等等 .. 现在，比较的次数应该是数组的总长度，因为通过线性探测，它应该尝试查看每个索引...但实际答案是 5! :|请任何人解释!!

Answer 1

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

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