为什么 Java 在 String 中的 hashCode() 使用 31 作为乘数? [英] Why does Java's hashCode() in String use 31 as a multiplier?

问题描述

根据 Java 文档，String 对象的哈希码计算如下:

<块引用>

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

使用 int 算法，其中 s[i] 是字符串的第 i 个字符，n 是字符串的长度字符串，^ 表示求幂.

为什么将 31 用作乘数?

我理解乘数应该是一个比较大的素数.那么为什么不是 29、37、甚至 97?

解决方案

根据 Joshua Bloch 的 Effective Java(一本不太推荐的书，由于不断提到 stackoverflow，我买了这本书):

<块引用>

选择值 31 是因为它是一个奇质数.如果它是偶数并且乘法溢出，信息就会丢失，因为乘以 2 相当于移位.使用素数的优点不太清楚，但它是传统的.31 的一个很好的特性是乘法可以用移位和减法代替以获得更好的性能:31 * i == (i << 5) - i.现代虚拟机会自动进行这种优化.

(来自第 3 章，第 9 项:在覆盖等于时始终覆盖哈希码，第 48 页)

Per the Java documentation, the hash code for a String object is computed as:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

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

Why is 31 used as a multiplier?

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

解决方案

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):

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.

(from Chapter 3, Item 9: Always override hashcode when you override equals, page 48)

这篇关于为什么 Java 在 String 中的 hashCode() 使用 31 作为乘数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！