computer-science - 二次探测

Question

在用于解决哈希冲突的二次探测方法中，H(k) =h(k) + c1*i^2 + c2*i。

我需要一些帮助来确定如何确定 c1 和 c2 的值，即如何确保访问哈希表的所有插槽。

Answer 1

令 ht_size = 哈希表槽数。我假设你的意思是

h(k) + c1*i^2 + c2*i % ht_size

c1=0 和 c2=1 将起作用；）

c1=0 和 c2 与 ht_size 互素也有效。1 是任意数的互质数。如果 ht_size 不是偶然的相同素数，素数也是很好的候选。

为什么这样的设置会访问所有插槽？如果 c1=0 且 c2 与 ht_size 互质，则 ggt(c2, ht_size) == 1。换句话说，在群（代数群论）中，c2 是一个生成器。这意味着c2**i将生成从 0 到 ht_size - 1 的所有数字。**我的意思是幂运算符，即应用组的运算符 i 次。群的算子是+，因此c2**i在群论记法中对应于c2*i在正规记法中。

我希望这能让您了解如何开始搜索 c1 和 c2 的组合，其中 c1 != 0。