双哈希中第二哈希函数使用合数的最优选择问题

嘿，这个问题抓得很准！咱们先回到双哈希的核心目标——当出现哈希冲突时，探测序列必须能遍历整个数组，不能陷入局部循环，这才是“最佳哈希扩散性”的本质。你的初步思路有一定道理，但核心判断标准可以更精准，咱们一步步拆解：

核心判断标准：h2与m的最大公约数（gcd） #

双哈希的探测序列公式是：(h1(k) + i*h2(k)) mod m（i为探测次数）。要让这个序列覆盖所有m个数组位置，必须满足h2与m的最大公约数gcd(h2, m) = 1。原因很简单：如果gcd(h2, m) = d > 1，那么探测序列的周期就是m/d，也就是说，你最多只能遍历数组的1/d部分，剩下的位置永远碰不到，扩散性直接拉胯。

针对m=20的选项分析 #

m=20的质因数是2和5，咱们逐个看选项：

• 6：gcd(6,20)=2 → 周期=20/2=10，只能遍历一半位置，排除
• 9：gcd(9,20)=1 → 周期=20，能遍历所有位置，完美符合要求
• 12：gcd(12,20)=4 → 周期=5，只能遍历1/4的位置，排除
• 15：gcd(15,20)=5 → 周期=4，只能遍历1/5的位置，排除

对你思路的复盘 #

你关注因数数量的方向是对的，但抓错了核心：不是因数越少越好，而是h2不能包含m的任何质因数。比如9的因数是3，和20的质因数（2、5）完全不重叠，所以互质；而15的因数包含5，和20共享质因数，导致gcd>1，直接锁死了探测范围。至于“接近数组大小”这个点，只有在h2满足互质条件的前提下才有意义，否则毫无价值。

补充：合数作为h2的通用选择逻辑 #

当必须用合数作为第二哈希参数时，记住这个规则：

• 先分解数组大小m的所有质因数
• 选择的合数h2不能包含这些质因数中的任何一个（即h2与m互质）
• 如果有多个符合条件的选项，再优先选较大的数（能减少探测次数的平均长度）

在你的问题里，只有9符合互质要求，所以它是唯一的最优解。

内容的提问来源于stack exchange，提问作者Immanuel