有没有办法调整整数溢出？

Question

我正在研究一个 anagram 哈希函数，已经解决了几种不同的方法，但我正在寻找极限性能作为练习。我已经提交了一个解决方案，该解决方案通过了所有给定的测试（以至少 1 毫秒的优势击败了 100% 的所有竞争对手），但我相信尽管它“获胜”，但它有一个没有被触发的弱点。它会以可能影响结果的方式出现整数溢出。

解决方案的要点是组合多个交换操作，每个操作都占用一定数量的位，并将它们连接成一个长变量。我选择了 xor、sum 和 product。 xor 运算完全适合固定数量的位数。求和运算可能会溢出，但是由于溢出的处理方式，如果重新排列字母及其对应的值，它仍然会得到相同的结果。例如，我不会担心这个函数是否会溢出。

private short sumHash(String s) {
    short hash=0;
    for (char c:s.toCharArray()) {
        hash+=c;
    }
    return hash;
}

我运行遇到麻烦的地方在于产品的收录。如果我创建一个 returns 值列表的乘积（例如字符串中的字符值）的函数，那么，至少，如果乘积溢出到恰好为零，结果可能会变得不准确。

private short productHash(String s) {
    short hash=1;
    for (char c:s.toCharArray()) {
        hash*=c;
    }
    return hash;
}

是否有任何安全且高效的方法来避免此弱点，以便函数获得乘法交换属性的好处，为字谜产生相同的值，但永远不会遇到这样的乘积溢出到零？

Answer 1

避免溢出的简单方法是使用更大的类型，例如 int 或 long。但是，出于您的目的，模运算可能更有意义。您可以对质数 p 执行 (a * b) % p 以保持交换性。（这里有一些深奥的数学，叫做群论，如果你有兴趣了解更多的话。）你需要限制 p 足够小，每个 a * b 都不会溢出。最简单的方法是选择 p，这样 (p - 1)^2 仍然可以用 short 或您使用的任何数据类型表示。

Answer 2

当然可以，如果您愿意竭尽全力去做的话。我想到的最简单的解决方案是写

hash *= primes[c];

其中 primes 是一个数组，它将每个可能的字符映射到一个不同的奇素数。只有当 infinite-precision 算术中的“真实”乘积是 2^32 的倍数时才会溢出为零，如果乘以奇素数，那是不可能的。

（你运行解决了哈希本身总是奇数的问题，但你可以将它右移一位以获得更完全混合的哈希。）

Answer 3

如果

你只会打零

a * b = 0 mod 2^64

相当于存在一个整数 k 使得

a * b = k * 2^64

也就是说，如果因子除以 2^64，即如果因子是偶数，我们就会遇到麻烦。因此，最简单的解决方案是确保所有因素都是奇数，例如这样：

for (char ch : chars) {
  hash *= (ch << 1) | 1;
}

这允许您保留 63 位信息。

但是请注意，此技术只会避免溢出引起的冲突，而不会避免共享公因数的乘法器引起的冲突。如果你也想避免这种情况，你将需要互质乘数，如果它们是质数，这是最容易实现的。

有没有办法调整整数溢出？

Is there a way to adjust for integer overflow?

java

integer-overflow