關於double hashing的計算問題?

Question

所謂的double hashing法：就是當碰撞發生，使用第二個預先設定的雜湊函數來進行位置的取得

問題題目：

http://imgur.com/8t4C6OD

為何這題答案是D，不是B?

69發生碰撞，使用hash(2)

D的解法是線性探測（LINEAR PROBING）吧?

Answer 1

最佳解答

D 是對的. 錯誤的是 <你對double hashing的誤解>

所謂的double hashing法：就是當碰撞發生，使用第二個預先設定的雜湊函數來進行位置的取得 (X)

<double hashing> 會產生 無限量數的 值 (可能重複)

k[i, v] where i=0...<無限大> and

k[i, v] = (h0(v) + i * h1(v)) % size_of_the_hash_table

當h1()退化成常數 1的時候 <doublr hashing>就退化成<LINEAR PROBING>

照我說的來計算 你會發現 D是對的

> 69碰撞,(69*3)/7 =4

k[i,69] 所產生的值是: 3, 9, 4, 10, 5, ...

因為 3 9 都已經被佔用了 故用 4.

簡單無比!

> 那64碰撞要如何解? 再除以7，怎麼都不會到10這個位置

k[i,64] 所產生的值是:9 10 0 1 2 3 ....

因為 9 都已經被佔用了 故用 10.

簡單無比!