如果雙散列函數也失敗，我應該怎麼做

Question

考慮將鍵10,22,31,9,15,28,62,88插入到長度爲m = 11的 散列表中，使用開放尋址哈希 函數h(k) = k mod m。舉例說明使用h2（k）= 1 +（k mod（m-1））進行雙重散列插入這些密鑰的結果。

以下是我的做法。

0 -> 22 , Since 22 mod 11 = 0 
1 -> 
2 -> 
3 -> 
4 -> 
5 -> 
6 -> 
7 -> 
8 -> 
9 -> 31 , Since 31 mod 11 = 9 
10 -> 10 , Since 10 mod 11 = 10 

好的問題來了，當試圖把鍵9放入哈希表。

h（9）= 9 mod 11，也就是9.自9以後我就不能放9。然後我嘗試給出h2（9）= 1 +（9 mod（11-1））的雙散列函數，它是10，它又一次消失了。所以我仍然不能把9放入哈希表。在這種情況下我該怎麼做。

Answer 1

最後，我可以用維基解釋找到答案。 http://en.wikipedia.org/wiki/Double_hashing

小時（9）= 9模11，其爲9

H2（9）= 1 +（9 MOD（11-1）），它是10

所以關鍵具有應（9 + 10）模11，其爲8

然後

8 - > 9

Answer 2

使用兩個散列函數是這樣的：

hi=(h(key)+i*h1(key))％m 0≤i≤m-1 

換句話說：你增量，每次第二哈希函數h1的價值，必要時纏繞。

所以地址列表，你會尋找一個主要內容如下：

h(key), h(key)+h1(key), h(key)+2*h1(key), ... , h(key)+n*h1(key)