algorithm - 探测哈希表

Question

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

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

这似乎不对，我想我误解了什么。

我知道我不会遇到与二次探测相同的问题，因为表格需要至少有一半是空的，而且它只会探测确定数量的元素。对于双重散列，我不确定这将如何工作，因为我还需要搜索表以证明要插入的 key 不存在。但是，如果没有一个单元格“从未被占用”，我怎么知道如何停止搜索呢？

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

Answer 1

如果您误解了线性探测的这一方面，我也是。我同意，如果哈希表接近满，则每次插入的性能会下降到 O(n)。参见 Don Knuth's 1963 analysis所有的细节。

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

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

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