哈希函数h(S)=((sum(S[i]*x**i))mod p)mod m的问题与降碰撞方法

原哈希函数的核心问题 #

你提到的哈希函数 h(S) = ((sum(S[i]*x**i)) mod p) mod m 属于多项式哈希的一类实现，但碰撞风险主要来自两个层面：

1. 当两个字符串的多项式加权和满足 sum((S[i]-T[i])*x^i) ≡ 0 mod p 时，它们经过mod p后的结果完全相同，后续再mod m必然碰撞。
2. 两次取模的操作如果配合不当（比如m和p不互质），会进一步压缩哈希值的分布空间，变相提升碰撞概率。

降低碰撞概率的具体方案 #

• 使用双哈希（或多哈希）：同时用两组完全独立的(x,p,m)参数计算两个哈希值，将它们组合成一个二元组作为最终哈希。只有当两组参数同时发生碰撞时，整体才会碰撞，概率会指数级降低。比如常用组合是(31, 1e9+7)和(127, 1e9+9)。
• 优化p的选择：优先选用接近2^32或264的大质数（如1e9+7、1e9+9，甚至1e18级别的质数）。如果用64位无符号整数计算，还可以利用自然溢出代替显式mod p——64位无符号整数溢出等价于mod 2^64，虽然2^64不是质数，但实际碰撞概率极低，且计算效率更高。
• 调整哈希表容量m：尽量选择质数作为m，且保证m与p互质。这样mod p后的结果再mod m时，哈希值的分布会更均匀，减少因分布不均导致的碰撞。
• 加入长度因子：将字符串的长度作为哈希的一部分（比如最终哈希为(h_p * s + s) mod m，其中h_p是mod p后的结果，s是字符串长度），避免不同长度的字符串因加权和巧合相等而碰撞。

x与p是否需要互质？ #

是的，必须互质。如果x和p存在大于1的公因数d，那么x在模p下的乘法逆元不存在，且会导致哈希函数的区分度大幅下降：比如两个字符串的字符差值都是d的倍数时，它们的加权和差值会被d整除，更容易满足≡0 mod p的条件，进而引发碰撞。通常选x为小质数（如31、127），这类数和大质数p自然互质，无需额外验证。

原函数易碰撞的字符串组示例 #

原函数对满足多项式加权和同余的字符串组会产生相同哈希值：

• 同长度字符串：比如x=2，p=5时，字符串[1,0]（计算得12^1 + 02^{0=2）和`[0,2]`（0*2}1 +2*2^0=2），mod p后结果相同，必然碰撞。
• 不同长度字符串：比如x=3，p=7时，单字符串[2]（23^{0=2）和双字符串`[0,2]`（0*3}1 +23^0=2），mod p后结果一致，也会碰撞。

函数修改建议 #

• 改用Horner法则计算多项式哈希：虽然你提到问题不是溢出，但Horner法则能避免大指数直接计算，同时提升效率，公式为：h = ((...((S[0]*x + S[1])*x + S[2])*x + ... ) + S[s-1]) mod p
• 调整索引顺序：原函数的i从1到s-1，建议统一为从0到s-1（或逆序），这样更符合常规多项式哈希的实现逻辑，减少不必要的混淆。

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