快來，我悄悄的給你說幾個HashCode的破事。

這是why技術的第 72 篇原創文章

Hash沖突是怎麼回事

在這個文章正式開始之前，先幾句話把這個問題說清楚了：我們常說的 Hash 沖突到底是怎麼回事？

直接上個圖檔：

你說你看到這個圖檔的時候想到了什麼東西？

有沒有想到 HashMap 的數組加連結清單的結構？

對咯，我這裡就是以 HashMap 為切入點，給大家講一下 Hash 沖突。

接着我們看下面這張圖：

假設現在我們有個值為 [why技術] 的 key，經過 Hash 算法後，計算出值為 1，那麼含義就是這個值應該放到數組下标為 1 的地方。

但是如圖所示，下标為 1 的地方已經挂了一個 eat 的值了。這個坑位已經被人占着了。

那麼此時此刻，我們就把這種現象叫為 Hash 沖突。

HashMap 是怎麼解決 Hash 沖突的呢？

鍊位址法，也叫做拉鍊法。

數組中出現 Hash 沖突了，這個時候連結清單的資料結構就派上用場了。

連結清單怎麼用的呢？看圖：

這樣問題就被我們解決了。

其實 hash 沖突也就是這麼一回事：不同的對象經過同一個 Hash 算法後得到了一樣的 HashCode。

那麼寫到這裡的時候我突然想到了一個面試題：

請問我上面的圖是基于 JDK 什麼版本的 HashMap 畫的圖？

為什麼想到了這個面試題呢？

因為我畫圖的時候猶豫了大概 0.3 秒，往連結清單上挂的時候，我到底是使用頭插法還是尾插法呢？

衆所周知，JDK 7 中的 HashMap 是采用頭插法的，即 [why技術] 在 [eat] 之前，JDK 8 中的 HashMap 采用的是尾插法。

這面試題怎麼說呢，真的無聊。但是能怎麼辦呢，八股文該背還是得背。

面試嘛，背一背，不寒碜。

建構 HashCode 一樣的 String

前面我們知道了，Hash 沖突的根本原因是不同的對象經過同一個 Hash 算法後得到了一樣的 HashCode。

這句話乍一聽：嗯，很有道理，就是這麼一回事，沒有問題。

比如我們常用的 HashMap ，絕大部分情況 key 都是 String 類型的。要出現 Hash 沖突，最少需要兩個 HashCode 一樣的 String 類。

那麼我問你：怎麼才能快速弄兩個 HashCode 一樣的 String 呢？

怎麼樣，有點懵逼了吧？

從很有道理，到有點懵逼隻需要一個問題。

來，我帶你分析一波。

我先問你：長度為 1 的兩個不一樣的 String，比如下面這樣的代碼，會不會有一樣的 HashCode？

String a = "a";
String b = "b";
           

肯定是不會的，對吧。

如果你不知道的話，建議你去 ASCII 碼裡面找答案。

我們接着往下梳理，看看長度為 2 的 String 會不會出現一樣的 HashCode？

要回答這個問題，我們要先看看 String 的 hashCode 計算方法，我這裡以 JDK 8 為例：

我們假設這兩個長度為 2 的 String，分别是 xy 和 ab 吧。

注意這裡的 xy 和 ab 都是占位符，不是字元串。

類似于國小課本中一進制二次方程中的未知數 x 和 y，我們需要帶入到上面的 hashCode 方法中去計算。

hashCode 算法，最主要的就是其中的這個 for 循環。

for 循環裡面的有三個我們不知道是啥的東西：h，value.length 和 val[i]。我們 debug 看一下：

h 初始情況下等于 0。

String 類型的底層結構是 char 數組，這個應該知道吧。

是以，value.length 是字元串的長度。val[] 就是這個 char 數組。

把 xy 帶入到 for 循環中，這個 for 循環會循環 2 次。

