是否在哈希表中搜索不存在的值O(n)？(线性探测)

Question

我只是想理解线性探测逻辑。

在使用开放寻址的as哈希表中，如何确认元素不在表中。

例如，假设您有一个10个桶的hashmap。假设您散列了一个键，并将其插入。现在，如果要插入元素A和B，并将元素A和B散列和还原到相同的存储桶中，则元素A和B如果使用线性探针，则很可能彼此相邻。

现在，仅仅因为存储桶是空的，似乎并不意味着映射中不存在元素。例如，在第一次删除元素A之后，您可以搜索元素B。首先，你得到一个空桶，你期望B在那里，但你需要再探测一个，你会发现B。它真的在那里。如果逻辑正确，那么您不需要搜索整个表来确认键是否不在那里吗？即每次O(n)性能。

我的意思是，你不需要检查整个地图才能真正确认它不在那里吗？

使用单独的hashmap链接方法，这个问题就不存在了。

例如：

​

如果约翰·史密斯被删除，我们试图找到桑德拉·迪。

或者使用线性寻址，您需要移动元素，这样就不会出现空洞。例如，如果John Smith被删除，那么从152到154的元素是否应该移回一个位置？它在描述中并没有真正看到这一点，但这可能有一定的意义。除非泰德·贝克的哈希值是154而不是153。需要比我想象的多一点的工作。

可能只需要在每个存储桶中使用一个简单的链表。

Answer 1

在绝对最坏的情况下，是的，确定某个项目是否在表中的算法是O(n)。然而，这永远不会发生在一个管理得当的哈希表中。

当一个项目被移除时，一个墓碑应该被放置在它被移除的表槽中。墓碑只是一些数据，表明曾经有一个元素在那里，但它已经被删除。通过这种方式，每次搜索元素时，都必须遵循所使用的探测序列，直到找到一个空的插槽。如果一个槽是空的，那么您已经完成了该哈希值的探测序列，并且知道它不会在表中的任何其他位置。

您必须搜索探测序列中的每个槽的唯一方法是，如果探测序列中没有空槽。由于您应该始终将哈希表设置为大约一半为空，因此这种情况不应该发生。

Answer 2

通过探测策略解决冲突的哈希表的使用对数据结构的删除能力提出了严格的要求。当您删除一个项目时，您必须补偿哈希表，以便它仍然满足搜索所需的要求(这是哈希表的要点)。

使用线性探测，如果您删除了一个项目，您将移动到下一个插槽。如果它与我们刚刚删除的槽的散列匹配，则移动它。冲洗并重复，直到您到达一个空的插槽。还有惰性删除策略，将项目标记为删除，然后在下一次搜索时实际删除/补偿。

假设有三个项目{A0，A1，A2}具有相同的哈希值。让{A0，A1}在哈希表中，{A2}不在哈希表中。如果我们删除A0，我们将其标记为删除。当我们搜索A2 (不在哈希表中)时，我们发现A0 (已删除)，然后我们移动到A1，我们将其重新定位到A0的插槽中，完成删除。我们移动到下一个位置(可能是A2，或者是A1刚刚占用的位置的候选位置)，但是发现它是空的，所以我们清空了A1刚刚腾出的位置，我们的哈希表回到了原始状态。

Answer 3

我认为这是晚了，但有提到探测序列和哈希表的最大探测序列。

每次你插入一个元素，你都会记录下你过去已经做过的探测的最大数量，并且是不是'maxProb‘小于你插入当前元素时做的探测的数量。

最终，当您在哈希表中搜索一个元素时，您将只执行最多的maxProb搜索。

现在考虑到您不允许无限或N个探测，其中N是哈希表的容量，运行时间将是O(x)，其中x是最坏情况下允许的最大探测。

假设您的散列键生成算法迫使您多次探测，那么您可以这样实现数据结构，即如果插入需要x个探测器，则它应该考虑重新对自身进行散列。