我正在阅读有关双重哈希以及如何将其与哈希表的开放寻址方案一起使用的信息。我理解开放寻址中的哈希函数 h(k) 需要为给定键 k 生成探测序列的要求，使得探测序列是集合 <0, 1, ..., m-1> 的某种排列对于 m 个桶。线性探测通过使用函数增加探测计数来简单地做到这一点
h(k,i) = (h1(k) + i) mod m
双散列使用函数
h(k,i) = (h1(k) + i*h2(k)) mod m
因此探测以 i*h2(k) 的增量进行。
双重散列的建议是选择“m”作为 2 的幂，并始终从 h2(k) 返回一个奇数，以便这两个数字是互质的。这如何保证探测序列是集合 <0, 1, ..., m-1> 的排列？
当且仅当 h2(k) 和 m 互质时，探针序列到达所有位置。要看到这一点，请求解方程
a + i * b = c (mod m)
为我：
i = (c - a) * inv(b) (mod m)
b 只有与 m 互质时才有逆。
实现这一目标的两个简单策略是
回答第二部分
在双重散列中，让散列函数为 h(k, i)，其中 k 是键，i 是探测序列。
让 h(k, i) = h(k, j) 对于一些 i 和 j，其中 j > i。这意味着从第 i 步开始，经过 (ji) 更多步后，哈希函数指向同一个槽。设 m 为表的大小。另外，h 1 (k) 和h 2 (k) 是普通的散列函数。
h(k, i) = h(k, j)
(h 1 (k) + i * h 2 (k)) mod m = (h 1 (k) + j * h 2 (k)) mod m
(i * h 2 (k)) mod m = (j * h 2 (k)) mod m
((j - i) * h 2 (k)) mod m = 0
由于 h 2 (k) 和 m 互质，因此 (j - i) 必须是倍数或至少是 m。因此，散列函数要重复时隙，步数必须至少为 m。
这证明了保持 h 2 (k) 和 m 相对素数，双散列会命中大小为 m 的表中的所有槽，从而产生 m 的所有排列。
因为奇数和 2 的幂是互质的。使用 m = 2 r和 h 2 (k) 只产生奇数有效。