Java集合ConcurrentHashMap詳解

更新時間：2023年01月15日 08:54:14 作者：真正的飛魚

ConcurrentHashMap?是?J.U.C?包里面提供的一個線程安全并且高效的?HashMap，所以ConcurrentHashMap?在并發(fā)編程的場景中使用的頻率比較高

介紹 ConcurrentHashMap

技術是為了解決問題而生的，ConcurrentHashMap 解決了多個線程同時操作一個 HashMap 時，可能出現的內部問題。當多個線程同時操作一個 HashMap 時，有可能會出現多線程同時修改一個共享變量（HashMap 類的成員變量），導致數據被覆蓋，產生意想不到的錯誤。

ConcurrentHashMap 內部使用了鎖和各種數據結構來保證訪問 Map 是線程安全的。

ConcurrentHashMap 和 HashMap 底層的數組、鏈表結構幾乎相同，底層對數據結構的操作思路是相同的。ConcurrentHashMap 除了數組 + 鏈表 + 紅黑樹的基本結構外，新增了轉移節(jié)點結構（ForwardingNode）。

介紹轉移節(jié)點（ForwardingNode）

轉移節(jié)點是 ForwardingNode 結構， ForwardingNode 繼承了 Node。ForwardingNode 節(jié)點的 hash 值固定為 -1。ForwardingNode 比 Node 多了一個 nextTable 成員變量，nextTable 成員變量的類型是 Node 數組。nextTable 成員變量是擴容之后的新數組。

如果數組在索引 i 上的結構是 ForwardingNode，那么表示這個哈希桶內的全部節(jié)點都已經轉移到擴容之后的新數組，舊的哈希桶內的數據不能發(fā)生改變。轉移節(jié)點（ForwardingNode）是為了保證 ConcurrentHashMap 擴容時的線程安全。保證了當一個哈希桶內的全部節(jié)點都已經轉移到擴容之后的新數組后、擴容操作完成之前，舊的哈希桶內的數據不發(fā)生變化。

當一個哈希桶內的全部節(jié)點都已經轉移到擴容之后的新數組后、擴容操作完成之前，如果有其他的線程執(zhí)行 put 操作，需要將新增的節(jié)點 put 到舊的哈希桶內，那么這個線程會調用 helpTransfer() 方法幫助擴容。擴容完成之后，這個線程再將要新增的節(jié)點 put 到新的哈希桶內。

ConcurrentHashMap 的新增操作

ConcurrentHashMap 在 put 方法上對數據結構的操作思路和 HashMap 相同，但 ConcurrentHashMap 的 put() 方法寫了很多保障線程安全的代碼。當調用 ConcurrentHashMap 的 put() 方法時，put() 方法的處理邏輯如下：

首先，如果 CHM 的成員變量 table 數組為空（null 或者 length 為 0），則調用 initTable() 方法初始化 table 數組。由于 initTable() 方法操作了共享變量，因此 initTable() 方法采用了一些手段來保證線程安全。
接下來，它會調用 spread() 方法根據 key 計算出 hash 值，然后根據計算出的 hash 值計算出 key 對應的數組索引 i
計算出 key 對應的數組索引 i 之后，它調用 tabAt() 方法，tabAt() 方法返回數組在索引 i 上的值。然后它根據數組在索引 i 上的值進行處理。由于 tabAt() 方法讀取了共享變量 table 數組在索引 i 上的值，因此 tabAt() 方法調用 Unsafe 類的 get 方法保證數據的可見性：
- 如果數組在索引 i 上的值為 null，則直接生成一個新的節(jié)點，并調用 casTabAt() 方法讓 tab[i] 指向該節(jié)點。由于 casTabAt() 方法操作了共享變量 tab 數組，因此 casTabAt() 方法調用 Unsafe 類的 compareAndSwap 方法保證數據不被覆蓋；
- 如果數組在索引 i 上的值不為 null，則意味著需要解決 hash 沖突問題、擴容沖突問題。
接上一步驟，如果數組在索引 i 上的值不為 null。
- 如果索引 i 上的結構是轉移節(jié)點（ForwardingNode 結構，節(jié)點的 hash 值為 -1，表明這個哈希桶內的全部節(jié)點都已經轉移到擴容之后的新數組，舊的哈希桶內的數據不能發(fā)生改變），它就會調用 helpTransfer() 方法，helpTransfer() 方法會幫助擴容。擴容完成之后，它再將要新增的節(jié)點 put 到擴容之后的新數組中。
- 如果索引 i 上的結構不是轉移節(jié)點，那么它會使用 synchronized 關鍵字給索引 i 上的結構加鎖，保證同時最多只有一個線程操作索引 i 上的結構。給索引 i 上的結構加鎖之后，它會判斷數組在索引 i 上的結構是鏈表還是紅黑樹，然后調用相應的新增代碼。
  - 如果索引 i 上的結構是鏈表，則把新生成的節(jié)點加到鏈表的末尾；
  - 如果索引 i 上的結構是紅黑樹，那么使用紅黑樹方式新增。
