开放寻址中的双重哈希，什么哈希函数和table长度
Double hashing in open addressing, what hash function and table length
在 Cormen 的书中 "Introduction to algorithms" 我读到双重散列（在开放寻址中）函数的形式为：
h(k, i) = (h1(k) + i * h2(k)) mod m
其中k是一个键，i是碰撞情况下的下一个索引，m 是 table 长度，hX 是散列函数。
他说双重哈希的主要问题是利用 table 中的所有索引。为了解决这个问题，我们应该将 m 设置为 2 的幂，并且 h2 函数应该 return 奇数。为什么（我看不到他在解释）？
一般规律是对m取模，重复添加h_2(k)就是一个以句点m/GCD(m, h_2(k))重复的循环。如果 m 和 h_2(k) 之间没有公因数，那么它将以句点 m 重复，这意味着您可以达到所有 m 指数。所以你不需要公因数。
通过使 m 为 2 的幂且 h_2(k) 为奇数，可以轻松满足 "no common factors" 规则。
在 Cormen 的书中 "Introduction to algorithms" 我读到双重散列（在开放寻址中）函数的形式为：
h(k, i) = (h1(k) + i * h2(k)) mod m
其中k是一个键，i是碰撞情况下的下一个索引，m 是 table 长度，hX 是散列函数。
他说双重哈希的主要问题是利用 table 中的所有索引。为了解决这个问题，我们应该将 m 设置为 2 的幂，并且 h2 函数应该 return 奇数。为什么（我看不到他在解释）？
一般规律是对m取模，重复添加h_2(k)就是一个以句点m/GCD(m, h_2(k))重复的循环。如果 m 和 h_2(k) 之间没有公因数，那么它将以句点 m 重复，这意味着您可以达到所有 m 指数。所以你不需要公因数。
通过使 m 为 2 的幂且 h_2(k) 为奇数，可以轻松满足 "no common factors" 规则。