導讀我們知道String.hashCode()返回的是一個int類型的數值，那當某個字符串的hash值超出int的最大范圍后會發生什么呢？首先我們來看下Stri....

我們知道String.hashCode()返回的是一個int類型的數值，那當某個字符串的hash值超出int的最大范圍后會發生什么呢？

首先我們來看下String.hashCode()的源碼，看看它是如何計算一個字符串的hash值：

/** The value is used for character storage. */ private final char value[]; /** Cache the hash code for the string */ private int hash; // Default to 0/** * 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.String有一個私有變量hash來緩存哈希值，即當該串第一次調用hashCode()方法時，hash默認值為0，繼續執行，當字符串長度大于0時計算出一個哈希值賦給hash,之后再調用hashCode()方法時不會重新計算，直接返回hash

2.計算時，使用的是該字符串截成的一個字符數組，用每個字符的ASCII值進行計算，根據注釋可以看出哈希計算公式是：s[0]*31^(n-1) s[1]*31^(n-2) ... s[n-1],n是字符數組的長度，s是字符數組

3.算法中還有一個乘數31，為什么使用31呢？

• hash函數必須選用質數（在大于一的自然數中除了1和它本身以外不再有其他因數的自然數）這是被科學家論證過的hash函數減少沖突的理論
• 如果乘數是偶數，并且乘法溢出的話，信息就會丟失，因為使用偶數相當于位移運算（低位補0）
• 使用31有個很好的性能，即用移位和減法來代替乘法，可以得到更好的性能：31*i == (i<<5)-i，現代的VM可以自動完成這種優化
• 31是個不大不小的質數，兼顧了性能和沖突率。我們利用s[0]*31^(n-1) s[1]*31^(n-2) ... s[n-1]這個公式，如果乘數換做是2或101計算字符串"abcde"這六個字母的hash值時，乘數為2，2^(6-1) = 32，乘數為101， 101^(6-1) = 10,510,100,501 一個太小一個太大。太小hash沖突概率大，太大過于分散占用存儲空間大，所以選擇一個不大不小的質數很有必要

也有實驗證明31這個數值更優：

整形的數值區間是 [-2147483648, 2147483647]，區間大小為 2^32。

所以這里可以將區間分成64個子區間，每個子區間大小為 2^26

乘子2算出的哈希值幾乎全部落在第32分區，也就是 (0, 67108864)數值區間內，落在其他區間內的哈希值數量幾乎可以忽略不計。這也就不難解釋為什么數字2作為乘子時，算出哈希值的沖突率如此之高的原因了

和2基本上差不多

相對不錯

分散比較均勻了

沖突率很低，這也說明哈希值溢出并不一定會導致沖突率上升。但是還是因為乘積太大導致整數溢出的問題。所以兼顧性能和沖突率31最為合適

看完了String.hashCode()的源碼，可以肯定的說一定會有字符串計算出來的hash值是超出int的最大取值范圍的，那這時候程序會怎么處理呢？

測試代碼：

@Test public void test3() { System.out.println("a".hashCode()); System.out.println("ab".hashCode()); System.out.println("abc".hashCode()); System.out.println("abcd".hashCode()); System.out.println("abcde".hashCode()); System.out.println("abcdef".hashCode()); System.out.println("abcdefg".hashCode()); }

結果輸出：

最后兩個輸出的是負數，按照公式來計算的話，"abcdef"的hash值應該是9259939531 102=2870581347，這明顯已經超出了int的取值范圍

在計算9259939531=2870581245時，結果已經超出了int的最大范圍，這時Java虛擬機做了默認的類型提升，把中間結果用long類型存放，然后計算2870581245 102=2870581347返回結果依然不能被int容納，根據Java的基礎類型的變窄轉換規則，取結果的低32位，然后在計算機中實際是用補碼存儲的，正數的補碼=原碼，所以2870581347在計算機中是這樣的：

00000000 00000000 00000000 00000000 10101011 00011001 10011000 01100011

基于變窄轉換，丟棄高于int寬度的部分，得到補碼：

10101011 00011001 10011000 01100011

然后首位是符號位，1代表負數，負數的補碼=反碼 1，反推得到反碼：

10101011 00011001 10011000 01100010

負數的反碼=符號位不變，原碼按位取反，反推得到原碼：

11010100 11100110 01100111 10011101=-1010100 11100110 01100111 10011101

轉化成十進制就是"-1424385949"，所以就有了上圖的輸出結果

來源：https://blog.csdn.net/weixin_45661382