1

これは質問です：

ダブル ハッシュによるオープン アドレスを使用し、主なハッシュ関数はhi(x) = (hash(x) + f(i)) mod M、 where hash(x) = x mod M、f(i) = i ∗ hash2(x)およびhash2(x) = 13 − (x mod 7)です。

キー 27、22、16、26、47、12、42、3 を (この順序で) 挿入する必要があります。セットのサイズは10個

This is what i have so far:
0 []
1 []
2 [22]
3 []
4 []
5 []
6 [16]
7 [27]
8 []
9 []

26 の挿入は二重衝突であるため、混乱しています....その方法と何が起こっているのか、誰か説明できますか?

4

2 に答える 2

1

r_ahlskog の提案には疑問があります。衝突が発生した場合にのみ i をインクリメントするべきではありませんか。26 は衝突してしまうため、i t0 を 1 増やす必要があり、この時点で 26 はスロット m=4 に解決されます。

    M = 10 (no. of slots)   
    hi(x) = (hash(x) + f(i)) mod M   (6+0) mod 10 = 14 mod 10 = 6
                                    (6+8) mod 10 = 14 mod 10 = 4
    hash(x) = x mod M                      26 mod 10 = 6

    f(i) = i ∗ hash2(x)           (i=0)  0 * 8 = 0
                                          (i=1) 1 * 8 = 8

    hash2(x) = 13 − (x mod 7)             13 - (26 mod 7) = 13-5=8

hi(x) は、i=0 の場合は 6、i=1 の場合は 4 になります。

私の理解が間違っている場合は修正してください。

これが最終的な答えです -

[0]=12;
[1]=42;
[2]=22;
[3]=3;
[4]=26;
[5]=47;
[6]=16;
[7]=27;

スロット 8 と 9 は空きです。

衝突は 42 にも発生しました。これは i=3 で解決されました。

于 2012-10-19T04:46:18.977 に答える
1

私の無知を示​​す危険を冒して、i と M はどのように定義されますか? M はサイズに等しいと推測し、i は挿入数のカウンターであると推測しましたが、それは出力に加算されません。ただし、私の実装は 26 ではなく 42 で衝突します。つまり、衝突する前にキースペースの半分以上を使用しました。

しかし、i like を指定すると、位置が挿入順序に依存することに気付きました。

その時点で私はすでに回答していましたが、パニックになって削除しました。インターネット上で愚かに見えることはありません。インターネットは決して忘れません。しかし、ハッシュについて間違った考えを持っていたのではないかと考え始めました。数値は個別の単位ではなく、全体としてハッシュされたものの一部であり、順序の依存関係は正しいのかもしれません。

誰かが私のワイルドな当て推量を改善できますか?

では、これを展開しましょう。

hash(x) = x % M
hash2(x) = 13 - (x % 7)
f(i) = i * hash2(x)
hi(x) = (hash(x) + f(i)) % M

for: i=0、M=10、x=27

hash(x) = 27 % 10 -> 7
hash2(x) = 13 - (27 mod 7) -> 7
f(i) = 0 * 7 - > 0
hi(x) = (7 + 0) % 10 -> 7

for: i=1、M=10、x=22

hash(x) = 22 % 10 -> 2
hash2(x) = 13 - (22 mod 7) -> 12
f(i) = 1 * 12 - > 12
hi(x) = (12 + 12) % 10 -> 4

for: i=2、M=10、x=16

hash(x) = 16 % 10 -> 6
hash2(x) = 13 - (16 mod 7) -> 11
f(i) = 2 * 11 - > 22
hi(x) = (6 + 22) % 10 -> 8

ご覧のとおり、それはあなたが持っていたものから非常に急速に発散します

于 2011-11-16T09:11:03.443 に答える