我正在阅读有关双重哈希以及它如何与哈希表的开放寻址方案一起使用的内容。我理解开放寻址中的哈希函数 h(k) 需要为给定 key 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 互质时，b 才具有逆。
实现这一目标的两个简单策略是
- 选择m作为素数，让h2(k)返回[1,m-1]中的值
- 选择m为2的幂，让h2(k)返回[1,m-1]中的奇数
关于algorithm - 双哈希如何工作？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25830215/