Java集合ConcurrentHashMap詳解

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

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

介紹 ConcurrentHashMap

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

ConcurrentHashMap 內(nèi)部使用了鎖和各種數(shù)據(jù)結(jié)構(gòu)來保證訪問 Map 是線程安全的。

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

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

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

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

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

ConcurrentHashMap 的新增操作

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

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

當調(diào)用 CHM 的 put() 方法時，如果 CHM 中已經(jīng)存在要新增的 key，并且方法的入?yún)?onlyIfAbsent 為 false，則替換舊值，并返回舊值。

ConcurrentHashMap 的擴容機制

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

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

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

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

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

ConcurrentHashMap 支持多線程擴容：

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

ConcurrentHashMap 的查找操作

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

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

ConcurrentHashMap 的容量大小問題

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

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

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

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

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

ConcurrentHashMap 的計數(shù)

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

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

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

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

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

private transient volatile long baseCount;

// 如果 counterCells 數(shù)組不為空，則數(shù)組的長度為 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內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: