如何实现同和整数序列返回相同哈希且避免溢出的哈希函数

核心需求明确 #

你需要的是和等价哈希：只要整数序列的总和相等，哈希返回值必须完全相等，同时避免直接求和导致的数值溢出问题。该需求的核心数学性质要求哈希计算满足 h(a + b) ≡ h(a) + h(b) mod M，其中M为选定的大素数，只有满足该同余性质，才能保证不管序列元素怎么拆分、顺序怎么调整，总和相同则哈希值相同。

第一个修改版本的未考虑边界 #

• 负数适配问题：若序列包含负整数，未处理负取模逻辑的话，会直接出现总和相同但哈希值不同的问题。比如序列[-1, 3]和[2]总和均为2，若-1对BIG_PRIME取模得到BIG_PRIME - 1，累加3后的模运算结果和2的模运算结果完全不同，直接不符合需求。
• 累加溢出漏判：仅判断单个h或value超过阈值就取模，会漏掉两个值均略低于阈值、累加后刚好超过Number.MAX_SAFE_INTEGER的场景，此时会出现浮点数精度丢失，导致哈希计算错误。
• 低差碰撞无法避免：只要两个序列的总和差值为BIG_PRIME的整数倍，必然会发生碰撞，小值短序列的碰撞概率极高。

第二个修改版本的未考虑边界 #

该版本的逻辑缺陷比第一个版本更严重，直接破坏了同余性质：

• 必然出现累加溢出：仅当h和value同时超过阈值才取模，两个均略低于阈值的数值累加后会直接超过安全整数范围，发生精度丢失。
• 核心需求不满足：总和相同的序列会得到不同哈希值。比如BIG_PRIME + 2作为单元素序列时，value超过阈值会被取模得到2；而拆分为[BIG_PRIME + 1, 1]时，第一次累加h初始为0（低于阈值），仅value超过阈值不会触发取模，累加后得到BIG_PRIME + 1，再加1得到BIG_PRIME + 2，最终哈希值和单元素序列的2完全不同，直接违背了和等价的要求。
• 累计溢出问题：连续累加多个略低于阈值的数值，累计值超过安全整数后会发生精度丢失，后续所有计算结果全部错误。
• 同样未处理负整数的取模适配问题。

方案合理性评估 #

两个修改版本均不合理。二者都破坏了哈希计算需要满足的加法同余性质，连「总和相同则哈希值相同」的最基本功能要求都无法满足，所谓的降低碰撞概率的优化完全是南辕北辙。

正确方案的核心逻辑 #

@derpirscher的实现之所以正确，核心是严格遵循了加法同余规则：每次累加后统一对大素数取模，同时适配了负整数的取模逻辑，保证哈希结果永远等于序列总和模大素数的结果，既不会出现溢出问题，也完全满足和等价的要求。选用接近1e12的大素数999999999989时，随机碰撞概率仅为1/1e12，绝大多数业务场景下都可以忽略碰撞风险。

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