單獨的鏈接哈希表 - 何時停止查找

Question

有關哈希表的快速問題。 我目前正在實現一個散列表 使用分開的鏈接 和開放尋址的組合，限制每個桶的鏈表的長度 到一定的長度。

不過，我有麻煩的方式來有效地獲得/本哈希表結構中刪除 思考，並想知道如果我是盲目愚蠢 或是否有人接近前一個類似的問題。

如果我試圖不斷地使用衝突解決方案進行探測，那麼我可能會永遠發現並且永遠不會發現密鑰是否不在表中。這是因爲大多數探測方法不會覆蓋每個桶，我寧可不使用線性探測。

由於大多數探測方法不會覆蓋每個存儲桶，並且跟蹤所查看的存儲桶的開銷很大，因此如果存儲桶被清空但探測路徑中的後續存儲桶不存在，則該算法不能簡單地一旦遇到空桶就停下來。

我非常感謝在這個問題上的任何想法。

謝謝！

Answer 1

在這樣無限的碰撞的情況下，我們通常傾向於使用：

• 線性探測：有n每一次，其中n是一個素數> = 7，爲什麼黃金跳？使用素數的90％的可疑數據通常迭代表中的每個單元格，因此遍歷整個表格而不是繞每個單元格跳過。
• poly polling：每次有n次跳轉，其中n使用f（x）= x^2 + 2x + 1等多項式函數重新計算，爲什麼？這會在每個單元格上給出不同的結果，而不是完全基於單元格中的值。