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

Question

以下是我对线性探测的理解。

对于插入：-我们散列到某个位置。如果该位置已经有一个值，我们线性增加到下一个位置，直到我们遇到一个空位置，然后我们在那里插入。这是有意义的。

我的问题围绕着查找。从我读过的描述中，我相信查找是这样工作的：

• 我们查看要查找散列的项的位置

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

Answer 1

线性探测（开放寻址）中的删除是以这样一种方式进行的，即在删除值的索引处分配任何标记，如“删除”。[可以在该索引处键入除“无”之外的任何值，以指示该索引处的值已被删除]。请看下面的代码片段，以说明我如何使用“删除”标记来填充删除值的索引

        if self.table[index] == value:
          print("key {} is found in the table and hence deletion tag is updated at that position".format(value))
          self.table[index] = "Deletion"

现在，当再次完成搜索时会发生什么，这个位置不是无，搜索将继续。请参阅下面的片段，搜索是如何在线性探针中实现的

    def search(self, value):
      index = value % self.table_size

      if self.table[index] != value:
        while self.table[index] is not None and self.table[index] != value:
            index = (index + 1) % self.table_size
      if self.table[index] == value:
        print("Key is found in the table")
      else:
        print("key is not found in the table")

还可以查看github代码，它解释了线性探测中的删除，而不中断查找。

Answer 2

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

有几种解决方案。一种是使用墓碑删除。在删除墓碑中，要删除一个元素，可以用一个名为墓碑的标记替换该元素，该标记指示“一个元素以前在这里，但后来被删除了”然后，在进行查找时，使用与之前相同的过程：跳转到散列位置，然后继续前进，直到找到一个空白点。这里的想法是，墓碑不算作空白点，所以你会不断地扫描它，以找到你正在搜索的内容。

为了保持较低的墓碑数量，您可以使用一些很好的技术，例如在插入过程中覆盖墓碑，或者在墓碑数量过多时全局重建表。

另一个选择是使用Robin Hood哈希和后移删除。在Robin Hood哈希中，你存储表中元素的方式基本上是让它们按照哈希代码排序（表前面的环绕会让事情变得更复杂，但这是一般的想法）。从那里开始，在进行删除时，你可以向后移动元素一点，以填补被删除元素的空白，直到你找到一个空白或一个已经在正确位置且不需要移动的元素。

有关此的更多信息，请查看这些关于线性探测和罗宾汉哈希的讲座幻灯片。

希望这有帮助！