data-structures - 对哈希表中基于开放寻址的线性探测方法感到困惑？

Question

假设根据字符串“temp”的散列函数的数组索引是 155，并且位置 155 被预先占用，然后尝试位置 156。假设位置 156 可用，因此该条目保存在位置 156 而不是 155。稍后我找到另一个字符串“another_temp”，它映射到位置 156。再次将其保存在下一个可用位置 157 中。

问题是：稍后如果我想找出“another_temp”的位置，我怎么知道它是 157 而不是 156，即使哈希函数返回 156？

谢谢。

Answer 1

您需要比较密钥，而不仅仅是哈希码。在哈希表中，您无论如何都需要存储密钥（在您的情况下为“temp”和“another_temp”）。仅仅存储和比较哈希值是不够的，因为哈希值不是唯一的。

开放寻址存在一些问题。一是：删除条目后怎么办？通常您存储一个特殊的“已删除”标记。另一个问题是：如果发生冲突，是否应该增加哈希码？您将在 Wikipedia 中找到更多详细信息。