hash 溢位時用的 「double hashing」

溢位發生時使用double hashing方法,

如用了double hashing,假設g(x)=5+(x mod5),還是發生溢位的話,接下來要怎麼辦?

像是平方探測第一次是 1^2接下來 -(1^2)接下來2^2在來-(2^2)

一直算下去。

Update:

我說錯是 hashing發生碰撞才對。使用double hashing方法要怎麼排位置?

Update 2:

h1 = 第一個hash function 例如 g(x) = 5 + ( x mod 5)

h2 = 第二個hash function 例如 g(x) = 9 + ( x mod 7)

題目就用一樣的,可是我看我書上的解答是這樣的,

double hashing是需要兩個hash function,

把7放進去代入第一個hash function ,如果第一個有位置就不用帶入第二個,如發生碰撞就帶入第二個。

可是你寫兩個都帶又加起來,我覺得怪怪的。

還有那如果帶入第二個還是發生碰撞呢?(沒溢位)要帶哪個呀@@?

Update 3:

還有g(x) = 5 + ( x mod 5),代7進去,我書上的解答會寫2耶,

他沒加上5,就直接7 mod 5=2 由於書上只有一題範例

我也不知誰對誰錯@@?

1 Answer

Rating
  • 1 decade ago
    Favorite Answer

    double hashing需要兩個hash function.

    h1 = 第一個hash function 例如 g(x) = 5 + ( x mod 5)

    h2 = 第二個hash function 例如 g(x) = 9 + ( x mod 7)

    j = 第幾次找位置

    k = 鍵值

    m = hash table的大小

    h(j,k) = ( h1(k) + j * h2(k) ) mod m

    例子:

    假設有hash table的大小是10個位置

    要把7放進去,參考上面的h1及h2

    算出

    h1 = 5 + ( 7 mod 5 ) = 7

    h2 * j = (9 + ( 7 mod 7 ) ) * 1 = 9

    (9 + 7) mod 10 = 6

    所以放第6個位置

    此時再放7進去時,一定會碰撞,

    所以j要改成2,再算一下

    h1 = 5 + ( 7 mod 5 ) = 7

    h2 * j = (9 + (7 mod 7))*2 = 18

    (7+ 18) mod 10 = 5,此時放在第5個位置

    以上,應該清楚了吧

    2009-02-27 19:09:14 補充:

    一般的double hashing是必需要兩個hash function,但沒說兩個hash function不能一樣啊 =_=

    2009-02-27 19:09:26 補充:

    照你補充的發問來看,我認為是這樣的

    使用 g(x) = 5 + ( x mod 5)

    但你沒提到table的size到底是多少,因為double hashing的一般式是

    h(x,j) = ( h1(x) + j * h2(x) ) mod m

    如果你的hashtable size 是5的話,那麼答案是對的...

    因為最後需要再 mod 5 所以 5 + 2 mod 5 = 2

    2009-02-27 19:09:30 補充:

    我想課本應該h1 = h2 且 j一開始是零

    這樣如果碰撞了話,

    則j代一進去;

    此時答案就變成

    (( 5 + ( 7 mod 5) + 1 * ( 5 + ( 7 mod 5))) mod 5 = 4改放第4個位置

Still have questions? Get your answers by asking now.