Java面試官的ConcurrentHashMap源碼奪命15問，你能堅持幾個？

今日分享開始啦，請大家多多指教~

本篇總結的是 ConcurrentHashMap 相關的面試題，臨近秋招，備戰暑期實習，祝大家進步多多！

1、請你描述一下ConcurrentHashMap儲存資料結構是什麼樣子呢？

ConcurrentHashMap 內部的 map 結構和 HashMap 是一致的，都是由：陣列 + 連結串列 + 紅黑樹 構成。ConcurrentHashMap 儲存資料的單元和 HashMap 也是一致的，即，Node 結構：

ConcurrentHashMap 和 HashMap 區別就在於前者支援併發擴容，其內部通過加鎖（自旋鎖 + CAS + synchronized + 分段鎖）來保證執行緒安全。2、請問ConcurrentHashMap的負載因子可以新指定嗎？

普通的 HashMap 的負載因子可以修改，但是 ConcurrentHashMap 不可以，因為它的負載因子使用 final關鍵字修飾，值是固定的 0.75 ：

負載因子：表示散列表的填滿程度~ 在ConcurrentHashMap中，該屬性是固定值0.75，不可修改~

private static final float LOAD_FACTOR = 0.75f;

3、請問節點的 Node.hash 欄位一般情況下必須 >=0 這是為什麼？

或者說，Node 節點的 hash 值有幾種情況？針對不同情況分析一下？

如果 Node.hash = -1，表示當前節點是 **FWD(ForWardingNode) **節點(表示已經被遷移的節點)。如果 Node.hash = -2，表示當前節點已經樹化，且當前節點為 TreeBin 物件，TreeBin 物件代理操作紅黑樹。如果 Node.hash > 0，表示當前節點是正常的 Node 節點，可能是連結串列，或者單個 Node。4、簡述 ConcurrentHashMap 中 sizeCtl 欄位的作用（不同情況下的含義）？

sizeCtr 即 Size Control，這個欄位一定要仔細去理解一下，這個欄位看不懂，可能會整個 ConcurrentHashMap 源碼都一臉懵逼。

① sizeCtl == 0 時，表示的是什麼情況？

izeCtl == 0，是預設值，表示在真正第一次初始化散連結串列的時候使用預設容量 16 進行初始化。

② sizeCtl == -1 時，表示什麼情況呢？

sizeCtl == -1表示當前散連結串列正處於初始化狀態。有執行緒正在對當前散列表(table) 進行初始化操作。

ConcurrentHashMap 的散連結串列是延遲初始化的，在併發條件下必須確保只能初始化一次，所以 sizeCtl == -1 就相當於一個"標識鎖"，防止多個執行緒去初始化散列表。

具體初始化操作就是在initTable()方法中，會通過 CAS 的方式去修改 sizeCtl 的值為 -1，表示已經有執行緒正在對散連結串列進行初始化，其他執行緒不可以再次初始化，只能等待！

如果 CAS 修改 sizeCtl = -1 操作成功的執行緒，可以接著執行對散連結串列初始化的邏輯。而 CAS 修改失敗的執行緒，在這裡會不斷地自旋檢查，直到散連結串列初始化結束。

這裡 CAS 失敗的執行緒會走如下邏輯，即自旋的執行緒會通過Thread.yield();方法，短暫釋放 CPU 資源，把 CPU 資源讓給更飢餓的執行緒去使用。目的是為了減輕自旋對CPU 效能的消耗。

③ 初始化完散列表後，map.sizeCtl > 0 時，表示什麼情況呢？

sizeCtl > 0 時，表示初始化或擴容完成後下一次觸發擴容的閾值。

比如，sizeCtl = 12 時，當散連結串列中資料的個數 >=12 時，就會觸發擴容操作。

④ sizeCtl < 0 && sizeCtl != -1 時，代表什麼情況呢？

sizeCtl < 0 && sizeCtl != -1 時，表示當前散連結串列正處於擴容狀態。

-(1 + nThreads)，表示有n個執行緒正在一起擴容。

這時候，sizeCtl 的高 16 位表示擴容標識戳，低 16 位表示參與併發擴容執行緒數：1 + nThread， 即當前參與併發擴容的執行緒數量為 n 個。

5、請你說一下擴容標識戳的作用及其計算方式？

根據老表的長度 tab.length 去獲取擴容唯一標識戳。

假設 16 -> 32 這樣擴容，那麼擴容標識戳的作用就是在多執行緒併發擴容條件下，所有 16 -> 32 擴容的執行緒都可以參與併發擴容。

sizeCtl < 0 && sizeCtl != -1 時，這時候sizeCtl 的高 16 位就表示擴容標識戳，低 16 位表示參與併發擴容執行緒數：1 + nThread， 即當前參與併發擴容的執行緒數量為 n 個。

6、ConcurrentHashMap如何保證寫資料執行緒安全？

