哈希码计算为什么要乘和忽略溢出位？

这个问题不是关于为什么一个乘法，这是相当明显的 - 它的分布。哈希码计算为什么要乘和忽略溢出位？

而恰恰这是成为更多的因素包括在散列码计算公式更重要乘法更多关于一个性质。

一个简单的计算显然可能会溢出，但这并不重要。

a * 31 + b

真正的问题是当许多项目在公式中被证明。

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

一旦超过5或6项是包括作为其位由哈希码值是至多包括5+术语时有溢出的第一项的值被丢失。使用这个系统只有最后5个左右的术语才是最终价值的重要贡献者。

31^7 > Integer.MAX_VALUE

那么，为什么大多数计算没有回滚周围的溢出位，并且xor w /结果的低位。我赞赏这需要一些小窍门，并且计算必须使用长整数（64位）来完成，所以前32位可以与整数结果进行XOR运算，但至少不会丢失任何位。

溢出被忽略的原因是什么？如前所述，使用长时间并不昂贵。

EDIT

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

注意样品B的最顶部位这正是9X 样品A使得在最后的32位的值几乎绝对没有差异 - 如果我改变9X到17倍，然后较低位将是相同。但是，如果由于溢出而导致最高位未被“丢失”并且低32位的xord值则会不同。

来源

2011-02-10 mP.

溢出被忽略了吗？如前所述，使用长时间并不昂贵。

但是它几乎没有任何收益。这种方法通常会产生一个很好的价值分布。

来源

2011-02-10 00:56:21 jason

不仅如此，而且很长一段时间会遇到同样的问题，只会花费一点点时间。（对不起，这是一个糟糕的...） – corsiKa 2011-02-10 08:22:08

素数作为乘数的全部原因是因为可能性意味着数值向左移动，最终所有位都丢失。然而，素数仍然有相同的概率，他们会更好一点，需要更长的时间消失。 – 2011-02-11 12:03:06

这是乘以奇数的好处;早期的数字不会完全落在整数的末尾。对于丢失的元素，31^n将需要是2的幂，并且不会发生。例如，在你的情况下，用31^7，你得到一个32位数的0x67E12CDF;因此，尽管溢出，输入元素乘以该值仍将对结果作出贡献。

来源

2011-02-10 00:57:18

是的，但随着时间的推移，只有非常低的位实际存在于散列码中。 – 2011-02-10 02:46:26

我在示例中看不到这一点。对我而言，它们看起来与您计算哈希代码的方式无关：a * 31 + b。

你也许可以找到一些a和b，这会给出相同的散列码（但高位不同）。然后将高位反转回散列码是有意义的。

或者，((a * 31) + b)*31 + ... + z的另一个例子是。然后找到一些a,b，...，z，其中哈希码不再依赖于a。所以a不会是一个重要的贡献者。

当然，如果您将31更改为65536，则很容易找到那些a，...，z。任何值都可以，a位全部都会掉线，a会被移到左边并被切断。但是，你可以这样做为31？或者类似的，你可以把高位反回来。但是，为什么？你能找到一个有用的案例吗？

65536的问题是，在二进制中它看起来像这样10000000000000000。所以，当你用它乘以一个数字时，二进制数就会有那16个零。对于31，二进制，这不会发生。

哦，我不是说那些例子不存在，因为它们（它毕竟只是一个散列）。但是，你不会找到很多或类似的例子。

来源

2011-02-10 14:01:16 Ishtar

哈希码计算为什么要乘和忽略溢出位？

回答

相关问题