第一次循環：h=0，val[0]=x，是以 h=31*0+x，即 h=x。

第二次循環：h=x，val[1]=y，是以 h=31*x+y。

是以，經過計算後， xy 的 hashCode 為 31*x+y。

同理可得，ab 的 hashCode 為 31*a+b。

由于我們想要建構 hashCode 一樣的字元串，是以可以得到等式：

31x+y=31a+b

那麼問題就來了：請問 x，y，a，b 分别是多少？

你算的出來嗎？

你算的出來個錘子！黑闆上的排列組合你不是舍不得解開，你就是解不開。

但是我可以解開，帶大家看看這個題怎麼搞。

數學課開始了。注意，我要變形了。

31x+y=31a+b 可以變形為：

31x-31a=b-y。

即，31(x-a)=b-y。

這個時候就清晰很多了，很明顯，上面的等式有一個特殊解：

x-a=1，b-y=31。

因為，由上可得：對于任意兩個字元串 xy 和 ab，如果它們滿足 x-a=1，即第一個字元的 ASCII 碼值相差為 1，同時滿足 b-y=31，即第二個字元的 ASCII 碼值相差為 -31。那麼這兩個字元的 hashCode 一定相等。

都已經說的這麼清楚了，這樣的組合對照着 ASCII 碼表來找，不是一抓一大把嗎？

Aa 和 BB，對不對？

Ab 和 BC，是不是？

Ac 和 BD，有沒有？

好的。現在，我們可以生成兩個 HashCode 一樣的字元串了。

我們在稍微加深一點點難度。假設我要建構 2 個以上 HashCode 一樣的字元串該怎麼辦？

我們先分析一下。

Aa 和 BB 的 HashCode 是一樣的。我們把它兩一排列組合，那不還是一樣的嗎？

比如這樣的：AaBB，BBAa。

再比如我之前《震驚！ConcurrentHashMap裡面也有死循環？》這篇文章中出現過的例子，AaAa，BBBB：

你看，神奇的事情就出現了。

我們有了 4 個 hashCode 一樣的字元串了。

有了這 4 個字元串，我們再去和 Aa，BB 進行組合，比如 AaBBAa，BBAaBB…

4*2=8 種組合方式，我們又能得到 8 個 hashCode 一樣的字元串了。

等等，我好像發現了什麼規律似的。

如果我們以 Aa，BB 為種子資料，經過多次排列組合，可以得到任意個數的 hashCode 一樣的字元串。字元串的長度随着個數增加而增加。

文字我還說不太清楚，直接 show you code 吧，如下：

public class CreateHashCodeSomeUtil {

    /**
     * 種子資料：兩個長度為 2 的 hashCode 一樣的字元串
     */
    private static String[] SEED = new String[]{"Aa", "BB"};
    
    /**
     * 生成 2 的 n 次方個 HashCode 一樣的字元串的集合
     */
    public static List<String> hashCodeSomeList(int n) {
        List<String> initList = new ArrayList<String>(Arrays.asList(SEED));
        for (int i = 1; i < n; i++) {
            initList = createByList(initList);
        }
        return initList;
    }

    public static List<String> createByList(List<String> list) {
        List<String> result = new ArrayList<String>();
        for (int i = 0; i < SEED.length; ++i) {
            for (String str : list) {
                result.add(SEED[i] + str);
            }
        }
        return result;
    }
}
           

通過上面的代碼，我們就可以生成任意多個 hashCode 一樣的字元串了。

就像這樣：

是以，别再問出這樣的問題了：

有了這些 hashCode 一樣的字元串，我們把這些字元串都放到HashMap 中，代碼如下：

public class HashMapTest {
    public static void main(String[] args) {
        Map<String, String> hashMap = new HashMap<String, String>();
        hashMap.put("Aa", "Aa");
        hashMap.put("BB", "BB");
        hashMap.put("AaAa", "AaAa");
        hashMap.put("AaBB", "AaBB");
        hashMap.put("BBAa", "BBAa");
        hashMap.put("BBBB", "BBBB");
        hashMap.put("AaAaAa", "AaAaAa");
        hashMap.put("AaAaBB", "AaAaBB");
        hashMap.put("AaBBAa", "AaBBAa");
        hashMap.put("AaBBBB", "AaBBBB");
        hashMap.put("BBAaAa", "BBAaAa");
        hashMap.put("BBAaBB", "BBAaBB");
        hashMap.put("BBBBAa", "BBBBAa");
        hashMap.put("BBBBBB", "BBBBBB");
    }
}
           

最後這個 HashMap 的長度會經過兩次擴容。擴容之後數組長度為 64：

但是裡面隻被占用了三個位置，分别是下标為 0,31,32 的地方：

畫圖如下：

看到了吧，刺不刺激，長度為 64 的數組，存 14 個資料，隻占用了 3 個位置。

這空間使用率，也太低了吧。

是以，這樣就算是 hack 了 HashMap。恭喜你，掌握了一項黑客攻擊技術：hash 沖突 Dos 。

如果你想了解的更多。可以看看石頭哥的這篇文章：《沒想到 Hash 沖突還能這麼玩，你的服務中招了嗎？》。

看到上面的圖，不知道大家有沒有覺得有什麼不對勁的地方？

如果沒有，那麼我再給你提示一下：數組下标為 32 的位置下，挂了一個長度為 8 的連結清單。

是不是，恍然大悟了。在 JDK 8 中，連結清單轉樹的門檻值是多少？

是以，在目前的案例中，數組下标為 32 的位置下挂的不應該是一個連結清單，而是一顆紅黑樹。

對不對？

對個錘子對！有的同學，上課不認真，稍不留神就被帶偏了。

這是不對的。連結清單轉紅黑樹的門檻值是節點大于 8 個，而不是等于 8 的時候。

也就是說需要再來一個經過 hash 計算後，下标為 32 的、且 value 和之前的 value 都不一樣的 key 的時候，才會觸發樹化操作。

不信，我給你看看現在是一個什麼節點：

沒有騙你吧？從上面的圖檔可以清楚的看到，第 8 個節點還是一個普通的 node。

而如果是樹化節點，它應該是長這樣的：

不信，我們再多搞一個 hash 沖突進來，帶你親眼看一下，代碼是不會騙人的。

那麼怎麼多搞一個沖突出來呢？

最簡單的，這樣寫：

這樣沖突不就多一個了嗎？我真是一個天才，情不自禁的給自己鼓起掌來。

好了，我們看一下現在的節點狀态是怎麼樣的：

怎麼樣，是不是變成了 TreeNode ，沒有騙你吧？

另外，我還想多說一句，關于一個 HashMap 的面試題的一個坑。

面試官問：JDK 8 的 HashMap 連結清單轉紅黑樹的條件是什麼？

絕大部分背過面試八股文的朋友肯定能答上來：當連結清單長度大于 8 的時候。

這個回答正确嗎？

是正确的，但是隻正确了一半。

還有一個條件是數組長度大于 64 的時候才會轉紅黑樹。

源碼裡面寫的很清楚，數組長度小于 64，直接擴容，而不是轉紅黑樹：

感覺很多人都忽略了“數組長度大于 64 ”這個條件。

背八股文，還是得背全了。

比如下面這種測試用例：

它們都會落到數組下标為 0 的位置上。

當第 9 個元素 BBBBAa 落進來的時候，會走到 treeifyBin 方法中去，但是不會觸發樹化操作，隻會進行擴容操作。

因為目前長度為預設長度，即 16。不滿足轉紅黑樹條件。

是以，從下面的截圖，我們可以看到，标号為 ① 的地方，數組長度變成了 32，連結清單長度變成了 9 ，但是節點還是普通 node：

