线性探测如何在不中断查找的情况下处理删除？

Question

这是我对线性探测的理解。

对于插入： - 我们散列到某个位置。如果该位置已经有值，我们线性递增到下一个位置，直到遇到空位置，然后在那里插入。这就说得通了。

我的问题围绕查找。从我读过的描述来看，我相信查找的工作方式如下：

• 我们查看我们正在寻找哈希值的项目的位置。
• 如果位置为空，我们返回 Not Found
• 如果位置已满，我们线性移动到位置，直到遇到我们正在寻找的值，或者遇到空位置（意味着未找到）

那么当我们从哈希中删除一个项目时，这是如何工作的呢？这不会扰乱这次查找吗？假设两个项目散列到相同的位置。我们添加这两个项目，然后删除我们添加的第一个项目。所以现在，第二个项目的预期位置（必须移动到不同的位置，因为第一个项目最初占据了它）是空的。删除是否以某种方式处理这个问题？

Answer 1

好问题！您完全正确，仅从线性探测表中删除一个项目就会在您报告的情况下引起问题。

对此有几个解决方案。一种是使用墓碑删除。在逻辑删除中，要删除某个元素，您可以使用称为逻辑删除的标记来替换该元素，该标记指示“元素曾经位于此处，但已被删除”。然后，当您进行查找时，您将使用与之前相同的过程：跳转到哈希位置，然后继续前进，直到找到空白点。这里的想法是，墓碑不算是空白点，因此您将继续扫描它以找到您要搜索的内容。

为了保持逻辑删除的数量较少，您可以使用一些不错的技术，例如在插入期间覆盖逻辑删除或在逻辑删除的数量变得太大时全局重建表。

另一种选择是使用Robin Hood 散列和后移删除。在罗宾汉散列中，您将元素存储在表中的方式基本上使它们按散列码排序（表前面的环绕使事情比这更复杂，但这是一般想法）。从那里开始，在进行删除时，您可以将元素向后移动一个位置以填充已删除元素的间隙，直到您遇到空白或已经位于正确位置并且不需要移动的元素。

有关这方面的更多信息，请查看有关线性探测和罗宾汉散列的讲座幻灯片。

希望这可以帮助！