HashCode使用31作為乘數(shù)的原因是什么

源碼講解

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循環(huán)每次執(zhí)行時進行乘積計算，循環(huán)后的公式如下；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》的內(nèi)容；

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.

這段內(nèi)容主要闡述的觀點包括；

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

「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.

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

3. Hash值碰撞概率統(tǒng)計

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

3.1 讀取單詞字典表

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

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

3.2 Hash計算函數(shù)

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;
} 

• 這個過程比較簡單，與原h(huán)ash函數(shù)對比只是替換了可變參數(shù)，用于我們統(tǒng)計不同乘積數(shù)的計算結果。 

3.3 Hash碰撞概率計算

想計算碰撞很簡單，也就是計算那些出現(xiàn)相同哈希值的數(shù)量，計算出碰撞總量即可。這里的實現(xiàn)方式有很多，可以使用set、map也可以使用java8的stream流統(tǒng)計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值，以及最終返回碰撞數(shù)量的統(tǒng)計結果。

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("乘數(shù) = %4d, 最小Hash = %11d, 最大Hash = %10d, 碰撞數(shù)量 =%6d, 碰撞概率 = %.4f%%", rate.getMultiplier(), rate.getMinHash(), rate.getMaxHash(), rate.getCollisionCount(), rate.getCollisionRate() * 100));
    }
} 

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

「測試結果」

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

Process finished with exit code 0

 

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

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

4. Hash值散列分布

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

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

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;
        // 篩選出每個格子里的哈希值數(shù)量，java8流統(tǒng)計；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; 

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

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());
} 

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

「統(tǒng)計圖表」

 

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

4.2.1 乘數(shù)2散列

 

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

 

4.2.2 乘數(shù)31散列

 

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

4.2.3 乘數(shù)199散列

 

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