1

这是问题：

通过双重哈希使用开放寻址，主要的哈希函数是, hi(x) = (hash(x) + f(i)) mod Mwherehash(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

冒着暴露我无知的风险，我和M是如何定义的？我猜 M 等于 size 并且猜想 i 是插入次数的计数器，但这不会加到您的输出中。然而，我的实现不会在 26 上发生冲突，而是在 42 上发生冲突，这意味着它在发生冲突之前使用了一半以上的键空间。

但后来我意识到像这样指定 i 会使位置取决于插入顺序。

那个时候我已经回答了，但是慌了把它删了，不能在网上看傻，网上永远不会忘记。但后来我开始想，也许我对散列有错误的想法，也许数字不是单独的单位，而是作为一个整体散列的东西的一部分，然后顺序依赖是正确的。

有人可以改进我的疯狂猜测吗？

好的，让我们展开这个。

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

对于：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

对于：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

对于：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 回答
1

我对 r_ahlskog 的建议有疑问。我们不应该只在发生碰撞时才增加 i 吗？由于 26 最终发生冲突，我们应该将 i t0 增加 1，此时 26 被解析为 slot 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 回答