那些年你啃過的ConcurrentHashMap
前言
我是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這一塊的時候會去背誦源碼，將方法的調用鏈都講的頭頭是道，我認為沒有必要，相反面試官可能會覺得你過於抽象，背的這麼清楚。並發的核心在於如何用手段去解決可能遇到的安全問題，並且讓它更高效點，面試的目的也是為了體現你思維能力。
如果覺得本文有所收穫，可以點贊支援一下呀~
