在哈希表中搜索一个不存在的值是否为O(n)?（线性探测）

Question

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

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

例如，假设您有一个10个桶的哈希映射。假设您散列密钥并插入它。现在，如果要插入元素A和B，并且哈希和缩小到相同的桶，则使用线性探测，元素A和B可能会彼此相邻。

现在，仅因为桶为空，并不意味着地图中不存在元素。例如，您在首先删除元素A后搜索元素B。首先，您会得到一个空桶，您期望B在其中，但您需要再探测一次，然后您会找到B。它确实存在。如果该逻辑正确，则每次都必须搜索整个表以确认关键字是否不存在吗？即每次O(n)性能。

我的意思是，难道您不需要浏览整张地图才能真正确认它不存在吗？

对于哈希映射的分离链接方法，这个问题不存在。

例如：

如果删除了John Smith，并且我们尝试找到Sandra Dee。

或者，使用线性寻址，您是否应该移动元素，以便没有这样的空洞。即，如果删除了John Smith，是否应将152到154的元素向后移动一个位置？我在描述中并没有真正看到它，但那可能有些道理。除非Ted Baker的哈希值为154而不是153。需要比我想象的更多的工作。

可能只需在每个桶中使用简单的链接列表。

- hookenz

---

发现了一份关于哈希表的绝佳教程。http://research.cs.vt.edu/AVresearch/hashing/ - hookenz

如果您想高效地测试一个值是否不在表中，可以看一下布隆过滤器：https://en.wikipedia.org/wiki/Bloom_filter - Alex Reynolds

Answer 1

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

当一个项目被移除时，应该在它被移除的表格插槽上放置一个墓碑。墓碑只是一些数据，用于指示曾经有一个元素在那里，但已被移除。通过这种方式，每次搜索元素时，必须按照使用的任何探测序列进行探测，直到找到一个空插槽。如果插槽为空，则已完成该哈希值的探测序列，并且知道它不会出现在表中的其他位置。

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

- Deddryk

Answer 2

使用探测策略解决冲突的哈希表对数据结构的删除功能提出了严格要求。当你删除一个项目时，必须使哈希表进行补偿，以便它仍然满足搜索所需的要求（这是哈希表的主要目的）。

使用线性探测，如果你删除一个项目，你会移动到下一个插槽。如果它与我们刚刚删除的插槽的哈希匹配，则将其移动。反复此过程，直到找到一个空插槽。还有一些惰性删除策略，其中项目被标记为删除，然后在下一次搜索时实际删除/补偿。

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

- Ethan Cabiac

---

我的意思是，如果您在桶实现中使用数组，并且该桶本身将键/值保持为开放式寻址，则会发生这种情况。 - hookenz

@Matt - 明白了。通过使用“桶”这个术语，我假设你正在使用支持冲突的哈希表。我看到你正在使用一种非冲突哈希表，并采用探测法来解决冲突。 - Ethan Cabiac

谢谢，我相信你是对的。这个问题的两个答案都是正确的。在我的情况下，我喜欢墓碑方法。 - hookenz

@EthanCabiac 感谢您的解释。我一直在寻找这个答案，并为此提供了悬赏。如果您能够回答我的问题并提供更详细的信息，我将接受它并向您奖励悬赏。请在此处查找问题链接。http://stackoverflow.com/questions/10855989/what-is-the-cost-of-deleting-a-value-from-a-hashtable - dharam

Answer 3

我觉得这可能有点晚了，但是在哈希表中有提到探测序列和最大探测序列。

每次插入一个元素时，你都要跟踪过去的最大探测次数，并且判断'maxProb'是否小于插入当前元素所需的探测次数。

最终，当你在哈希表中查找元素时，你只会执行最多maxProb次搜索。

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

假设你的哈希键生成算法强制你进行多次探测，那么你可以以这样的方式实现数据结构，如果插入需要x次探测，则应该考虑重新哈希。

- dharam