接上一步驟，如果索引 i 上的結構是普通鏈表，則把新生成的節(jié)點加到鏈表的末尾之后，需要判斷是否需要將鏈表轉為紅黑樹：
- 如果鏈表的長度大于等于 8，并且數組的長度大于等于 64，則調用 treeifyBin() 將鏈表轉為紅黑樹；
- 如果鏈表的長度大于等于 8，但是數組的長度小于 64，則調用 tryPresize() 方法執(zhí)行擴容操作；
- 當紅黑樹中的節(jié)點個數小于等于 6 時，紅黑樹會轉為鏈表。
將節(jié)點加入 CHM 集合之后，put() 方法的最后一步是調用 addCount() 方法增加 ConcurrentHashMap 中元素個數的計數值。addCount() 方法的任務是：增加 ConcurrentHashMap 中元素的計數值。如果元素的數量超過了 ConcurrentHashMap 擴容的閾值（sizeCtl），那么就會調用 transfer() 方法執(zhí)行擴容操作。如果此時有其他的線程已經在執(zhí)行擴容操作，那么當前線程就協助擴容。

當調用 CHM 的 put() 方法時，如果 CHM 中已經存在要新增的 key，并且方法的入參 onlyIfAbsent 為 false，則替換舊值，并返回舊值。

ConcurrentHashMap 的擴容機制

ConcurrentHashMap 的擴容時機和 HashMap 相同，都是在 put() 方法的最后一步檢查是否需要擴容。ConcurrentHashMap 擴容的方法叫做 transfer()，從 put() 方法的 addCount() 方法進去，就能找到 transfer() 方法。

如果 ConcurrentHashMap 中元素的數量超過了擴容的閾值（sizeCtl），那么它會調用 transfer() 方法執(zhí)行擴容操作。ConcurrentHashMap 的擴容機制是擴容為原來容量的 2 倍。ConcurrentHashMap 擴容的處理邏輯和 HashMap 完全不同。

ConcurrentHashMap 擴容的大體思路如下：擴容需要把舊數組上的全部節(jié)點轉移到擴容之后的新數組上，節(jié)點的轉移是從數組的最后一個索引位置開始，一個索引一個索引進行的。每個線程一輪處理有限個數的哈希桶。當舊數組上的全部節(jié)點轉移到擴容之后的新數組后，ConcurrentHashMap 的 table 成員變量指向擴容之后的新數組，擴容操作完成。transfer() 方法的處理邏輯如下：

首先根據 CPU 核數和 table 數組的長度，計算當前線程一輪處理哈希桶的個數。ConcurrentHashMap 的 transferIndex 成員變量會記錄下一輪或者是下一個線程要處理的哈希桶的索引值 + 1
- 如果 CPU 核數為 1，那么當前線程一輪處理哈希桶的個數為 table 數組的長度；
- 如果 CPU 核數大于 1，那么先計算 num = (tab.length >>> 3) / NCPU的值：
  - 如果 num 值大于等于 16，那么 num 值就是當前線程一輪處理哈希桶的個數；
  - 如果 num 值小于 16，那么當前線程一輪處理哈希桶的個數為 16。也就是說，線程一輪處理哈希桶的個數最小值為 16。
