探测哈希表

Question

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

对于线性探测，我理解探测是如何工作的，而且我的导师暗示他希望步长是1.事情是，不允许重复。所以我必须在插入之前“搜索”一个值，对吧？但是如果表格被用于所有单元格被“占用”或“删除”的点？然后，为了搜索特定的关键字以确保它不在表格中，我必须搜索整个表格。这意味着搜索操作（以及扩展，插入操作）是O（n）。

这看起来不正确，我想我误解了一些东西。

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

因此：在开放哈希中，表中的每个条目都被占用，是否需要O（n）个探针来搜索元素（并插入，如果不允许重复）？

Answer 1

如果你误解了线性探测的这个方面，我也是这样。我同意如果散列表接近满，那么性能会降低到每插入O（n）。所有的细节见Don Knuth's 1963 analysis。另外，我很惊讶地看到，这个问题的第一个分析实际上是由数学家Ramanujan在1913年完成的，他的结果暗示“元素的总位移，即建设成本，对于线性探测哈希算法充满的桌子大概是N ^（3/2）。“ （见here）

然而，在实践中，我认为插入速度慢的问题是几乎全散列表的重要问题。重要的问题是你到了无法再插入的地步！因此，散列表的任何实际实现都必须有一个策略，当散列表超出给定的加载因子时，重新确定散列表的大小，并根据理论或实验选择最佳的重新定义大小的加载因子。在这种情况下使用实验特别有价值，因为线性散列的性能可能对散列函数以避免群集均匀分布项目的能力非常敏感，这使得性能非常依赖于项目被插入到表格中。