前言

我是fancy，一個年紀輕輕bug量就累計到3200個的程序員，同事們都夸我一個人養活了整個測試組。

最近迷上了并發編程。并發這玩意怎么說呢，就是你平時工作用不到，一用就用在面試上。這不，又卷起了并發容器。

那說起并發容器，你一定也知道那幾個，CopyOnWriteArrayList、并發隊列BlockingQueue，等等。但是作為面試的典中典，聊到并發容器就無法繞開ConcurrentHashMap。

由于篇幅原因，這篇文章不會具體解釋那些較為基礎的問題，比如為什么散列表數組的長度一定要是2的n次方等。將更多圍繞并發這?個話題。如有需要，之后會另外講解。

所以本文我們就來深入聊聊這個大廠面試青睞的對象，八股文里的蘭博基尼：ConcurrentHashMap。

以下的技術點都基于JDK1.8~

基礎回顧

我們都知道，從JDK1.8起，ConcurrentHashMap底層的數據結構就已經從原來的Segment分段鎖變為了數組 + 鏈表 + 紅黑樹的形態。

它是一款并發容器，一款裝數據的容器在并發環境下鐵定就會有各種各樣的問題。你在單線程環境下玩單機，并發環境下就會有別的線程和你搶數據，搶桶位。因此編寫JUC包的大神Doug Lea也都為這些場景一一做了適配，可以說是絕對的并發安全，至少運行了這么多年了也沒遇到什么bug。

紅黑樹

紅黑樹數據結構

JDK1.8這里的紅黑樹，準確的來說是一個TreeBin代理類，它作為紅黑樹的具體實現起存儲作用，而TreeNode是封裝紅黑樹的數據結構，所以你可以理解TreeBin就是封裝TreeNode的一個容器。

紅黑樹在ConcurrentHashMap里面的體現是一個雙向鏈表：

紅黑樹插入數據

在這里，紅黑樹維護一個字段dir。

在插入數據的時候會獲取節點的hash值，從而與當前節點p的hash值比較，若插入節點的hash小于當前節點，則dir的值為-1，否則為1：

所以，當dir的值為-1時，就代表插入節點需要插入到當前節點的左子節點或者繼續往左子樹上查找，相反如果dir值為1則向右查找，這里的規則和二叉查找樹的規則是一樣的。

多線程競爭下的讀寫操作

由于讀操作本身就是天然線程安全的。所以多個線程對同一個桶位同時讀并不會有什么問題。

但若是相互競爭的寫操作，就是通過Synchronized鎖的方式來保證某個桶位同一時刻只有一個線程能獲取到資源。

通過源碼可以看到，put()方法的核心是putVal():

putVal()很長，它主要是通過Synchronized去鎖住每一個節點保證并發的安全性。在這里最為重要的兩點，一是判斷你put進去的這個元素，是處于鏈表還是處于紅黑樹上；二就是判斷當前插入的key是否與鏈表或者紅黑樹上的某個元素一致。如果當前插入key與鏈表當中所有元素的key都不一致時，那么當前的插入操作就追加到鏈表的末尾。否則就替換掉key對應的value。

擴容原理

在知道擴容原理之前，得知道什么情況會導致擴容。

因此需要知道的兩個重要字段：

• MIN_TREEIFY_CAPACITY ：數組初始長度，默認為64
• TREEIFY_THRESHOLD ：樹化閾值，指定桶位鏈表長度達到8的話，就可能發生樹化操作

線程往桶里面新增每一個元素，都會對鏈表的長度進行判斷，只有元素個數大于閾值MIN_TREEIFY_CAPACITY并且鏈表長度大于8，才會調用treeifyBin()把鏈表轉化為紅黑樹，否則就會進行擴容操作。

這里的擴容，指的就是擴大數組的桶個數，從而裝下更多的元素。

除此之外，擴容還維護了另一重要的字段，sizeCtl：

通過翻譯，我們可以知道這個字段有三種狀態：

• sizeCtl < 0：若為-1則起標記作用，告知其它線程此時正在初始化；若為其它的值表示當前table正在擴容
• sizeCtl = 0：表示創建table數組時還未進行擴容，沒有指定的初始容量
• sizeCtl > 0：表示當table初始化后下次擴容的觸發條件

字段的值可以轉化為32位的二進制數值，它的高16位表示擴容標識戳，用來標識擴容的范圍，如從長度16擴容到32；低16位表示當前參與擴容的線程數量。

擴容操作會新建一個長度更大的數組，然后將老數組上的元素全部遷移到新的數組去。

擴容的本質目的是為了減少桶位鏈表的長度，提高查詢效率。因為鏈表的查詢復雜度是O(n)，如果鏈表過長就會影響查詢效率。