這個問題其實就是問，向 ConcurrentHashMap 中新增資料確保執行緒安全是如何實現的。

ConcurrentHashMap 內部通過加鎖（自旋鎖 + CAS + synchronized + 分段鎖）來保證執行緒安全。

新增資料具體流程如下：

① 首先，先判斷散連結串列是否已經初始化，如果沒初始化則先初始化散連結串列，再進行寫入操作。

② 當向桶位中寫資料時，先判斷桶中是否為空，如果是空桶，則直接通過 CAS 的方式將新增資料節點寫入桶中。如果 CAS 寫入失敗，則說明有其他執行緒已經在當前桶位中寫入資料，當前執行緒競爭失敗，回到自旋位置，自旋等待。

如果當前桶中不為空，就需要判斷當前桶中頭結點的類型：

③ 如果桶中頭結點的 hash 值 為 -1，表示當前桶位的頭結點為 FWD 結點，目前散連結串列正處於擴容過程中。這時候當前執行緒需要去協助擴容。

④ 如果 ②、③ 條件不滿足，則表示當前桶位的存放的可能是一條連結串列，也可能是紅黑樹的代理物件 TreeBin。這種情況下會使用 synchronized 鎖住桶中的頭結點，來保證桶內的寫操作是執行緒安全的。

7、描述一下ConcurrentHashMap中的hash定址演算法

ConcurrentHashMap 的定址演算法和 HashMap 差別不大：

首先是通過 Node 節點的 Key 獲取到它的 HashCode 值，再將 HashCode值通過 spread(int h)方法進行繞道運算，進而得到最終的 Hash 值。

獲取到最終的 hash 值之後，再通過定址公式：index = (tab.length -1) & hash 獲得桶位下標。

8、ConcurrentHashMap如何統計當前散列表中的資料量?

ConcurrentHashMap 統計儲存資料的數量是通過 addCount(long x, int check) 方法實現的，本質上是藉助了 LongAdder 原子類。

ConcurrentHashMap為什麼不採用 ConcurrentHashMap為什麼不採用 AtomicLong 統計散列表資料量呢？統計散列表資料量呢？

因為 AtomicLong 原子類自增操作是基於 CAS 實現的，基於 CAS 實現會導致一個問題，就是當大量執行緒同時執行 CAS 操作時，只能有一個執行緒執行成功，而其他所有執行緒都會因為失敗而進入自旋狀態，自旋本身就是一個 while(true) 的迴圈，非常耗費系統資源。

那麼 LongAdder 是如何保證大併發量下，效能依舊高效呢？

先看下LongAdder的操作原理圖：

LongAdder採用"分段"的方式降低CAS失敗的頻次，典型的用空間換時間：

LongAdder有一個全局變數volatile long base;值，當併發不高的情況下都是通過CAS來直接操作base值，如果CAS失敗，則針對LongAdder中的Cell[]陣列中的Cell進行CAS操作，減少失敗的概率。

如當前類中base = 10，有三個執行緒進行CAS原子性的 加1操作，執行緒一執行成功，此時base=11，執行緒二、執行緒三執行失敗後開始針對於Cell[]陣列中的Cell元素進行加1操作，同樣也是CAS操作，此時陣列index=1和index=2中Cell的value都被設定為了1。

執行完成後，統計累加資料：sum = 11 + 1 + 1 = 13，利用LongAdder進行累加的操作就執行完了，流程圖如下：

9、觸發擴容條件的執行緒，執行的預處理工作都有哪些？

首先，觸發擴容條件的執行緒，要做的第一件事就是通過 CAS 的方式修改 sizeCtl 欄位值，使其高 16 位為擴容唯一標識戳，低 16 位為(參與擴容的執行緒數 + 1)，表示有執行緒正在進行擴容邏輯！

注意：這裡高 16 位的擴容唯一標識戳是根據當前散連結串列的長度計算得來，其最高位是 1。那麼最終得到的 sizeCtl 就應該是一個負數。

然後，當前觸發擴容條件的執行緒會創建一個新的散連結串列，大小為原來舊散連結串列的 2 倍。並且將新散連結串列的引用賦給 map.nextTable 欄位。

又因為 ConcurrentHashMap 是支援多執行緒併發擴容的，所以需要讓協助擴容的執行緒知道舊散連結串列資料遷移到新散連結串列的進度。為此 ConcurrentHashMap 提供了一個 transferIndex 欄位，用於記錄舊散連結串列資料的總遷移進度！遷移工作進度是從 高位桶開始，一直遷移到下標是 0 的桶位。

10、舊散連結串列中遷移完畢後的桶，如何做標記？

舊散連結串列中遷移完畢的桶，需要用 ForwardingNode 物件表示桶內節點，這種 Node 比較特殊，是用來表示當前桶中的資料已經被遷移到新散連結串列的桶中去了。

