algorithm - Hashcode计算为什么乘法忽略溢出位？

Question

这个问题不是关于为什么一个人会倍增，这是相当明显的 - 它是关于分配的。

Why use a prime number in hashCode?

但这更多地是关于乘法的一个属性，哈希码计算公式中包含的因素越多，该属性就变得越重要。

一个简单的计算显然可能会溢出，但这无关紧要。

a * 31 + b

真正的问题是当公式中有很多项时。

((a * 31) + b) * 31 ... 6n.

一旦包含超过 5 或 6 个术语，第一个术语的值将丢失，因为当哈希码值达到包含 5+ 个术语时，它的位已经溢出。使用这个系统，只有最后 5 个左右的术语对最终值有真正重要的贡献。

31 ^ 7 > Integer.MAX_VALUE

那么为什么大多数计算不回滚溢出的位并对结果的低位进行异或运算。我明白这需要一些小改动，并且必须使用 longs(64 位)进行计算，因此前 32 位可以与整数结果进行异或运算，但至少不会丢失任何位。

溢出被忽略有什么特别的原因吗？如前所述，使用 long 的成本并不高。

编辑

100000*31^7=            2751261411100000       0x9C641F717C560
6553600000*31^7 180306667837849600000    0xC641F717C5600000

请注意，后一个值恰好是前一个值的 65536 倍，这也意味着它的答案大 16 位。请注意，整数值0xC641F717C5600000 是 0xC5600000 从 16 位值中丢失了实际有效值。

*SAMPLE A*
65536*4096*27512614111  

=7385361114638319616
=0x667E12CDF0000000
   12345678
=0xF0000000

*SAMPLE B*
9*65536*4096*27512614111

=66468250031744876544
=0x9A6EA93D70000000
   12345678
=0x70000000

请注意，SAMPLE B 的最高位恰好是 9x SAMPLE A 对最终的 32 位值几乎没有任何影响 - 如果我将 9x 更改为 17x那么低位将是相同的。但是，如果最高位没有因溢出和 xord 与低 32 位而“丢失”，则该值将不同。

Answer 1

这就是乘以奇数的好处；较早的数字永远不会完全脱离整数的末尾。对于要丢失的元素，31^n 需要是 2 的幂，而这不可能发生。在您的情况下，例如，对于 31^7，您将获得 0x67E12CDF 的 32 位数字；因此，尽管有溢出，但输入元素乘以该值仍会对结果有所贡献。