Java中String类的hashCode方法

首先我们先来看一下 String 的 hashCode 源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 /**
* Returns a hash code for this string. The hash code for a
* {@code String} object is computed as
* <blockquote><pre>
* s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
* </pre></blockquote>
* using {@code int} arithmetic, where {@code s[i]} is the
* <i>i</i>th character of the string, {@code n} is the length of
* the string, and {@code ^} indicates exponentiation.
* (The hash value of the empty string is zero.)
*
* @return a hash code value for this object.
*/
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;

for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}

private int hash; // Default to 0

String 中有个私有字段 hash,表示该字符串的哈希值,默认为 0,在调用 hashCode 方法时,如果 hash 不为 0 就直接返回了。如果为 0,字符串的哈希值被计算并且赋值给 hash 字段,之后再调用 hashCode 方法便可以直接获取 hash 字段返回。

hash 的计算方法是:

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

s[i] 是 string 的第 i+1 个字符,s[0] 表示第 1 个字符,n 是 String 的长度。s[0]*31^(n-1) 表示 31 的 n-1 次方再乘以第一个字符的值。

为什么是 31,可以参考 stackoverflow 相关问题 Why does Java’s hashCode() in String use 31 as a multiplier?

因为 31 是一个奇质数。一方面可以产生更分散的散列,即不同字符串 hash 值也一般不同,所以在选择系数的时候要选择尽量长的并且让乘法结果尽量不要溢出的系数,如果计算出来的hash地址越大,所谓的「冲突」就越少,查找起来效率也会提高。但是也不能过大,在 java 乘法中如果数字相乘过大会导致溢出的问题,从而导致数据的丢失。另一个方面主要是计算效率比较高,31 i=32 i - i=(i << 5) - i,这种位移与减法结合的计算相比一般的乘法运算快很多。

字符串哈希值可以做很多事情,通常是类似于字符串判等,判回文之类的。但是仅仅依赖于哈希值来判断其实是不严谨的,除非能够保证不会有哈希冲突,不过通常这一点很难做到。

就拿 jdk 中 String 类的哈希方法来举例,字符串 “gdejicbegh” 与字符串 “hgebcijedg” 具有相同的 hashCode() 返回值 -801038016,并且它们具有 reverse 的关系。这个例子说明了用 jdk 中默认的 hashCode 方法判断字符串相等或者字符串回文,都存在反例。