二次探測哈希表的限制

Question

我正在做一個程序來比較哈希表中線性探測，二次探測和單獨鏈接所需的平均和最大訪問。

我已經做了3例的元素插入部分。從哈希表中查找元素時，我需要限制搜索結束。 在單獨鏈接的情況下，當下一個指針爲空時，我可以停止。 對於線性探測，當探測整個表格（即表格的大小）時，我可以停下來。 我應該用什麼作爲二次探測的極限？桌子的大小會怎樣？

我二次探測功能是這樣

newKey = (key + i*i) % size; 

其中i從0到無窮大。請幫我..

Answer 1

對於這樣的問題分析i生長在兩塊：

第一區間：i去從0到size-1

在這種情況下，我沒有得到的解決方案現在。希望會更新。

秒間隔：i去從size到infinity

在這種情況下i可以表示爲i = size + k，然後

newKey = (key + i*i) % size 
     = (key + (size+k)*(size+k)) % size 
     = (key + size*size + 2*k*size + k*k) % size 
     = (key + k*k) % size 

所以它肯定，我們將開始探索先前探測細胞，之後i河段到size。所以你只需要考慮i從0到size-1的情況。因爲休息一次又一次只是同一個故事。

What the story tells up to now:一個簡單的分析表明我最多需要探測size次，因爲超過size次我開始探測相同的單元。

Answer 2

請參閱this link。如果你的表格大小是2的冪，並且你正在使用一個反函數函數f（i）= i *（i + 1）/ 2，那麼你可以保證遍歷整個表格。如果你的桌子尺寸是一個素數，你肯定會遍歷至少一半的桌子。一般來說，你可以檢查一下你是否回到了原點。如果發生這種情況，你需要重新哈希。