以下這段代碼是jdk8里默認(rèn)的String.hashCode方法的實(shí)現(xiàn)。這里可以看出實(shí)現(xiàn)里采用了一個(gè)神奇的魔法數(shù)字31.為什么是31而不是32接奈，或者37拂酣？
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;
}
以下是一個(gè)簡(jiǎn)單的代碼椅棺，展示了idea intellij 自帶功能重寫了hashCode方式屁擅。原理與jdk中string.equals相同.
public class Course implements Cloneable,Serializable {
private String name;
private String score;
private String term;
private String id;
//setters偿凭、getters略
@Override
public int hashCode() {
int result = name != null ? name.hashCode() : 0;
result = 31 * result + (score != null ? score.hashCode() : 0);
result = 31 * result + (term != null ? term.hashCode() : 0);
result = 31 * result + (id != null ? id.hashCode() : 0);
return result;
}
}
比如 Guava 庫(kù)中的 Objects.hashCode(), JDK 中的 Arrays.hashCode()，IntelliJ IDEA 生成的 hashCode() 方法使用的算法也與 String.hashCode() 相同煤蹭。
hashcode=s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
對(duì)于為什么采用37笔喉，網(wǎng)上主要有兩種流行的答案
1、二進(jìn)制計(jì)算中硝皂，31 * i = (i << 5) - i常挚，這樣的計(jì)算可以轉(zhuǎn)換移位和減法，節(jié)約了計(jì)算資源
2稽物、基于31可以產(chǎn)生較少的哈希碰撞奄毡。
在參考文章[3]里JohnZaj說(shuō)：As Goodrich and Tamassia point out, If you take over 50,000 English words (formed as the union of the word lists provided in two variants of Unix), using the constants 31, 33, 37, 39, and 41 will produce less than 7 collisions in each case. Knowing this, it should come as no surprise that many Java implementations choose one of these constants.
Coincidentally, I was in the middle of reading the section "polynomial hash codes" when I saw this question.
EDIT: here is link to the ~10mb PDF book i'm referring to above. See section 10.2 Hash Tables (page 413) of Data Structures and Algorithms in Java
參考文章：
[1]. String.hashCode() 實(shí)現(xiàn)及 Magic Number 31
[2]. http://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622
[3]. https://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier
