探测哈希表

Question

我正在为一个项目实现一个哈希表，使用3种不同的探测。现在我正在做线性的工作。

对于线性探测，我了解探测的工作原理，我的教练暗示他希望步长为1。问题是，不允许重复。所以我必须在插入之前“搜索”一个值，对吧？但是，如果使用该表时，所有单元格要么被“占用”，要么被“删除”，该怎么办呢？然后，为了搜索特定的键以确保它不在表中，我必须搜索整个表。这意味着搜索操作(扩展为插入操作)是O(n)。

这看起来不太对劲，我想我误解了什么。

我知道使用二次探测不会遇到同样的问题，因为表需要至少有一半是空的，并且它只会探测确定数量的元素。对于双哈希，我不确定这是如何工作的，因为我还需要搜索表来证明要插入的键不存在。但是，如果没有一个单元格“从未被占用”，我如何知道如何停止搜索？

那么:在开放散列中，过去表中的每个条目都已被占用，那么是否需要O(n)个探测来搜索元素(如果不允许重复，则插入元素)？

Answer 1

如果你误解了线性探测的这一方面，我也是。我同意如果哈希表几乎满了，那么每次插入的性能就会下降到O(n)。有关所有细节，请参阅Don Knuth's 1963 analysis。

顺便说一句，我很惊讶地看到这个问题的第一个分析实际上是由数学家Ramanujan在1913年完成的，他的结果表明“对于满的线性探测哈希表，元素的总位移，即构建成本，大约是N^(3/2)。”(参见here)

然而，在实践中，我不认为插入速度慢的问题是几乎满的哈希表的重要问题。重要的问题是你已经到了根本不能再做插入的地步了！

因此，哈希表的任何实际实现都必须有一种策略，用于在哈希表超出给定的负载因子时重新调整其大小，并根据理论或实验选择用于重新调整大小的最佳负载因子。在这种情况下，使用实验特别有价值，因为线性散列的性能可能对散列函数以避免群集的方式在散列表上均匀分布项的能力非常敏感，这使得性能非常依赖于要插入到表中的项的特性。