1、請你描述一下ConcurrentHashMap存儲數(shù)據(jù)結(jié)構(gòu)是什么樣子呢？

• ConcurrentHashMap 內(nèi)部的 map 結(jié)構(gòu)和 HashMap 是一致的，都是由：數(shù)組 + 鏈表 + 紅黑樹 構(gòu)成。
• ConcurrentHashMap 存儲數(shù)據(jù)的單元和 HashMap 也是一致的，即，Node 結(jié)構(gòu)：

  static class Node<K,V> implements Map.Entry<K,V> {
      // hash值
      final int hash;
      // key
      final K key;
      // value
      volatile V val;
      // 后驅(qū)節(jié)點
      volatile Node<K,V> next;    
      ....
  }
  

• ConcurrentHashMap 和 HashMap 區(qū)別就在于前者支持并發(fā)擴容，其內(nèi)部通過加鎖（自旋鎖 + CAS + synchronized + 分段鎖）來保證線程安全。

2、請問ConcurrentHashMap的負載因子可以新指定嗎？

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

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

private static final float LOAD_FACTOR = 0.75f;

3、請問節(jié)點的 Node.hash 字段一般情況下必須 >=0 這是為什么？

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

• 如果 Node.hash = -1，表示當前節(jié)點是 **FWD(ForWardingNode) **節(jié)點(表示已經(jīng)被遷移的節(jié)點)。
• 如果 Node.hash = -2，表示當前節(jié)點已經(jīng)樹化，且當前節(jié)點為 TreeBin 對象，TreeBin 對象代理操作紅黑樹。
• 如果 Node.hash > 0，表示當前節(jié)點是正常的 Node 節(jié)點，可能是鏈表，或者單個 Node。

4、請你簡述 ConcurrentHashMap 中 sizeCtl 字段的作用（不同情況下的含義）？

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

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

• izeCtl == 0，是默認值，表示在真正第一次初始化散鏈表的時候使用默認容量 16 進行初始化。

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

• sizeCtl == -1表示當前散鏈表正處于初始化狀態(tài)。有線程正在對當前散列表(table) 進行初始化操作。
• ConcurrentHashMap 的散鏈表是延遲初始化的，在并發(fā)條件下必須確保只能初始化一次，所以 sizeCtl == -1 就相當于一個"標識鎖"，防止多個線程去初始化散列表。
• 具體初始化操作就是在initTable()方法中，會通過 CAS 的方式去修改 sizeCtl 的值為 -1，表示已經(jīng)有線程正在對散鏈表進行初始化，其他線程不可以再次初始化，只能等待！

// SIZECTL：期望值，初始為0
// this 就表示當前 ConcurrentHashMap對象
// sc 表示要修改的 sizeCtrl 
// -1 表示將 sc 修改為 -1
U.compareAndSwapInt(this, SIZECTL, sc, -1);

• 如果 CAS 修改 sizeCtl = -1 操作成功的線程，可以接著執(zhí)行對散鏈表初始化的邏輯。而 CAS 修改失敗的線程，在這里會不斷的自旋檢查，直到散鏈表初始化結(jié)束。
• 這里 CAS 失敗的線程會走如下邏輯，即自旋的線程會通過Thread.yield();方法，短暫釋放 CPU 資源，把 CPU 資源讓給更饑餓的線程去使用。目的是為了減輕自旋對CPU 性能的消耗。

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

• sizeCtl > 0 時，表示初始化或擴容完成后下一次觸發(fā)擴容的閾值。比如，sizeCtl = 12 時，當散鏈表中數(shù)據(jù)的個數(shù) >=12 時，就會觸發(fā)擴容操作。

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

• sizeCtl < 0 && sizeCtl != -1 時，表示當前散鏈表正處于擴容狀態(tài)。-(1 + nThreads)，表示有n個線程正在一起擴容。這時候，sizeCtl 的高 16 位表示擴容標識戳，低 16 位表示參與并發(fā)擴容線程數(shù)：1 + nThread， 即當前參與并發(fā)擴容的線程數(shù)量為 n 個。

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

