問題1：HashMap的數據結構是什麼樣的？

同學1：嗯...數組+鏈表

同學2：數組+鏈表...

同學3：數組+鏈表...

同學4：數組+鏈表+紅黑樹...

同學n：.....

為什麼答案會有兩種？難道大家學習的HashMap有兩個版本？我突然想起馬克思哲學裡面的一句話，真理是相對的，不是絕對的，變化才是唯一的真理。

不錯，對於Java這種語言排行榜經常排於榜首的高級語言，變化也是它的生存之道。Java在推出新版本的同時，不斷的完善重要class的數據結構，提升它的性能，穩固它的安全性。HashMap就是其中之一。

HashMap在Java1.7裡使用的是數組+鏈表的數據結構，在Java1.8裡使用的是數組+鏈表+紅黑樹。

問題2：HashMap為什麼在1.8的版本，對它的數據結構進行了修改？

同學1：嗯，有bug（標準的程序員思維）

同學2：有漏洞...(有黑客思維的同學)

同學3：沒事，無聊，寂寞，想搞事情...(有創業者思維的同學)

同學4：提升性能...(有架構師思維的同學)

......

Java在維護它全球頂級語言，近趨於霸主地位的時候，當然要從細節入手，從源碼入手，完善它的性能，修復它的漏洞。Java如此，其他語言也是如此。

問題3：HashMap在1.7和1.8，性能上究竟有了多大的提升，我們上代碼，看看速度如何？

測試結果如下：

我們可以清楚的看見HashMap在1.8的版本，數據量非常大（10萬條）的時候，查詢的總時間明顯比較低，也就是說HashMap在1.8的版本查找速度很快，插入或者是刪除相對較慢。那麼為什麼會這樣？

思考題：為什麼HashMap在1.8的版本，查找速度有了大幅提升？

接下來，我將逐一帶大家進行全面剖析HashMap的數據結構。

一. 數據結構不同

1. HashMap在1.7的版本數據結構如下：

數組+鏈表（單向鏈表）

1.1 從數據結構我們來分析HashMap的put過程

插入元素的數據結構如下代碼：

第一步：計算key對應數組的index（索引），是通過hashcode & （length-1），就是hashcode值和（數組長度-1）的與運算。

第二步：將插入的元素放入數組index的位置，將next指針指向之前的元素。

圖解過程：

1.2 HashMap在1.7的版本的get過程

第一步：計算key對應數組的index（索引）,找到數組的頭結點

第二步：從頭結點逐個向下遍歷，直到key的hash值與節點的hash值碰撞相等，然後取出value值。

思考一下：get過程的時間複雜度應該是O(n)，試著想一下，如果我們在插入的過程中對節點進行一些變換，例如將單向鏈表變成二叉樹，或者是平衡二叉樹，是不是下次在查找的過程，就能減少遍歷的時間複雜度呢？

下面，我們引入HashMap在Java1.8裡的數據結構

2. HashMap在1.8的版本數據結構如下：

從源碼中分析：

我們來翻譯這句話：

HashMap處理“碰撞”增加了紅黑樹這種數據結構，當碰撞結點較少時，採用鏈表存儲，當較大時（>8個），採用紅黑樹（特點是查詢時間是O（logn））存儲（有一個閥值控制，大於閥值(8個)，將鏈表存儲轉換成紅黑樹存儲。

可能此時，對於數據結構，你會有知識斷層，那麼沒關係，我來為你一一介紹這些數據結構。

1. 數組，帶有索引的容器，固定長度(ArrayList中數據結構，自動擴容)

2. 雙向鏈表，如下圖（LinkedList）

3. 單向鏈表

4. 紅黑樹

特點：

1）每個節點非紅即黑

2）根節點是黑的;

3）每個葉節點（葉節點即樹尾端NULL指針或NULL節點）都是黑的;

4）如圖所示，如果一個節點是紅的，那麼它的兩兒子都是黑的;

5）對於任意節點而言，其到葉子點樹NULL指針的每條路徑都包含相同數目的黑節點;

6）每條路徑都包含相同的黑節點;

2.1 此時，我們分析一下HashMap在1.8版本里面的put過程

插入元素包含如下

1）單向鏈表，代碼如上面對應的1.7版本

2）紅黑樹

分析put過程

第一步：計算key對應數組的index（索引），是通過hashcode & （length-1），就是hashcode值和（數組長度-1）的與運算。

第二步：當前索引所對應的單向鏈表長度<=8時，將插入的元素放入數組index的位置，將next指針指向之前的元素。反之，則把當前索引所有的元素轉化為紅黑樹。

2.2 HashMap在1.8的版本的get過程

第一步：計算key對應數組的index（索引）,找到數組的頭結點

第二步：如果頭節點是單向鏈表結構，則從頭結點逐個向下遍歷，知道key的hash值與節點的hash值碰撞相等，然後取出value值。如果是紅黑樹，則用紅黑樹的遍歷，碰撞hash值，然後取出value值。

二. HashMap的擴容

當HashMap中的元素個數超過數組大小*loadFactor時，就會進行數組擴容，loadFactor的默認值為0.75，也就是說，默認情況下，數組大小為16，那麼當hashmap中元素個數超過16*0.75=12的時候，就把數組的大小擴展為2*16=32，即擴大一倍，然後重新計算每個元素在數組中的位置，而這是一個非常消耗性能的操作，所以如果我們已經預知hashmap中元素的個數，那麼預設元素的個數能夠有效的提高hashmap的性能。

比如說，我們有1000個元素new HashMap(1000), 但是理論上來講new HashMap(1024)更合適，不過上面已經說過，即使是1000，hashmap也自動會將其設置為1024。 但是new HashMap(1024)還不是更合適的，因為0.75*1000 < 1000, 也就是說為了讓0.75 * size > 1000, 我們必須這樣new HashMap(2048)才最合適，既考慮了&的問題，也避免了resize的問題。

總結：

一. HashMap在Java1.7的版本是數組+單向鏈表存儲，在1.8的版本是數組+單向鏈表+紅黑樹（如果當前索引對應的單向鏈表長度小於等於8，則用單向鏈表，如果大於8，則轉化為紅黑樹）

二. HashMap在1.8的版本中，大數據量的查找，性能有了提升，是因為在put的過程中，增加了紅黑樹的轉化，犧牲了put的時間和空間複雜度

三. HashMap的擴容過程，是個非常消耗性能的，擴容後的HashMap，需要重新計算之前數組各個索引對應的頭結點（根節點）在新數組中對應的索引。

粉絲福利，需獲取HashMap、分佈式、微服務、spring全家桶等最新相關架構資料

關注我+轉發此文+私信回覆關鍵詞:架構