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 索引。所以你不需要公因数。

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