• 根據(jù)老表的長度 tab.length 去獲取擴容唯一標識戳。
• 假設(shè) 16 -> 32 這樣擴容，那么擴容標識戳的作用就是在多線程并發(fā)擴容條件下，所有 16 -> 32 擴容的線程都可以參與并發(fā)擴容。

// 固定值16，與擴容相關(guān)，計算擴容時會根據(jù)該屬性值生成一個擴容標識戳
private static int RESIZE_STAMP_BITS = 16;

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

• sizeCtl < 0 && sizeCtl != -1 時，這時候sizeCtl 的高 16 位就表示擴容標識戳，低 16 位表示參與并發(fā)擴容線程數(shù)：1 + nThread， 即當前參與并發(fā)擴容的線程數(shù)量為 n 個。

6、ConcurrentHashMap如何保證寫數(shù)據(jù)線程安全？

這個問題其實就是問，向 ConcurrentHashMap 中添加數(shù)據(jù)確保線程安全是如何實現(xiàn)的。

• ConcurrentHashMap 內(nèi)部通過加鎖（自旋鎖 + CAS + synchronized + 分段鎖）來保證線程安全。

添加數(shù)據(jù)具體流程如下：

• ① 首先，先判斷散鏈表是否已經(jīng)初始化，如果沒初始化則先初始化散鏈表，再進行寫入操作。
• ② 當向桶位中寫數(shù)據(jù)時，先判斷桶中是否為空，如果是空桶，則直接通過 CAS 的方式將新增數(shù)據(jù)節(jié)點寫入桶中。如果 CAS 寫入失敗，則說明有其他線程已經(jīng)在當前桶位中寫入數(shù)據(jù)，當前線程競爭失敗，回到自旋位置，自旋等待。
• 如果當前桶中不為空，就需要判斷當前桶中頭結(jié)點的類型：
• ③ 如果桶中頭結(jié)點的 hash 值 為 -1，表示當前桶位的頭結(jié)點為 FWD 結(jié)點，目前散鏈表正處于擴容過程中。這時候當前線程需要去協(xié)助擴容。
• ④ 如果 ②、③ 條件不滿足，則表示當前桶位的存放的可能是一條鏈表，也可能是紅黑樹的代理對象 TreeBin。這種情況下會使用 synchronized 鎖住桶中的頭結(jié)點，來保證桶內(nèi)的寫操作是線程安全的。

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

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

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

/**
 * 計算Node節(jié)點hash值的算法：參數(shù)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沖突產(chǎn)生~
 * ------------------------------------------------------------------------------
 * 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))得到的結(jié)果再& HASH_BITS，目的是為了讓得到的hash值結(jié)果始終是一個正數(shù)
 */
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如何統(tǒng)計當前散列表中的數(shù)據(jù)量?

ConcurrentHashMap 統(tǒng)計存儲數(shù)據(jù)的數(shù)量是通過 addCount(long x, int check) 方法實現(xiàn)的，本質(zhì)上是借助了 LongAdder 原子類。

ConcurrentHashMap為什么不采用 ConcurrentHashMap為什么不采用 AtomicLong 統(tǒng)計散列表數(shù)據(jù)量呢？統(tǒng)計散列表數(shù)據(jù)量呢？

• 因為 AtomicLong 原子類自增操作是基于 CAS 實現(xiàn)的，基于 CAS 實現(xiàn)會導(dǎo)致一個問題，就是當大量線程同時執(zhí)行 CAS 操作時，只能有一個線程執(zhí)行成功，而其他所有線程都會因為失敗而進入自旋狀態(tài)，自旋本身就是一個 while(true) 的循環(huán)，非常耗費系統(tǒng)資源。

那么 LongAdder 是如何保證大并發(fā)量下，性能依舊高效呢？

先看下LongAdder的操作原理圖：

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

• LongAdder有一個全局變量volatile long base;值，當并發(fā)不高的情況下都是通過CAS來直接操作base值，如果CAS失敗，則針對LongAdder中的Cell[]數(shù)組中的Cell進行CAS操作，減少失敗的概率。