假設桶位的長度從16擴容到32，說明桶位變多了，那遷移到新數組后就需要有元素去到新的桶位。這就需要通過一些算法將老數組和新數組的元素位置做一個映射。因為擴容后元素有的需要遷移到新的位置，有的還是處于和老數組一樣的位置，只不過是換了一個數組。

如何計算出這個元素遷移后要呆在哪個桶位呢？這里使用了一個按位與的算法。就是將這個桶位key的hash值 & (擴容前數組長度 - 1)，若生成的值等于0則不需要遷移，否則就要進行遷移。并且維護兩個變量ln和hn代表是否需要進行位置遷移。然后采用尾插法將元素插入。這就是LastRun機制。

注：尾插法指的就是后面插入的元素都處于前一個元素的后面

這里簡單普通的擴容是沒什么問題的，大多數場景都和HashMap的擴容是一樣的。

問題就在于當前是處于并發環境的，而擴容也需要時間。

正在擴容 && 有多個線程正在競爭

所以，比較復雜的場景來了。若是桶位正在擴容，且有多個線程正在競爭讀寫咋辦？厚禮謝

沒關系，我們依然分情況來討論。

擴容期間的讀操作

如果擴容期間，有線程進行元素的讀取，比如你去get()某個key的value，那讀不讀的到呢？

答案是可以。但是前提是你這個節點已經遷移結束，如果你是一個正在擴容遷移的節點，那就訪問不到。

具體的操作，就是去調用find()。

當一個桶位要進行數據遷移，就會往這個桶位上放置一個ForwardingNode節點。除此之外還需要去標識這個節點是正在遷移還是已經遷移結束了的；

在這里我們統稱遷移前的桶位節點叫老節點，遷移后的桶位節點叫新節點。當其中某一個節點遷移完成后，就會在老節點上添加一個fwd引用，它指向新節點的地址。

所以當某個線程訪問了這個節點，看到它上面存在fwd引用，就說明當前table正在擴容，那么就會根據這個引用上的newtable字段去新數組的對應桶位上找到數據然后返回。

擴容期間的寫操作

寫操作相較于讀操作會更加復雜一點，原因就是讀操作只需要獲取對應數據返回就行了，而寫操作還要修改數據，所以當一個寫線程來修改數據剛好碰到容器處于擴容期間，那么它還要協助容器進行擴容。

具體的擴容操作依然還要分情況，假如訪問的桶位數據還沒有被遷移走的話，那就直接競爭鎖，然后在老節點上進行操作就行。

但是假如線程修改的節點正好是一個fwd節點，說明當前節點正處于擴容操作，那么為了節約線程數并且快速完成任務，當前線程就會進行協助擴容。如果有多個線程進行同時寫，那么它們都會調用helpTransfer()進行協助擴容。

這里協助擴容的方式就是拿到一個擴容標識戳，這個標識戳的作用就是用來標識擴大的容量大小。因為每個線程都是獨立的嘛，互不通信，但是它們要做的事情是相同的，就是將桶位擴大相同的值，所以它們就必須拿到這個相同的標識戳，只有標識戳一致才會進行擴容。

假設一個容器從16個桶位擴容到32個桶位，有線程A、B兩個線程。

若A觸發了擴容的機制，那么線程A就會進行擴容，此時線程B也來進行寫操作，發現正在擴容就會進入到協助擴容的步驟中去。

所以線程A和線程B共同負責桶位的擴容。

一個線程負責擴容的桶位個數，是根據CPU核心數來算的。最少是16個，也就是一個線程最少要負責16個元素的擴容：

我們在上面有提過，sizeCtl轉化為32位后，它的低16位是表示當前參與擴容的線程數量。所以當A線程觸發了擴容之后，它就會將sizeCtl低16位的最后一位值+1，表示擴容線程多了一位，當它退出擴容時又會將最后一位的值-1，表示擴容線程少了一位，就這樣各個線程共同維護這個字段。

所以你一定會好奇了：那我要是最后一個退出擴容的線程要怎么維護啊？是的，最后一個線程還有一些別的事情要做。當某一個線程完成任務后去判斷sizeCtl的值得時候，發現它的低16位只剩下最后一位是1，再減下去就是0了，那就代表它是最后一個退出擴容的線程。此時它還需要去檢查一遍老的table數組，判斷是否還有遺漏的slot沒有遷移。具體的操作就是去輪詢檢查是否還留有fwd節點，如果沒有的話代表遷移完成，如果有的話還需要繼續將它遷移到新的桶位。

由于源碼非常長，所以我們就不貼全部源碼了，通過流程圖的方式來幫助大家理解這個擴容期間的操作：

總結

有的童鞋在看Juc這一塊的時候會去背誦源碼，將方法的調用鏈都講的頭頭是道，我認為沒有必要，相反面試官可能會覺得你過于抽象，背的這么清楚。并發的核心在于如何用手段去解決可能遇到的安全問題，并且讓它更高效點，面試的目的也是為了體現你思維能力。