一、為什么 String 重寫 equals() 后還需要重寫 hashcode()
hashCode() 的源碼：
兩個對象比較，由于 Java 默認比較的是類的地址值掠兄，每個對象一定是不同的伍掀，所以重寫 hashCode() 和 equals()。重寫 hashCode() 是為了提高效率，因為先根據(jù)類里的屬性生成 hashCode抚恒，如果生成的 hashCode 值不同赫编，則沒必要再使用 equals() 比較屬性的值巡蘸，這樣就大大減少了 equals 的次數(shù)，這對大數(shù)據(jù)量比較的效率提高是很明顯的擂送。一個很好的例子就是在集合中的使用：
Java 中的 List 集合是有序的悦荒，因此是可以重復的。set 集合是無序的嘹吨，因此是不能重復的搬味，那么如何保證不能被放入重復的元素呢，單靠 equals() 比較的話蟀拷，如果原來集合中已有 10000 個元素了碰纬，那么放入 10001 個元素，難道要將前面的所有元素都進行比較问芬，看看是否有重復悦析？這個效率可想而知，因此 hashcode 就應遇而生了此衅，Java 就采用了 hash 表强戴，利用哈希算法(也叫散列算法)，就是將對象數(shù)據(jù)根據(jù)該對象的特征使用特定的算法將其定義到一個地址上挡鞍，那么在后面定義進來的數(shù)據(jù)只要看對應的 hashCode 地址上是否有值骑歹，那么就用 equals 比較，如果沒有則直接插入墨微，如此大大減少了 equals 的使用次數(shù)道媚，執(zhí)行效率就大大提高了。
為什么必須要重寫 hashCode()翘县，簡言之就是為了保證同一個對象最域，在 equals 相同的情況下 hashCode 值也相同。如果重寫了 equals() 而未重寫 hashCode()炼蹦，可能就會出現(xiàn)兩個沒有關系的對象 equals 相同(因為 equals 都是根據(jù)對象的特征進行重寫的)羡宙，但 hashCode 不同的情況。
String 是遵守類 hashCode 的協(xié)定掐隐，equals() 相同狗热，如何保持 hashCode 相同钞馁。初始 String 對象成員變量 int hash 默認是 0，調用 hashCode() 之后h = 31 * h + val[i]匿刮，其實就是 String 內部根據(jù) char[] 來進行一個運算僧凰。那么只要內容 equals()，其內容運算生產(chǎn)的 hashCode() 也是相等的熟丸。這里也闡明了 equals() 與 hashCode() 在一般應用中的正向關系训措。
二、HashCode算法為什么采用 31 作為乘數(shù)
1??更少的乘積結果沖突
31 是質子數(shù)中一個“不大不小”的存在光羞，如果使用的是一個如 2 的較小質數(shù)绩鸣，那么得出的乘積會在一個很小的范圍，很容易造成哈希值的沖突纱兑。而如果選擇一個 100 以上的質數(shù)呀闻，得出的哈希值會超出 int 的最大范圍，這兩種都不合適潜慎。而如果對超過 50,000 個英文單詞(由兩個不同版本的 Unix 字典合并而成)進行 hashCode() 運算捡多，并使用常數(shù) 31、33铐炫、37垒手、39 和 41 作為乘子，每個常數(shù)算出的哈希值沖突數(shù)都小于 7 個(國外大神做的測試)倒信，那么這幾個數(shù)就被作為生成 hashCode 值的備選乘數(shù)了科贬。
2??31 可以被 JVM 優(yōu)化
位運算是 JVM 里最有效的計算方式：
- 【左移 <<】左邊的最高位丟棄，右邊補全0(把 << 左邊的數(shù)據(jù)*2的移動次冪)堤结。
- 【右移 >>】把>>左邊的數(shù)據(jù)/2的移動次冪唆迁。
- 【無符號右移 >>>】無論最高位是 0 還是 1鸭丛，左邊補齊 0竞穷。
所以：31 * i = (i << 5) - i【例如：31*2=62 轉換為 2*2^5-2=62】
3??理解
- 首先 hash 函數(shù)必須要選用質/素數(shù)，這個是被科學家論證過的 hash 函數(shù)減少沖突的一個理論鳞溉。
- 如果設置為偶數(shù)的話會存在溢出的情況瘾带，導致信息丟失(因為使用偶數(shù)相當于使用了移位運算)。
- 可以兼顧到虛擬機的性能熟菲，虛擬機默認使用
2<<5-1來得到很好的性能看政，且其是一個不大不小的質數(shù)，兼顧了性能和沖突率抄罕。
為什么 31 的性能和解決沖突是最優(yōu)的允蚣？回顧 String 對象的 hashCode()：
/**
* 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;
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
選擇不大不小的質數(shù)的原因
正如備注上所描述的那樣，這段代碼的實際執(zhí)行方法如下：
s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1] 推算過程為
i=0 -> h = 31 * 0 + val[0]
i=1 -> h = 31 * (31 * 0 + val[0]) + val[1]
i=2 -> h = 31 * (31 * (31 * 0 + val[0]) + val[1]) + val[2]
因此可以代入式的計算一下呆贿，假如有一個String test = “abcdef”六個字母嚷兔。使用一個較小的質數(shù) 2 或者一個較大的質數(shù) 101 帶入進去森渐，前者2^(6-1) = 32，后者101^(6-1) = 10 510 100 501冒晰。 一個太小一個太大同衣。太小的話 hash 沖突的概率就會相對大一些，太大的話就會太過于分散壶运，對于 hash 結構的集合來說就會占用過的存儲空間耐齐。因此選擇不大不小的質數(shù)是非常有必要的。
如何證明 31 這個數(shù)值就比其他數(shù)值優(yōu)呢蒋情？
整型的數(shù)值區(qū)間是 [-2147483648, 2147483647]埠况，區(qū)間大小為 2^32。所以這里可以將區(qū)間等分成 64 個子區(qū)間棵癣，每個子區(qū)間大小為 2^26询枚。
乘子 2 算出的哈希值幾乎全部落在第 32 分區(qū)，也就是 [0, 67108864) 數(shù)值區(qū)間內浙巫，落在其他區(qū)間內的哈希值數(shù)量幾乎可以忽略不計金蜀。這也就不難解釋為什么數(shù)字 2 作為乘子時，算出哈希值的沖突率如此之高的原因了的畴。
乘子 101渊抄，沖突率很低，這也說明哈希值溢出并不一定會導致沖突率上升丧裁。但是還是因為乘積太大導致整數(shù)溢出的問題护桦。所以 Java 在設計的時候是為了兼顧性能和 hash 函數(shù)的分散性。
由此煎娇，使用 31 這數(shù)值二庵，可以說是最佳實踐。