ForwardingNode 有哪些作用？

ForwardingNode 物件內部提供了一個用於向新散連結串列中查詢目標資料的find()方法。當此時某個執行緒剛好在舊散連結串列中查詢目標元素時，剛好遇到當前桶位中存放的是 FWD 節點，那麼就可以通過 FWD 節點的 find() 方法重新定向到新散連結串列中去查詢目標元素！11、如果散列表正在庫容時，再來新的寫入請求該如何處理呢？

這裡要分兩種情況考慮：

如果當前執行緒執行寫入操作時，根據定址演算法訪問到的桶中不是 FWD 節點(即，當前桶中資料沒有被遷移)。那麼此時先判斷桶中是否為空，如果為空則 CAS 方式寫入資料。而如果桶不為空，則可能是連結串列或者 TreeBin，這時候需要通過 synchronized 關鍵字鎖住桶的頭結點再進行寫入操作。而如果如果當前執行緒執行寫入操作時，根據定址演算法訪問到的桶中是 FWD 節點(即，當前桶中資料已經被遷移)。碰到 FWD 節點，說明此時散連結串列正在進行擴容，這時候需要當前執行緒也加入進去，去協助散連結串列擴容（helpTransfer(tab, f);協助擴容是為了儘量減少擴容所花費在資料遷移上的時間）。

當前執行緒加入到協助擴容中後，ConcurrentHashMap 會根據全局的transferIndex欄位去給當前執行緒分配遷移工作任務（需要負責遷移舊散連結串列的桶位區間）。例如，讓當前執行緒負責遷移舊散連結串列中 【0-4】桶位上的資料到新散連結串列。

一直到當前執行緒分配不到要負責遷移的任務時，則退出協助擴容，即擴容結束。這時候，當前執行緒就可以繼續執行寫入資料的邏輯了！

12、擴容期間，擴容工作執行緒如何維護sizeCtl的低16位呢？

每一個執行擴容任務的執行緒(包含協助擴容)，它在開始工作之前，都會更新 sizeCtl的低 16 位，即讓低 16 位 +1，說明又加入一個新的執行緒去執行擴容。

每個執行擴容的執行緒都會被分配一個遷移工作任務區間，如果當前執行緒所負責的任務區間遷移工作完成了，沒有再被分配遷移任務區間，那麼此時當前執行緒就可以退出協助擴容了，這時候更新 sizeCtl的低 16 位，即讓低 16 位 -1，說明有一個執行緒退出併發擴容了。

如果 sizeCtl 低 16 位-1後的值為 1，則說明當前執行緒是最後一個退出併發擴容的執行緒。

13、如果再來新的寫執行緒請求該怎麼處理？

當桶位中連結串列升級為紅黑樹，且當前紅黑樹上有讀執行緒正在訪問：

寫執行緒會被阻塞，因為紅黑樹比較特殊，新寫入資料，可能會觸發紅黑樹的自平衡，這就會導致樹的結構發生變化，會影響讀執行緒的讀取結果！

在紅黑樹上讀取資料和寫入資料是互斥的，具體原理分析如下：

我們知道 ConcurrentHashMap 中的紅黑樹由 TreeBin 來代理，TreeBin 內部有一個 Int 類型的 state 欄位。當讀執行緒在讀取資料時，會使用 CAS 的方式將 state 值 +4（表示加了讀鎖），讀取資料完畢後，再使用CAS 的方式將 state 值 -4。如果寫執行緒去向紅黑樹中寫入資料時，會先檢查 state 值是否等於 0，如果是 0，則說明沒有讀執行緒在檢索資料，這時候可以直接寫入資料，寫執行緒也會通過 CAS 的方式將 state 欄位值設定為 1（表示加了寫鎖）。如果寫執行緒檢查 state 值不是 0，這時候就會park()掛起當前執行緒，使其等待被喚醒。反過來，當紅黑樹上有寫執行緒正在執行寫入操作，那麼如果有新的讀執行緒請求該怎麼處理？

TreeBin 物件內部保留了一個連結串列結構，就是為了這種情況而設計的。這時候會讓新來的讀執行緒到連結串列上去訪問資料，而不經過紅黑樹。

14、掛起等待的寫執行緒後，什麼時候將其喚醒再繼續執行寫操作呢？

上一個問題中，我們分析了：當讀執行緒在讀取資料時，會使用 CAS 的方式將 state 值 +4（表示加了讀鎖），讀取資料完畢後，再使用CAS 的方式將 state 值 -4。

當 state 值減去 4 後，讀執行緒會先檢查一下 state 值是不是 2，如果是 2 ，則說明有等待被喚醒的寫執行緒在掛起等候，這時候呼叫 unsafe.unpark() 方法去喚醒該寫執行緒。

15、 請你說一下ConcurrentHashMap中的lastRun機制？

今日份分享已結束，請大家多多包涵和指點！