algorithm - 开放寻址中的双重哈希，什么哈希函数和表长度

Question

在 Cormen 的“算法简介”一书中，我读到双散列（在开放寻址中）函数的形式为：

h(k, i) = (h1(k) + i * h2(k)) mod m

其中k是键，i是冲突情况下的下一个索引，m是表长度，hX是哈希函数。

他说双重哈希的主要问题是利用表中的所有索引。为了解决这个问题，我们应该将m设置为 2 的幂，并且h2函数应该返回奇数值。为什么（我看不到他解释）？

Answer 1

一般规则是模数m，h_2(k)重复加法是一个循环，重复周期m/GCD(m, h_2(k))。如果两者之间没有公因子m，h_2(k)那么它将以句点重复，m这意味着您可以到达所有m索引。所以你不想要公因数。

“无公因数”规则很容易通过2 和奇数m的幂来满足。h_2(k)