ConcurrentHashMap源碼奪命15問，你能堅持到第幾問？

• 本篇總結的是 ConcurrentHashMap 相關的面試題，後續會每日更新~
• 對 ConcurrentHashMap 源碼不熟悉的可以參考我的往期部落格： ConcurrentHashMap源碼解析文章總目錄
• 卷嗎？卷就對了，Java 就是這麼卷卷單單！​

• 

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

ConcurrentHashMap 内部的 map 結構和 HashMap 是一緻的，都是由：數組 + 連結清單 + 紅黑樹 構成。

ConcurrentHashMap 存儲資料的單元和 HashMap 也是一緻的，即，Node 結構：

static class Node<K,V> implements Map.Entry<K,V> {
    // hash值
    final int hash;
    // key
    final K key;
    // value
    volatile V val;
    // 後驅節點
    volatile Node<K,V> next;
    
    ....
}
      

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，表示已經有線程正在對散連結清單進行初始化，其他線程不可以再次初始化，隻能等待！

// SIZECTL：期望值，初始為0
// this 就表示目前 ConcurrentHashMap對象
// sc 表示要修改的 sizeCtrl 
// -1 表示将 sc 修改為 -1
U.compareAndSwapInt(this, SIZECTL, sc, -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 擴容的線程都可以參與并發擴容。

// 固定值16，與擴容相關，計算擴容時會根據該屬性值生成一個擴容辨別戳
private static int RESIZE_STAMP_BITS = 16;

/**
 * table數組擴容時，計算出一個擴容辨別戳，當需要并發擴容時，目前線程必須拿到擴容辨別戳才能參與擴容：
 */
static final int resizeStamp(int n) {
    // RESIZE_STAMP_BITS：固定值16，與擴容相關，計算擴容時會根據該屬性值生成一個擴容辨別戳
    return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}
      

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 值。

/**
 * 計算Node節點hash值的算法：參數h為hash值
 * eg: 
 * h二進制為 -->                     1100 0011 1010 0101 0001 1100 0001 1110
 * (h >>> 16) -->                   0000 0000 0000 0000 1100 0011 1010 0101 
 * (h ^ (h >>> 16)) -->             1100 0011 1010 0101 1101 1111 1011 1011
 * 注：(h ^ (h >>> 16)) 目的是讓h的高16位也參與尋址計算，使得到的hash值更分散，減少hash沖突産生~
 * ------------------------------------------------------------------------------
 * HASH_BITS -->                    0111 1111 1111 1111 1111 1111 1111 1111
 * (h ^ (h >>> 16)) -->             1100 0011 1010 0101 1101 1111 1011 1011
 * (h ^ (h >>> 16)) & HASH_BITS --> 0100 0011 1010 0101 1101 1111 1011 1011
 * 注： (h ^ (h >>> 16))得到的結果再& HASH_BITS，目的是為了讓得到的hash值結果始終是一個正數
 */
static final int spread(int h) {
    // 讓原來的hash值異或^原來hash值的右移16位，再與&上HASH_BITS(0x7fffffff: 二進制為31個1)
    return (h ^ (h >>> 16)) & HASH_BITS;
}
      

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

8、ConcurrentHashMap如何統計目前散清單中的資料量?

ConcurrentHashMap 統計存儲資料的數量是通過 addCount(long x, int check) 方法實作的，本質上是借助了 LongAdder 原子類。（參考文章：LongAdder源碼解析）

ConcurrentHashMap為什麼不采用 ConcurrentHashMap為什麼不采用 AtomicLong 統計散清單資料量呢？統計散清單資料量呢？

因為 AtomicLong 原子類自增操作是基于 CAS 實作的，基于 CAS 實作會導緻一個問題，就是當大量線程同時執行 CAS 操作時，隻能有一個線程執行成功，而其他所有線程都會因為失敗而進入自旋狀态，自旋本身就是一個 while(true) 的循環，非常耗費系統資源。

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

先看下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進行累加的操作就執行完了，流程圖如下：

（圖檔參考自面試官問我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()挂起目前線程，使其等待被喚醒。挂起寫線程時，寫線程會先将 state 值的第 2 個 bit 位設定為 1（二進制為 10），轉換成十進制就是 2，表示有寫線程等待被喚醒。

反過來，當紅黑樹上有寫線程正在執行寫入操作，那麼如果有新的讀線程請求該怎麼處理？

TreeBin 對象内部保留了一個連結清單結構，就是為了這種情況而設計的。這時候會讓新來的讀線程到連結清單上去通路資料，而不經過紅黑樹。

14、挂起等待的寫線程後，什麼時候将其喚醒再繼續執行寫操作呢？

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

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

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

文章參考：ConcurrentHashMap擴容？lastRun到底是個啥？

總結的面試題也挺費時間的，文章會不定時更新，有時候一天多更新幾篇，如果幫助您複習鞏固了知識點，還請三連支援一下，後續會億點點的更新！