3

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

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

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

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

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

4

2 回答 2

3

好问题！你是绝对正确的，只是从线性探测表中删除一个项目会在你报告的情况下导致问题。

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

为了保持较低的墓碑数量，您可以使用一些不错的技术，例如在插入期间覆盖墓碑或在墓碑数量变得过多时全局重建表。

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

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

希望这可以帮助！

于 2020-03-11T21:24:05.280 回答
1

线性探测（开放寻址）中的删除是这样完成的，即为删除值的索引分配任何标记，例如“删除”。[可以在该索引处键入除 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 代码，解释线性探测中的删除而不中断查找。

于 2022-02-18T13:25:45.127 回答