領取完任務之后線程就開始處理哈希桶內的節(jié)點。節(jié)點的轉移是從數組的最后一個索引位置開始，一個索引一個索引進行的。在轉移索引 i 上的節(jié)點之前，它會使用 synchronized 關鍵字給索引 i 上的結構加鎖，保證同時最多只有一個線程操作索引 i 上的結構。
給索引 i 上的結構加鎖之后，它會判斷數組在索引 i 上的結構是鏈表還是紅黑樹，然后調用相應的節(jié)點轉移代碼。
- 如果索引 i 上的結構是鏈表，它通過將節(jié)點 key 的 hash 值和數組的長度 n 做與運算獲得 n 對應的二進制表示中的 1 這一位在 hash 值中是 0 還是 1，即 b = p.hash & n。獲取到 b 之后，用 b 來判斷要轉移的節(jié)點是要掛到低位哈希桶里，還是掛到高位哈希桶里。遍歷完鏈表，形成兩個鏈表（低位鏈表、高位鏈表）之后，將鏈表的頭節(jié)點賦值給對應的 tab[i]：
  - 如果 b 的值為 0，則要轉移的節(jié)點掛到低位哈希桶里
  - 如果 b 的值非 0，則要轉移的節(jié)點掛到高位哈希桶里
- 如果索引 i 上的結構是紅黑樹那么使用紅黑樹方式轉移節(jié)點。
在將索引 i 上的全部節(jié)點轉移到擴容之后的新數組后，它讓舊數組 tab[i] 指向轉移節(jié)點（ForwardingNode）。
當舊數組上的全部節(jié)點轉移到擴容之后的新數組后，ConcurrentHashMap 的 table 成員變量指向擴容之后的新數組，擴容操作完成。

介紹低位哈希桶、高位哈希桶：如果 ConcurrentHashMap 當前的數組長度為 n 時，一個節(jié)點的 key 對應的哈希桶索引為 i。那么 ConcurrentHashMap 擴容之后數組長度為 2n 時，這個節(jié)點的 key 對應的低位哈希桶的索引為 i，對應的高位哈希桶的索引為 i + n。

ConcurrentHashMap 支持多線程擴容：

如果在擴容的過程中，有其他的線程執(zhí)行新增操作，新增操作完成后，這個線程會調用 transfer() 方法協助擴容。
如果一個線程在擴容時，有其他的線程執(zhí)行新增操作，需要把節(jié)點 put 到索引為 i 的哈希桶內。其他的線程它發(fā)現索引 i 上的結構是轉移節(jié)點（ForwardingNode 結構，節(jié)點的 hash 值為 -1，表明這個哈希桶內的元素已經擴容遷移完成），那么這個線程它就會調用 helpTransfer() 方法，helpTransfer() 方法會調用 transfer() 幫助擴容。擴容完成之后，它再將要新增的節(jié)點 put 到擴容之后的新數組中。

ConcurrentHashMap 的查找操作

當調用 ConcurrentHashMap 的 get() 方法時，get() 方法的處理邏輯如下：

首先，它會根據傳入的 key 計算出 hash 值；然后根據計算出的 hash 值計算出 key 對應的數組索引 i
計算出 key 對應的數組索引 i 之后，根據存儲位置，從數組中取出對應的 Entry，然后通過 key 對象的 equals() 方法判斷傳入的 key 和 Entry 中的 key 是否相等：
- 如果傳入的 key 和 Entry 中的 key 相等，則查找操作完成，返回 Entry 中的 value；
- 如果傳入的 key 和 Entry 中的 key 不相等，則再判斷數組在索引 i 上的結構是鏈表還是紅黑樹，然后調用相應的查找數據的方法。直到找到相等的 Entry 或者沒有下一個 Entry 為止。

ConcurrentHashMap 的容量大小問題

ConcurrentHashMap 的數組長度總是為 2 的冪次方。不論傳入的初始容量是否為 2 的冪次方，最終都會轉化為 2 的冪次方。

