源碼講解

1. 固定乘積31在這用到了

// 獲取hashCode "abc".hashCode();
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;
} 

在獲取hashCode的源碼中可以看到，有一個固定值31，在for循環每次執行時進行乘積計算，循環后的公式如下；s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

「那么這里為什么選擇31作為乘積值呢？」 

2. 來自stackoverflow的回答

在stackoverflow關于為什么選擇31作為固定乘積值，有一篇討論文章，Why does Java's hashCode() in String use 31 as a multiplier? 這是一個時間比較久的問題了，摘取兩個回答點贊最多的；

「413個贊????的回答」

最多的這個回答是來自《Effective Java》的內容；

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

這段內容主要闡述的觀點包括；

1. 31 是一個奇質數，如果選擇偶數會導致乘積運算時數據溢出。
2. 另外在二進制中，2個5次方是32，那么也就是     31 * i == (i << 5) - i。這主要是說乘積運算可以使用位移提升性能，同時目前的JVM虛擬機也會自動支持此類的優化。

「80個贊????的回答」

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.

• 這個回答就很有實戰意義了，告訴你用超過5千個單詞計算hashCode，這個hashCode的運算使用31、33、37、39和41作為乘積，得到的碰撞結果，31被使用就很正常了。
• 「他這句話就就可以作為我們實踐的指向了。」 

3. Hash值碰撞概率統計

接下來要做的事情并不難，只是根據stackoverflow的回答，統計出不同的乘積數對10萬個單詞的hash計算結果。10個單詞表已提供，可以通過關注公眾號：bugstack蟲洞棧進行下載 

3.1 讀取單詞字典表

1 a "n.(A)As 或 A's  安(ampere(a) art.一;n.字母A /[軍] Analog.Digital,模擬/數字 /(=account of) 帳上"
2 aaal American Academy of Arts and Letters 美國藝術和文學學會
3 aachen  亞琛[德意志聯邦共和國西部城市]
4 aacs Airways and Air Communications Service (美國)航路與航空通訊聯絡處
5 aah " [軍]Armored Artillery Howitzer,裝甲榴彈炮;[軍]Advanced Attack Helicopter,先進攻擊直升機"
6 aal "ATM Adaptation Layer,ATM適應層"
7 aapamoor "n.[生]丘澤,高低位鑲嵌沼澤" 

• 單詞表的文件格式如上，可以自行解析
• 讀取文件的代碼比較簡單，這里不展示了，可以通過     資源下載進行獲取 

3.2 Hash計算函數

public static Integer hashCode(String str, Integer multiplier) {
    int hash = 0;
    for (int i = 0; i < str.length(); i++) {
        hash = multiplier * hash + str.charAt(i);
    }
    return hash;
} 

• 這個過程比較簡單，與原hash函數對比只是替換了可變參數，用于我們統計不同乘積數的計算結果。 

3.3 Hash碰撞概率計算

想計算碰撞很簡單，也就是計算那些出現相同哈希值的數量，計算出碰撞總量即可。這里的實現方式有很多，可以使用set、map也可以使用java8的stream流統計distinct。

private static RateInfo hashCollisionRate(Integer multiplier, List<Integer> hashCodeList) {
    int maxHash = hashCodeList.stream().max(Integer::compareTo).get();
    int minHash = hashCodeList.stream().min(Integer::compareTo).get();
    int collisionCount = (int) (hashCodeList.size() - hashCodeList.stream().distinct().count());
    double collisionRate = (collisionCount * 1.0) / hashCodeList.size();
    return new RateInfo(maxHash, minHash, multiplier, collisionCount, collisionRate);
}

• 這里記錄了最大hash和最小hash值，以及最終返回碰撞數量的統計結果。

3.4 單元測試

@Before
public void before() {
    "abc".hashCode();
    // 讀取文件，103976個英語單詞庫.txt
    words = FileUtil.readWordList("E:/itstack/git/github.com/interview/interview-01/103976個英語單詞庫.txt");
}

@Test
public void test_collisionRate() {
    List<RateInfo> rateInfoList = HashCode.collisionRateList(words, 2, 3, 5, 7, 17, 31, 32, 33, 39, 41, 199);
    for (RateInfo rate : rateInfoList) {
        System.out.println(String.format("乘數 = %4d, 最小Hash = %11d, 最大Hash = %10d, 碰撞數量 =%6d, 碰撞概率 = %.4f%%", rate.getMultiplier(), rate.getMinHash(), rate.getMaxHash(), rate.getCollisionCount(), rate.getCollisionRate() * 100));
    }
} 

• 以上先設定讀取英文單詞表中的10個單詞，之后做hash計算。
• 在hash計算中把單詞表傳遞進去，同時還有乘積數；     2, 3, 5, 7, 17, 31, 32, 33, 39, 41, 199，最終返回一個list結果并輸出。
• 這里主要驗證同一批單詞，對于不同乘積數會有怎么樣的hash碰撞結果。

「測試結果」

