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

Question

只是想了解线性探测逻辑。

对于使用开放寻址的哈希表，您如何才能确认某个元素不在表中。

例如，假设您有一个 10 桶 HashMap 。 假设您散列一个 key ，然后将其插入。现在，如果要插入元素 A 和 B，并散列和归约到同一个桶，那么如果使用线性探针，元素 A 和 B 可能会彼此相邻。

现在，仅仅因为桶是空的，似乎并不意味着 map 中不存在某个元素。例如在元素 A 第一次被删除后搜索元素 B。首先，您在预期 B 所在的位置得到一个空桶，但您需要再探测一个桶，然后您会找到 B。它确实存在。如果该逻辑是正确的，那么您是否不必搜索整个表以确认是否有键不存在？即每次 O(n) 性能。

我的意思是，你不需要遍历整个 map 才能真正确认它不存在吗？

对于 hashmap 的单独链接方法不存在该问题。

例如:

如果 John Smith 被删除，我们会尝试找到 Sandra Dee。

或者对于线性寻址，您是要四处移动元素，这样就没有空洞了。即，如果删除 John Smith，是否应该将 152 到 154 中的元素移回一位？它在描述中并没有真正看到这一点，但这可能有些道理。除非 ted baker 按照描述散列为 154 而不是 153。需要比我想象的更多的工作。

可能只是在每个桶中使用一个简单的链表。

Answer 1

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

当一个元素被移除时，一个墓碑应该被放置在它被移除的 table 位置。墓碑只是一些数据，表明那里曾经有一个元素，但它已被删除。这样，每次搜索元素时，您都必须按照所使用的任何探测序列进行搜索，直到找到一个空槽。如果槽为空，则您已完成该哈希值的探测序列，并且知道它不会位于表中的任何其他位置。

您必须搜索探测序列中的每个插槽的唯一方法是探测序列中是否没有空插槽。由于您应该始终以哈希表的一半为空为目标，因此不应发生这种情况。