怎麼樣，有點意思吧，我覺得這樣學 HashMap 有趣多了。

實體類當做 key

上面的示例中，我們用的是 String 類型當做 HashMap 中的 key。

這個場景能覆寫我們開發場景中的百分之 95 了。

但是偶爾會有那麼幾次，可能會把實體類當做 key 放到 HashMap 中去。

注意啊，面試題又來了：在 HashMap 中可以用實體類當對象嗎？

那必須的是可以的啊。但是有坑，注意别踩進去了。

我拿前段時間看到的一個新聞給大家舉個例子吧：

假設我要收集學生的家庭資訊，用 HashMap 存起來。

那麼我的 key 是學生對象， value 是學生家庭資訊對象。

他們分别是這樣的：

public class HomeInfo {

    private String homeAddr;
    private String carName;
     //省略改造方法和toString方法
}

public class Student {

    private String name;
    private Integer age;
     //省略改造方法和toString方法

}
           

然後我們的測試用例如下：

public class HashMapTest {

    private static Map<Student, HomeInfo> hashMap = new HashMap<Student, HomeInfo>();

    static {
        Student student = new Student("why", 7);
        HomeInfo homeInfo = new HomeInfo("大南街", "自行車");
        hashMap.put(student, homeInfo);
    }

    public static void main(String[] args) {
        updateInfo("why", 7, "濱江路", "摩托");
        for (Map.Entry<Student, HomeInfo> entry : hashMap.entrySet()) {
            System.out.println(entry.getKey()+"-"+entry.getValue());
        }
    }

    private static void updateInfo(String name, Integer age, String homeAddr, String carName) {
        Student student = new Student(name, age);
        HomeInfo homeInfo = hashMap.get(student);
        if (homeInfo == null) {
            hashMap.put(student, new HomeInfo(homeAddr, carName));
        }
    }
}
           

初始狀态下，HashMap 中已經有一個名叫 why 的 7 歲小朋友了，他家住大南街，家裡的交通工具是自行車。

然後，有一天他告訴老師，他搬家了，搬到了濱江路去，而且家裡的自行車換成了機車。

于是老師就通過頁面，修改了 why 小朋友的家庭資訊。

最後調用到了 updateInfo 方法。

嘿，你猜怎麼着？

我帶你看一下輸出：

更新完了之後，他們班上出現了兩個叫 why 的 7 歲小朋友了，一個住在大南街，一個住在濱江路。

更新變新增了，你說神奇不神奇？

現象出來了，那麼根據現象定位問題代碼不是手到擒來的事兒？

很明顯，問題就出在這個地方：

這裡取出來的 homeInfo 為空了，是以才會新放一個資料進去。

那麼我們看看為啥這裡為空。

跟着 hashMap.get() 源碼進去瞅一眼：

标号為 ① 的地方是計算 key ，也就是 student 對象的 hashCode。而我們 student 對象并沒有重寫 hashCode，是以調用的是預設的 hashCode 方法。

這裡的 student 是 new 出來的：

是以，這個 student 的 hashCode 勢必和之前在 HashMap 裡面的 student 不是一樣的。

是以，标号為 ③ 的地方，經過 hash 計算後得出的 tab 數組下标，對應的位置為 null。不會進入 if 判斷，這裡傳回為 null。

那麼解決方案也就呼之欲出了：重寫對象的 hashCode 方法即可。

是嗎？

等等，你回來，别拿着半截就跑。我話還沒說完呢。

接着看源碼：

HashMap put 方法執行的時候，用的是 equals 方法判斷目前 key 是否與表中存在的 key 相同。

我們這裡沒有重寫 equals 方法，是以這裡傳回了 false。

是以，如果我們 hashCode 和 equals 方法都沒有重寫，那麼就會出現下面示意圖的情況：

如果，我們重寫了 hashCode，沒有重寫 equals 方法，那麼就會出現下面示意圖的情況：

