介紹 ConcurrentHashMap

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

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

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

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

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

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

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

ConcurrentHashMap 的新增操作

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

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

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

ConcurrentHashMap 的擴(kuò)容機(jī)制

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

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

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

• 首先根據(jù) CPU 核數(shù)和 table 數(shù)組的長度，計(jì)算當(dāng)前線程一輪處理哈希桶的個(gè)數(shù)。ConcurrentHashMap 的 transferIndex 成員變量會(huì)記錄下一輪 或者是 下一個(gè)線程要處理的哈希桶的索引值 + 1

  • 如果 CPU 核數(shù)為 1，那么當(dāng)前線程一輪處理哈希桶的個(gè)數(shù)為 table 數(shù)組的長度；
  • 如果 CPU 核數(shù)大于 1，那么先計(jì)算 num = (tab.length >>> 3) / NCPU的值：
    • 如果 num 值大于等于 16，那么 num 值就是當(dāng)前線程一輪處理哈希桶的個(gè)數(shù)；
    • 如果 num 值小于 16，那么當(dāng)前線程一輪處理哈希桶的個(gè)數(shù)為 16。也就是說，線程一輪處理哈希桶的個(gè)數(shù)最小值為 16。

• 領(lǐng)取完任務(wù)之后線程就開始處理哈希桶內(nèi)的節(jié)點(diǎn)。節(jié)點(diǎn)的轉(zhuǎn)移是從數(shù)組的最后一個(gè)索引位置開始，一個(gè)索引一個(gè)索引進(jìn)行的。<u>在轉(zhuǎn)移索引 i 上的節(jié)點(diǎn)之前，它會(huì)使用 synchronized 關(guān)鍵字給索引 i 上的結(jié)構(gòu)加鎖，保證同時(shí)最多只有一個(gè)線程操作索引 i 上的結(jié)構(gòu)。</u>

• 給索引 i 上的結(jié)構(gòu)加鎖之后，它會(huì)判斷數(shù)組在索引 i 上的結(jié)構(gòu)是鏈表 還是 紅黑樹，然后調(diào)用相應(yīng)的節(jié)點(diǎn)轉(zhuǎn)移代碼。

  • 如果索引 i 上的結(jié)構(gòu)是鏈表，它通過將節(jié)點(diǎn) key 的 hash 值 和 數(shù)組的長度 n 做與運(yùn)算獲得 n 對(duì)應(yīng)的二進(jìn)制表示中的 1 這一位在 hash 值中是 0 還是 1，即 b = p.hash & n。獲取到 b 之后，用 b 來判斷要轉(zhuǎn)移的節(jié)點(diǎn)是要掛到低位哈希桶里，還是掛到高位哈希桶里。遍歷完鏈表，形成兩個(gè)鏈表（低位鏈表、高位鏈表）之后，將鏈表的頭節(jié)點(diǎn)賦值給對(duì)應(yīng)的 tab[i]：

    • 如果 b 的值為 0，則要轉(zhuǎn)移的節(jié)點(diǎn)掛到低位哈希桶里
    • 如果 b 的值非 0，則要轉(zhuǎn)移的節(jié)點(diǎn)掛到高位哈希桶里

  • 如果索引 i 上的結(jié)構(gòu)是紅黑樹那么使用紅黑樹方式轉(zhuǎn)移節(jié)點(diǎn)。

• 在將索引 i 上的全部節(jié)點(diǎn)轉(zhuǎn)移到擴(kuò)容之后的新數(shù)組后，它讓舊數(shù)組 tab[i] 指向轉(zhuǎn)移節(jié)點(diǎn)（ForwardingNode）。

• 當(dāng)舊數(shù)組上的全部節(jié)點(diǎn)轉(zhuǎn)移到擴(kuò)容之后的新數(shù)組后，ConcurrentHashMap 的 table 成員變量指向擴(kuò)容之后的新數(shù)組，擴(kuò)容操作完成。

介紹低位哈希桶、高位哈希桶：如果 ConcurrentHashMap 當(dāng)前的數(shù)組長度為 n 時(shí)，一個(gè)節(jié)點(diǎn)的 key 對(duì)應(yīng)的哈希桶索引為 i。那么 ConcurrentHashMap 擴(kuò)容之后數(shù)組長度為 2n 時(shí)，這個(gè)節(jié)點(diǎn)的 key 對(duì)應(yīng)的低位哈希桶的索引為 i，對(duì)應(yīng)的高位哈希桶的索引為 i + n。

ConcurrentHashMap 支持多線程擴(kuò)容：

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

ConcurrentHashMap 的查找操作

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

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

ConcurrentHashMap 的容量大小問題

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

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

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

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

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

ConcurrentHashMap 的計(jì)數(shù)

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

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

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

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

ConcurrentHashMap 的計(jì)數(shù)將線程競爭分散到 counterCells 數(shù)組的每一個(gè)元素，提高了并發(fā)計(jì)數(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; }
}

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

最新評(píng)論