哈希(没有重新哈希的双哈希)

Question

这就是问题所在:

通过双哈希和主哈希使用开放寻址函数为hi(x) = (hash(x) + f(i)) mod M，其中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感到困惑，因为它是双重碰撞....谁能解释一下怎么做，怎么回事?

Answer 1

冒着显示我无知的风险，i和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

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

等等，你可以看到它很快就偏离了

Answer 2

我对r_ahlskog的建议有疑问。难道我们不应该只在发生碰撞时才增加i吗?由于26最终发生碰撞，我们应该将i增加到0 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

当i=0时，

hi(x)为6，当i=1时，hi(x)为4。

如果我理解错了请纠正。

这是最终答案——

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

8号槽和9号槽是空闲的

42也发生了碰撞。