探測哈希表

Question

我正在實施一個項目的哈希表，使用3種不同的探測。現在我正在研究線性問題。

對於線性探測，我理解探測是如何工作的，而且我的導師暗示他希望步長是1.事情是，不允許重複。所以我必須在插入之前「搜索」一個值，對吧？但是如果表格被用於所有單元格被「佔用」或「刪除」的點？然後，爲了搜索特定的關鍵字以確保它不在表格中，我必須搜索整個表格。這意味着搜索操作（以及擴展，插入操作）是O（n）。

這看起來不正確，我想我誤解了一些東西。

我知道我不會遇到與二次探測相同的問題，因爲表需要至少有一半空，並且它只會探測確定數量的元素。而對於double哈希，我不知道這將如何工作，因爲我還需要搜索表以證明要插入的密鑰不存在。但是，如果沒有一個單元「沒有被佔用」，我怎麼知道如何停止搜索？

因此：在開放哈希中，表中的每個條目都被佔用，是否需要O（n）個探針來搜索元素（並插入，如果不允許重複）？

Answer 1

如果你誤解了線性探測的這個方面，我也是這樣。我同意如果散列表接近滿，那麼性能會降低到每插入O（n）。所有的細節見Don Knuth's 1963 analysis。另外，我很驚訝地看到，這個問題的第一個分析實際上是由數學家Ramanujan在1913年完成的，他的結果暗示「元素的總位移，即建設成本，對於線性探測哈希算法充滿的桌子大概是N ^（3/2）。「 （見here）

然而，在實踐中，我認爲插入速度慢的問題是幾乎全散列表的重要問題。重要的問題是你到了無法再插入的地步！因此，散列表的任何實際實現都必須有一個策略，當散列表超出給定的加載因子時，重新確定散列表的大小，並根據理論或實驗選擇最佳的重新定義大小的加載因子。在這種情況下使用實驗特別有價值，因爲線性散列的性能可能對散列函數以避免羣集均勻分佈項目的能力非常敏感，這使得性能非常依賴於項目被插入到表格中。