總之一句話：在 HashMap 中，如果用對象做 key，那麼一定要重寫對象的 hashCode 方法和 equals 方法。否則，不僅不能達到預期的效果，而且有可能導緻記憶體溢出。

比如上面的示例，我們放到循環中去，啟動參數我們加上 -Xmx10m，運作結果如下：

因為每一次都是 new 出來的 student 對象，hashCode 都不盡相同，是以會不停的觸發擴容的操作，最終在 resize 的方法抛出了 OOM 異常。

奇怪的知識又增加了

寫這篇文章的時候我翻了一下《Java 程式設計思想(第 4 版)》一書。

奇怪的知識又增加了兩個。

第一個是在這本書裡面，對于 HashMap 裡面放對象的示例是這樣的：

Groundhog：土撥鼠、旱獺。

Prediction：預言、預測、預告。

考慮一個天氣預報系統，将土撥鼠和預報聯系起來。

這 TM 是個什麼讀不懂的神仙需求？

幸好 why 哥學識淵博，閉上眼睛，去我的知識倉庫裡面搜尋了一番。

原來是這麼一回事。

在美國的賓西法尼亞州，每年的 2 月 2 日，是土撥鼠日。

根據民間的說法，如果土撥鼠在 2 月 2 号出洞時見到自己的影子，然後這個小東西就會回到洞裡繼續冬眠，表示春天還要六個星期才會到來。如果見不到影子，它就會出來覓食或者求偶，表示寒冬即将結束。

這就呼應上了，通過判斷土撥鼠出洞的時候是否能看到影子，進而判斷冬天是否結束。

這樣，需求就說的通了。

第二個奇怪的知識是這樣的。

關于 HashCode 方法，《Java程式設計思想(第4版)》裡面是這樣寫的：

我一眼就發現了不對勁的地方：result=37*result+c。

前面我們才說了，基數應該是 31 才對呀？

作者說這個公式是從《Effective Java（第1版）》的書裡面拿過來的。

這兩本書都是 java 聖經啊，建議大家把夢幻關聯打在留言區上。

《Effective Java（第1版）》太久遠了，我這裡隻有第 2 版和第 3 版的實體書。

于是我在網上找了一圈第 1 版的電子書，終于找到了對應描述的地方：

可以看到，書裡給出的公式确實是基于 37 去計算的。

翻了一下第三版，一樣的地方，給出的公式是這樣的：

而且，你去網上搜：String 的 hashCode 的計算方法。

都是在争論為什麼是 31 。很少有人提到 37 這個數。

其實，我猜測，在早期的 JDK 版本中 String 的 hashCode 方法應該用的是 37 ，後來改為了 31 。

我想去下載下傳最早的 JDK 版本去驗證一下的，但是網上翻了個底朝天，沒有找到合适的。

書裡面為什麼從 37 改到 31 呢？

作者是這樣解釋的，上面是第 1 版，下面是第 2 版：

用方框框起來的部分想要表達的東西是一模一樣的，隻是對象從 37 變成了 31 。

而為什麼從 37 變成 31 ，作者在第二版裡面解釋了，也就是我用下劃線标注的部分。

31 有個很好的特許，即用位移和減法來代替乘法，可以得到更好的性能：

31*i==（i<<5）-1。現代的虛拟機可以自動完成這種優化。

從 37 變成 31，一個簡單的數字變化，就能帶來性能的提升。

個中奧秘，很有意思，有興趣的可以去查閱一下相關資料。

真是神奇的計算機世界。

好了，這次的文章就到這裡啦。

才疏學淺，難免會有纰漏，如果你發現了錯誤的地方，可以在留言區提出來，我對其加以修改。

感謝您的閱讀，我堅持原創，十分歡迎并感謝您的關注。

我是 why 哥，一個被代碼耽誤的文學創作者，不是大佬，但是喜歡分享，是一個又暖又有料的四川好男人。

歡迎關注我呀。