如當前類中base = 10，有三個線程進行CAS原子性的 加1操作，線程一執(zhí)行成功，此時base=11，線程二、線程三執(zhí)行失敗后開始針對于Cell[]數(shù)組中的Cell元素進行加1操作，同樣也是CAS操作，此時數(shù)組index=1和index=2中Cell的value都被設(shè)置為了1。

執(zhí)行完成后，統(tǒng)計累加數(shù)據(jù)：sum = 11 + 1 + 1 = 13，利用LongAdder進行累加的操作就執(zhí)行完了，流程圖如下：

9、觸發(fā)擴容條件的線程，執(zhí)行的預(yù)處理工作都有哪些？

• 首先，觸發(fā)擴容條件的線程，要做的第一件事就是通過 CAS 的方式修改 sizeCtl 字段值，使其高 16 位為擴容唯一標識戳，低 16 位為(參與擴容的線程數(shù) + 1)，表示有線程正在進行擴容邏輯！
  • 注意：這里高 16 位的擴容唯一標識戳是根據(jù)當前散鏈表的長度計算得來，其最高位是 1。那么最終得到的 sizeCtl 就應(yīng)該是一個負數(shù)。
• 然后，當前觸發(fā)擴容條件的線程會創(chuàng)建一個新的散鏈表，大小為原來舊散鏈表的 2 倍。并且將新散鏈表的引用賦給 map.nextTable 字段。
• 又因為 ConcurrentHashMap 是支持多線程并發(fā)擴容的，所以需要讓協(xié)助擴容的線程知道舊散鏈表數(shù)據(jù)遷移到新散鏈表的進度。為此 ConcurrentHashMap 提供了一個 transferIndex 字段，用于記錄舊散鏈表數(shù)據(jù)的總遷移進度！遷移工作進度是從 高位桶開始，一直遷移到下標是 0 的桶位。

10、舊散鏈表中遷移完畢后的桶，如何做標記？

• 舊散鏈表中遷移完畢的桶，需要用 ForwardingNode 對象表示桶內(nèi)節(jié)點，這種 Node 比較特殊，是用來表示當前桶中的數(shù)據(jù)已經(jīng)被遷移到新散鏈表的桶中去了。

ForwardingNode 有哪些作用？

• ForwardingNode 對象內(nèi)部提供了一個用于向新散鏈表中查詢目標數(shù)據(jù)的find()方法。
• 當此時某個線程剛好在舊散鏈表中查詢目標元素時，剛好遇到當前桶位中存放的是 FWD 節(jié)點，那么就可以通過 FWD 節(jié)點的 find() 方法重新定向到新散鏈表中去查詢目標元素！

11、如果散列表正在庫容時，再來新的寫入請求該如何處理呢？

這里要分兩種情況考慮：

• 如果當前線程執(zhí)行寫入操作時，根據(jù)尋址算法訪問到的桶中不是 FWD 節(jié)點(即，當前桶中數(shù)據(jù)沒有被遷移)。那么此時先判斷桶中是否為空，如果為空則 CAS 方式寫入數(shù)據(jù)。而如果桶不為空，則可能是鏈表或者 TreeBin，這時候需要通過 synchronized 關(guān)鍵字鎖住桶的頭結(jié)點再進行寫入操作。
• 而如果如果當前線程執(zhí)行寫入操作時，根據(jù)尋址算法訪問到的桶中是 FWD 節(jié)點(即，當前桶中數(shù)據(jù)已經(jīng)被遷移)。
  • 碰到 FWD 節(jié)點，說明此時散鏈表正在進行擴容，這時候需要當前線程也加入進去，去協(xié)助散鏈表擴容（helpTransfer(tab, f);協(xié)助擴容是為了盡量減少擴容所花費在數(shù)據(jù)遷移上的時間）。
  • 當前線程加入到協(xié)助擴容中后，ConcurrentHashMap 會根據(jù)全局的transferIndex字段去給當前線程分配遷移工作任務(wù)（需要負責遷移舊散鏈表的桶位區(qū)間）。例如，讓當前線程負責遷移舊散鏈表中 【0-4】桶位上的數(shù)據(jù)到新散鏈表。
  • 一直到當前線程分配不到要負責遷移的任務(wù)時，則退出協(xié)助擴容，即擴容結(jié)束。這時候，當前線程就可以繼續(xù)執(zhí)行寫入數(shù)據(jù)的邏輯了！

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