單詞數量：103976
乘數 =    2, 最小Hash =          97, 最大Hash = 1842581979, 碰撞數量 = 60382, 碰撞概率 = 58.0730%
乘數 =    3, 最小Hash = -2147308825, 最大Hash = 2146995420, 碰撞數量 = 24300, 碰撞概率 = 23.3708%
乘數 =    5, 最小Hash = -2147091606, 最大Hash = 2147227581, 碰撞數量 =  7994, 碰撞概率 = 7.6883%
乘數 =    7, 最小Hash = -2147431389, 最大Hash = 2147226363, 碰撞數量 =  3826, 碰撞概率 = 3.6797%
乘數 =   17, 最小Hash = -2147238638, 最大Hash = 2147101452, 碰撞數量 =   576, 碰撞概率 = 0.5540%
乘數 =   31, 最小Hash = -2147461248, 最大Hash = 2147444544, 碰撞數量 =     2, 碰撞概率 = 0.0019%
乘數 =   32, 最小Hash = -2007883634, 最大Hash = 2074238226, 碰撞數量 = 34947, 碰撞概率 = 33.6106%
乘數 =   33, 最小Hash = -2147469046, 最大Hash = 2147378587, 碰撞數量 =     1, 碰撞概率 = 0.0010%
乘數 =   39, 最小Hash = -2147463635, 最大Hash = 2147443239, 碰撞數量 =     0, 碰撞概率 = 0.0000%
乘數 =   41, 最小Hash = -2147423916, 最大Hash = 2147441721, 碰撞數量 =     1, 碰撞概率 = 0.0010%
乘數 =  199, 最小Hash = -2147459902, 最大Hash = 2147480320, 碰撞數量 =     0, 碰撞概率 = 0.0000%

Process finished with exit code 0

 

以上就是不同的乘數下的hash碰撞結果圖標展示，從這里可以看出如下信息；

1. 乘數是2時，hash的取值范圍比較小，基本是堆積到一個范圍內了，后面內容會看到這塊的展示。
2. 乘數是3、5、7、17等，都有較大的碰撞概率
3. 「乘數是31的時候，碰撞的概率已經很小了，基本穩定。」
4. 順著往下看，你會發現199的碰撞概率更小，這就相當于一排奇數的茅坑量多，自然會減少碰撞。     「但這個范圍值已經遠超過int的取值范圍了，如果用此數作為乘數，又返回int值，就會丟失數據信息」。 

4. Hash值散列分布

除了以上看到哈希值在不同乘數的一個碰撞概率后，關于散列表也就是hash，還有一個非常重要的點，那就是要盡可能的讓數據散列分布。只有這樣才能減少hash碰撞次數，也就是后面章節要講到的hashMap源碼。

那么怎么看散列分布呢？如果我們能把10萬個hash值鋪到圖表上，形成的一張圖，就可以看出整個散列分布。但是這樣的圖會比較大，當我們縮小看后，就成一個了大黑點。所以這里我們采取分段統計，把2 ^ 32方分64個格子進行存放，每個格子都會有對應的數量的hash值，最終把這些數據展示在圖表上。 

4.1 哈希值分段存放

public static Map<Integer, Integer> hashArea(List<Integer> hashCodeList) {
    Map<Integer, Integer> statistics = new LinkedHashMap<>();
    int start = 0;
    for (long i = 0x80000000; i <= 0x7fffffff; i += 67108864) {
        long min = i;
        long max = min + 67108864;
        // 篩選出每個格子里的哈希值數量，java8流統計；https://bugstack.cn/itstack-demo-any/2019/12/10/%E6%9C%89%E7%82%B9%E5%B9%B2%E8%B4%A7-Jdk1.8%E6%96%B0%E7%89%B9%E6%80%A7%E5%AE%9E%E6%88%98%E7%AF%87(41%E4%B8%AA%E6%A1%88%E4%BE%8B).html
        int num = (int) hashCodeList.parallelStream().filter(x -> x >= min && x < max).count();
        statistics.put(start++, num);
    }
    return statistics; 

• 這個過程主要統計     int取值范圍內，每個哈希值存放到不同格子里的數量。
• 這里也是使用了java8的新特性語法，統計起來還是比較方便的。 

4.2 單元測試

@Test
public void test_hashArea() {
    System.out.println(HashCode.hashArea(words, 2).values());
    System.out.println(HashCode.hashArea(words, 7).values());
    System.out.println(HashCode.hashArea(words, 31).values());
    System.out.println(HashCode.hashArea(words, 32).values());
    System.out.println(HashCode.hashArea(words, 199).values());
} 

• 這里列出我們要統計的乘數值，每一個乘數下都會有對應的哈希值數量匯總，也就是64個格子里的數量。
• 最終把這些統計值放入到excel中進行圖表化展示。

「統計圖表」

 

• 以上是一個堆積百分比統計圖，可以看到下方是不同乘數下的，每個格子里的數據統計。
• 除了199不能用以外，31的散列結果相對來說比較均勻。 

4.2.1 乘數2散列

 

• 乘數是2的時候，散列的結果基本都堆積在中間，沒有很好的散列。

4.2.2 乘數31散列

 

• 乘數是31的時候，散列的效果就非常明顯了，基本在每個范圍都有數據存放。 

4.2.3 乘數199散列

 

• 乘數是199是不能用的散列結果，但是它的數據是更加分散的，從圖上能看到有兩個小山包。但因為數據區間問題會有數據丟失問題，所以不能選擇。