面經手冊 · 第2篇《資料結構，HashCode為什麼使用31作為乘數？》

作者：小傅哥

部落格：https://bugstack.cn

沉澱、分享、成長，讓自己和他人都能有所收獲！😄

一、前言

在面經手冊的前兩篇介紹了《面試官都問我啥》和《認知自己的技術棧盲區》，這兩篇内容主要為了說明面試過程的考查範圍，包括個人的自我介紹、技術棧積累、項目經驗等，以及在技術棧盲區篇章中介紹了一個整套技術棧在系統架構用的應用，以此全方面的掃描自己有哪些盲區還需要補充。而接下來的章節會以各個系列的技術棧中遇到的面試題作為切入點，講解技術要點，了解技術原理，包括；資料結構、資料算法、技術棧、架構等進行逐漸展開學習。

在進入資料結構章節講解之前可以先了解下，資料結構都有哪些，基本可以包括；

數組(Array)

、

棧(Stack)

隊列(Queue)

連結清單(LinkList)

樹(Tree)

散清單(Hash)

堆(Heap)

圖(Graph)

。

而本文主要講解的就是與散清單相關的

HashCode

，本來想先講

HashMap

，但随着整理資料發現與

HashMap

的實作中，

HashCode

的散列占了很重要的一設計思路，是以最好把這部分知識補全，再往下講解。

二、面試題

說到HashCode的面試題，可能這是一個非常核心的了。其他考點；怎麼實作散列、計算邏輯等，都可以通過這道題的學習了解相關知識。

Why does Java's hashCode() in String use 31 as a multiplier?

這個問題其實☞指的就是，hashCode的計算邏輯中，為什麼是31作為乘數。

三、資源下載下傳

本文講解的過程中涉及部分源碼等資源，可以通過關注公衆号：

bugstack蟲洞棧

，回複下載下傳進行擷取{回複下載下傳後打開獲得的連結，找到編号ID：19}，包括；

HashCode 源碼測試驗證工程， interview-03
103976個英語單詞庫.txt，驗證HashCode值
HashCode散列分布.xlsx，散列和碰撞圖表

四、源碼講解

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

的源碼中可以看到，有一個固定值

，在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.

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

31 是一個奇質數，如果選擇偶數會導緻乘積運算時資料溢出。
另外在二進制中，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碰撞結果圖示展示，從這裡可以看出如下資訊；

乘數是2時，hash的取值範圍比較小，基本是堆積到一個範圍内了，後面内容會看到這塊的展示。
乘數是3、5、7、17等，都有較大的碰撞機率
乘數是31的時候，碰撞的機率已經很小了，基本穩定。
順着往下看，你會發現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是不能用的散列結果，但是它的資料是更加分散的，從圖上能看到有兩個小山包。但因為資料區間問題會有資料丢失問題，是以不能選擇。

文中引用

http://www.tianxiaobo.com/2018/01/18/String-hashCode-方法為什麼選擇數字31作為乘子/
https://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier

五、總結

以上主要介紹了hashCode選擇31作為乘數的主要原因和實驗資料驗證，算是一個散列的資料結構的案例講解，在後續的類似技術中，就可以解釋其他的源碼設計思路了。
看過本文至少應該讓你可以從根本上解釋了hashCode的設計，關于他的所有問題也就不需要死記硬背了，學習程式設計内容除了最開始的模仿到深入以後就需要不斷的研究數學邏輯和資料結構。
文中參考了優秀的hashCode資料和stackoverflow，并親自做實驗驗證結果，大家也可以下載下傳本文中資源内容；英文字典、源碼、excel圖表等内容。

六、推薦閱讀

面經手冊 · 開篇《面試官都問我啥》
工作兩年履歷寫成這樣，誰要你呀！
講道理，隻要你是一個愛折騰的程式員，畢業找工作真的不需要再花錢教育訓練！
大學四年到畢業工作5年的學習路線資源彙總
手寫mybait-spring核心功能(幹貨好文一次學會工廠bean、類代理、bean注冊的使用)
源碼分析 | Mybatis接口沒有實作類為什麼可以執行增删改查

公衆号：bugstack蟲洞棧 | 作者小傅哥多年從事一線網際網路 Java 開發的學習曆程技術彙總，旨在為大家提供一個清晰詳細的學習教程，側重點更傾向編寫Java核心内容。如果能為您提供幫助，請給予支援(關注、點贊、分享)！

面經手冊 · 第2篇《資料結構，HashCode為什麼使用31作為乘數？》

一、前言

二、面試題

三、資源下載下傳

四、源碼講解

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

2. 來自stackoverflow的回答

3. Hash值碰撞機率統計

3.1 讀取單詞字典表

3.2 Hash計算函數

3.3 Hash碰撞機率計算

3.4 單元測試

4. Hash值散列分布

4.1 哈希值分段存放

4.2 單元測試

4.2.1 乘數2散列

4.2.2 乘數31散列

4.2.3 乘數199散列

五、總結

六、推薦閱讀

繼續閱讀

資料結構與算法（27）——排序（二）

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

軟體測試工程師跳槽：收到面試電話後，我會做的事。

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

Linux裝置模型（中）之上層容器

scala (3) Function 和 Method