關於double hashing的計算問題?

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

問題題目:

http://imgur.com/8t4C6OD

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

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

D的解法是線性探測(LINEAR PROBING)吧?

1 個解答

評分
  • 4 年前
    最佳解答

    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.

    簡單無比!

還有問題?馬上發問,尋求解答。