为什么Java的哈希值code（）在字符串中使用31作为乘数？ [英] Why does Java's hashCode() in String use 31 as a multiplier?

问题描述

在Java中，哈希code 为字符串对象被计算为

In Java, the hash code for a String object is computed as

S [0] * 31 ^（N-1）+ S [1] * 31 ^（N-2）+ ... S [N-1]

使用 INT 算术，其中 S [I] 是我 ^日字符串的字符， N 是字符串的长度， ^ 表示幂。

using int arithmetic, where s[i] is the i^th character of the string, n is the length of the string, and ^ indicates exponentiation.

为什么31作为乘数？

我明白乘数应该是一个比较大的素数。那么，为什么不是29或37，甚至是97？

I understand that the multiplier should be a relatively large prime number. So why not 29, or 37, or even 97?

推荐答案

据约书亚布洛赫的有效的Java （一本书，不能充分推荐的，而我买得益于不断提及的计算器）：

According to Joshua Bloch's Effective Java (a book that can't be recommended enough, and which I bought thanks to continual mentions on stackoverflow):

值31的选择，因为它是一个奇素数。如果是连和乘法溢出时，信息会丢失，如乘2等于转向。使用黄金的优点是不太清楚，但它是传统的。 31一个很好的特性是乘法可以通过移位和减法有更好的表现来代替： 31 *我==（I＆LT;小于5） - 我 。现代的虚拟机自动做这种优化。

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

（第3章，第9项：始终覆盖散列code，当你重载equals，第48页）的

这篇关于为什么Java的哈希值code（）在字符串中使用31作为乘数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！