c++ - 散列(没有重新散列的双重散列)

Question

问题是:

通过双重散列和主散列使用开放寻址函数是 hi(x) = (hash(x) + f(i)) mod M，其中 hash(x) = x mod M 和 f(一)=
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 like 会使位置取决于插入顺序。

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

有人可以改进我的胡乱猜测吗？

---

好的，那我们展开这个。

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

依此类推，正如您所见，它与您所拥有的差异很快