• 每一個執(zhí)行擴容任務(wù)的線程(包含協(xié)助擴容)，它在開始工作之前，都會更新 sizeCtl的低 16 位，即讓低 16 位 +1，說明又加入一個新的線程去執(zhí)行擴容。
• 每個執(zhí)行擴容的線程都會被分配一個遷移工作任務(wù)區(qū)間，如果當前線程所負責的任務(wù)區(qū)間遷移工作完成了，沒有再被分配遷移任務(wù)區(qū)間，那么此時當前線程就可以退出協(xié)助擴容了，這時候更新 sizeCtl的低 16 位，即讓低 16 位 -1，說明有一個線程退出并發(fā)擴容了。
• 如果 sizeCtl 低 16 位-1后的值為 1，則說明當前線程是最后一個退出并發(fā)擴容的線程。

13、當桶位中鏈表升級為紅黑樹，且當前紅黑樹上有讀線程正在訪問，那么如果再來新的寫線程請求該怎么處理？

寫線程會被阻塞，因為紅黑樹比較特殊，新寫入數(shù)據(jù)，可能會觸發(fā)紅黑樹的自平衡，這就會導(dǎo)致樹的結(jié)構(gòu)發(fā)生變化，會影響讀線程的讀取結(jié)果！

在紅黑樹上讀取數(shù)據(jù)和寫入數(shù)據(jù)是互斥的，具體原理分析如下：

• 我們知道 ConcurrentHashMap 中的紅黑樹由 TreeBin 來代理，TreeBin 內(nèi)部有一個 Int 類型的 state 字段。
• 當讀線程在讀取數(shù)據(jù)時，會使用 CAS 的方式將 state 值 +4（表示加了讀鎖），讀取數(shù)據(jù)完畢后，再使用CAS 的方式將 state 值 -4。
• 如果寫線程去向紅黑樹中寫入數(shù)據(jù)時，會先檢查 state 值是否等于 0，如果是 0，則說明沒有讀線程在檢索數(shù)據(jù)，這時候可以直接寫入數(shù)據(jù)，寫線程也會通過 CAS 的方式將 state 字段值設(shè)置為 1（表示加了寫鎖）。
• 如果寫線程檢查 state 值不是 0，這時候就會park()掛起當前線程，使其等待被喚醒。掛起寫線程時，寫線程會先將 state 值的第 2 個 bit 位設(shè)置為 1（二進制為 10），轉(zhuǎn)換成十進制就是 2，表示有寫線程等待被喚醒。

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

• TreeBin 對象內(nèi)部保留了一個鏈表結(jié)構(gòu)，就是為了這種情況而設(shè)計的。這時候會讓新來的讀線程到鏈表上去訪問數(shù)據(jù)，而不經(jīng)過紅黑樹。

14、掛起等待的寫線程后，什么時候?qū)⑵鋯拘言倮^續(xù)執(zhí)行寫操作呢？

• 上一個問題中，我們分析了：當讀線程在讀取數(shù)據(jù)時，會使用 CAS 的方式將 state 值 +4（表示加了讀鎖），讀取數(shù)據(jù)完畢后，再使用CAS 的方式將 state 值 -4。
• 當 state 值減去 4 后，讀線程會先檢查一下 state 值是不是 2，如果是 2 ，則說明有等待被喚醒的寫線程在掛起等候，這時候調(diào)用 unsafe.unpark() 方法去喚醒該寫線程。

15、總結(jié)

文章會不定時更新，有時候一天多更新幾篇，如果幫助您復(fù)習鞏固了知識點，后續(xù)會億點點的更新！希望大家多多關(guān)注腳本之家的其他內(nèi)容！

最新評論