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

Question

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

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

我的问题围绕查找展开。从我读过的描述来看，我相信查找是这样工作的：

我们查看要查找的项目的散列位置。
如果位置为空，我们return未找到
如果位置已满，我们将线性移动到位置，直到遇到我们要查找的值，或者遇到空位置（意味着未找到）

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

Answer 1

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

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

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

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

有关这方面的更多信息，请查看 these lecture slides on linear probing and Robin Hood hashing。

希望对您有所帮助！

Answer 2

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

        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"

现在，再次搜索时会发生什么，这个位置不是 None，搜索将继续。请参阅下面的代码片段，了解如何在线性探头中实现搜索

    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 code explaining deletion in linear probing without breaking lookups.

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

How does linear probing handle deletions without breaking lookups?

hashtable

data-structures

linear-probing