ConcurrentHashMap 中根據 key 計算出 hash 值，然后根據計算出的 hash 值計算出 key 對應的數組索引 i：

根據 key 計算處 hash 值：在計算 hash 值時，它先將 key 的 hashCode 值無符號右移 16 位，然后再和 key 的 hashCode 值做異或運算，即 hash = (hashCode >>> 16) ^ hashCode。
根據 hash 值計算出 key 對應的數組索引 i：在計算 key 對應的數組索引 i 時，它將 hash 值和數組的長度 - 1 做與運算獲得 key 對應的數組索引 i，即 i = hash & (n - 1)。

ConcurrentHashMap 的數組長度總是為 2 的冪次方設計的非常巧妙：

在計算 hash 值時，它先將 key 的 hashCode 值無符號右移 16 位，然后再和 key 的 hashCode 值做異或運算，即 hash = (hashCode >>> 16) ^ hashCode。使 key 的 hashCode 值高 16 位的變化映射到低 16 位中，使 hashCode 值高 16 位也參與后續(xù)索引 i 的計算，減少了碰撞的可能性。
在計算 key 對應的數組索引 i 時，它將 hash 值和數組的長度 - 1 做與運算獲得 key 對應的數組索引 i，即 i = hash & (n - 1)。由于數組的長度 n 是 2 的冪次方，n - 1 可以保證它的二進制表示中的后幾位都是 1，n 對應的二進制位及之前的位都是 0。因此，計算出的數組索引 i 和 hash 值的二進制表示中后幾位有關，而與前面的二進制位無關
當 b 是 2 的冪次方時，a % b == a & (b - 1)。CPU 處理位運算比處理數學運算的速度更快，效率更高。
在 ConcurrentHashMap 擴容時，它通過將 key 的 hash 值和數組的長度 n 做與運算獲得 n 對應的二進制表示中的 1 這一位在 hash 值中是 0 還是 1，即 b = p.hash & n。獲取到 b 之后，用 b 來判斷要轉移的節(jié)點是要掛到低位哈希桶里，還是掛到高位哈希桶里：
- 如果 b 的值為 0，則要轉移的節(jié)點掛到低位哈希桶里
- 如果 b 的值非 0，則要轉移的節(jié)點掛到高位哈希桶里

ConcurrentHashMap 的計數

當調用 ConcurrentHashMap 的 put() 方法時，put() 方法的最后一步是調用 addCount() 方法。

addCount() 方法的任務是：增加 ConcurrentHashMap 中元素的計數值。如果元素的數量超過了 ConcurrentHashMap 擴容的閾值（sizeCtl），那么就會調用 transfer() 方法執(zhí)行擴容操作。如果此時有其他的線程已經在執(zhí)行擴容操作，那么當前線程就協助擴容。

ConcurrentHashMap 采用了一些數據結構和手段來支持高效的并發(fā)計數。ConcurrentHashMap 使用 long 類型的 baseCount 成員變量和 CounterCell 類型的 counterCells 數組來支持高效的并發(fā)計數。

baseCount 是基礎的計數值。主要通過調用 Unsafe 類的 compareAndSwap 方法更新 baseCount 的值
counterCells 數組的使用：如果有多個線程調用 addCount() 方法增加元素的計數值，那么每個線程將要增加的計數值保存在 counterCells 數組中。當調用 ConcurrentHashMap 的 size() 方法獲取元素個數時，size() 方法將循環(huán)遍歷 counterCells 數組，累加計數值得到當時元素。

ConcurrentHashMap 的計數將線程競爭分散到 counterCells 數組的每一個元素，提高了并發(fā)計數的性能。

private transient volatile long baseCount;

// 如果 counterCells 數組不為空，則數組的長度為 2 的冪次方。
private transient volatile CounterCell[] counterCells;

@sun.misc.Contended static final class CounterCell {
? ? volatile long value;
? ? CounterCell(long x) { value = x; }
}

到此這篇關于Java集合ConcurrentHashMap詳解的文章就介紹到這了,更多相關Java集合ConcurrentHashMap內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: