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
/**
* 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;
}
1
private int hash; // Default to 0

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

hash的计算方法是:

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方法判断字符串相等或者字符串回文,都存在反例。