根据Java文档,String对象的哈希代码是这样计算的:
S [0]*31^(n-1) + S [1]*31^(n-2) +…+ s (n - 1) 使用int算术,其中s[i]是 字符串的第i个字符,n是的长度 字符串,^表示取幂。
为什么用31作为乘数?
我知道乘数应该是一个相对较大的质数。那么为什么不是29岁,37岁,甚至97岁呢?
根据Java文档,String对象的哈希代码是这样计算的:
S [0]*31^(n-1) + S [1]*31^(n-2) +…+ s (n - 1) 使用int算术,其中s[i]是 字符串的第i个字符,n是的长度 字符串,^表示取幂。
为什么用31作为乘数?
我知道乘数应该是一个相对较大的质数。那么为什么不是29岁,37岁,甚至97岁呢?
当前回答
在(大多数)老式处理器上,乘以31可能相对便宜。例如,在ARM上,它只有一条指令:
RSB r1, r0, r0, ASL #5 ; r1 := - r0 + (r0<<5)
大多数其他处理器都需要单独的移位和减法指令。然而,如果你的乘数很慢,这仍然是一种胜利。现代处理器往往具有快速乘法器,所以只要32在正确的一边,就没有太大区别。
这不是一个很好的哈希算法,但它已经足够好了,比1.0代码更好(比1.0规范好得多!)。
其他回答
Bloch并没有深入研究这个问题,但我总是听到/相信这是基本的代数。哈希可以归结为乘法和模运算,这意味着如果可以的话,永远不要使用带公因式的数字。换句话说,相对素数提供了答案的均匀分布。
使用哈希的数字通常是:
你放入的数据类型的模量 (2^32或2^64) 哈希表中桶数的模数(变化。在java中,以前是质数,现在是2^n) 在混合函数中乘以或平移一个神奇的数字 输入值
实际上,您只能控制其中的几个值,因此需要多加注意。
我不确定,但我猜他们测试了一些质数样本,发现31在一些可能的字符串样本中给出了最好的分布。
在最新版本的JDK中,仍然使用31。https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/lang/String.html hashCode ()
哈希字符串的目的是
唯一(让我们看看hashcode计算文档中的运算符^,它有助于唯一) 计算成本低
31是可以放入8位(= 1字节)寄存器的最大值,是可以放入1字节寄存器的最大素数,是奇数。
31乘以<<5然后减去自己,因此需要廉价的资源。
事实上,37就可以了!Z:= 37 * x可计算为y:= x + 8 * x;z:= x + 4 * y。这两个步骤都对应一个LEA x86指令,所以这是非常快的。
事实上,通过设置y:= x + 8 * x,可以以同样的速度完成与更大的素数73的乘法运算;Z:= x + 8 * y。
使用73或37(而不是31)可能会更好,因为它会导致更密集的代码:两条LEA指令只占用6个字节,而move+shift+subtract(31的乘法)占用7个字节。一个可能的警告是,这里使用的3参数LEA指令在英特尔的Sandy桥架构上变慢了,延迟增加了3个周期。
而且,73是谢尔顿·库珀最喜欢的数字。
根据Joshua Bloch的《Effective Java》(这本书再怎么推荐都不为过,多亏了stackoverflow上不断的提及,我才买了这本书):
选择值31是因为它是一个奇质数。如果它是偶数并且乘法溢出,信息就会丢失,因为乘2相当于移位。使用质数的优势不太明显,但它是传统的。31的一个很好的属性是乘法可以被移位和减法代替,以获得更好的性能:31 * i == (i << 5) - i。现代虚拟机自动进行这种优化。
(摘自第3章第9项:重写equals时总是重写hashcode,第48页)