解析ConcurrentHashMap: get、remove方法分析
更新時間：2021年06月10日 17:22:57 作者：興趣使然の草帽路飛
ConcurrentHashMap是由Segment數(shù)組結(jié)構(gòu)和HashEntry數(shù)組結(jié)構(gòu)組成。Segment的結(jié)構(gòu)和HashMap類似，是一種數(shù)組和鏈表結(jié)構(gòu)，今天給大家普及java面試常見問題---ConcurrentHashMap知識，一起看看吧
前面幾篇文章分析了并發(fā)HashMap的put方法及其相關(guān)方法，transfer方法，那么接下來本篇文章相對之前幾篇難度會小一些。
本篇文章介紹ConcurrentHashMap的get方法和remove方法。
1、get方法
get方法：獲取元素，根據(jù)目標(biāo)key所在桶的第一個元素的不同采用不同的方式獲取元素，關(guān)鍵點在于find()方法的重寫。
public V get(Object key) {
// tab 引用map.table
// e 當(dāng)前元素(用于循環(huán)遍歷)
// p 目標(biāo)節(jié)點
// n table數(shù)組長度
// eh 當(dāng)前元素hash
// ek 當(dāng)前元素key
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
// 根據(jù)key.hashCode()計算hash: 擾動運算后得到得到更散列的hash值
int h = spread(key.hashCode());
java // --------------------------------------------------------------------------------
// CASE1:
// 如果元素所在的桶存在且里面有元素
// 條件一：(tab = table) != null
// true -> 表示已經(jīng)put過數(shù)據(jù)，并且map內(nèi)部的table也已經(jīng)初始化完畢
// false -> 表示創(chuàng)建完map后，并沒有put過數(shù)據(jù)，map內(nèi)部的table是延遲初始化的，只有第一次寫數(shù)據(jù)時會觸發(fā)初始化創(chuàng)建table邏輯
// 條件二：(n = tab.length) > 0 如果為 true-> 表示table已經(jīng)初始化
// 條件三：(e = tabAt(tab, (n - 1) & h)) != null
// true -> 當(dāng)前key尋址的桶位有值
// false -> 當(dāng)前key尋址的桶位中是null，是null直接返回null
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 進入if代碼塊內(nèi)部的前置條件：當(dāng)前桶位有數(shù)據(jù)
java // 如果第一個元素就是要找的元素，則直接返回
// 對比頭結(jié)點hash與查詢key的hash是否一致
// 條件成立：說明頭結(jié)點與查詢Key的hash值完全一致
if ((eh = e.hash) == h) {
// 完全比對 查詢key 和 頭結(jié)點的key
// 條件成立：說明頭結(jié)點就是查詢數(shù)據(jù)
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
// 當(dāng)e的hash值以及e對應(yīng)的key都匹配目標(biāo)元素時，則找到了，直接返回~
return e.val;
}
java // --------------------------------------------------------------------------------
// CASE2: eh < 0
// 條件成立：即，hash小于0 分2種情況，是樹或者正在擴容,需要借助find方法尋找元素，find的尋找方式依據(jù)Node的不同子類有不同的實現(xiàn)方式:
// 情況一：eh=-1 是fwd結(jié)點 -> 說明當(dāng)前table正在擴容，且當(dāng)前查詢的這個桶位的數(shù)據(jù)已經(jīng)被遷移走了，需要借助fwd結(jié)點的內(nèi)部方法find去查詢
// 情況二：eh=-2 是TreeBin節(jié)點 -> 需要使用TreeBin 提供的find方法查詢。
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
java // --------------------------------------------------------------------------------
// CASE3: 前提條件 -> CASE1和CASE2條件不滿足！
// 說明是當(dāng)前桶位已經(jīng)形成鏈表的這種情況: 遍歷整個鏈表尋找元素
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
java }
return null;
}
1.1 ForwardingNode 內(nèi)部類(FWD結(jié)點)
在get方法CASE2中，eh < 0會分2中情況：
情況一：eh=-1 是fwd結(jié)點 -> 說明當(dāng)前table正在擴容，且當(dāng)前查詢的這個桶位的數(shù)據(jù)已經(jīng)被遷移走了，需要借助fwd結(jié)點的內(nèi)部方法find去查詢。
情況二：eh = -2 是TreeBin節(jié)點 -> 需要使用TreeBin 提供的find方法查詢。
下面就分析一下情況一，即當(dāng)前桶位中是fwd結(jié)點。我們來分析一下FWD這個內(nèi)部類，以及其內(nèi)部的find方法：
static final class ForwardingNode<K,V> extends Node<K,V> {
final Node<K,V>[] nextTable;
ForwardingNode(Node<K,V>[] tab) {
super(MOVED, null, null, null);
this.nextTable = tab;
}
java // fwd結(jié)點的find方法：
Node<K,V> find(int h, Object k) {
// loop to avoid arbitrarily deep recursion on forwarding nodes
// tab 一定不為空：整個ConcurrentHashMap源碼中，只有一個地方實例化ForwardingNode，就是在transfer遷移數(shù)據(jù)方法中執(zhí)行了：ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);（當(dāng)某個桶位數(shù)據(jù)處理完畢后，將此桶位設(shè)置為fwd節(jié)點，其它寫線程或讀線程看到后，會有不同邏輯）
Node<K,V>[] tab = nextTable;
java // ------------------------------------------------------------------------------
// 自旋1
outer: for (;;) {
// n 表示為擴容而創(chuàng)建的新表的長度
// e 表示在擴容而創(chuàng)建新表時，使用尋址算法得到的桶位頭結(jié)點
Node<K,V> e; int n;
java // 條件一：永遠不成立
// 條件二：永遠不成立
// 條件三：永遠不成立
// 條件四：在新擴容表中重新路由定位 hash 對應(yīng)的頭結(jié)點
// true -> 1.在oldTable中對應(yīng)的桶位在遷移之前就是null
// false -> 2.擴容完成后，有其它寫線程，將此桶位設(shè)置為了null
if (k == null || tab == null || (n = tab.length) == 0 ||
(e = tabAt(tab, (n - 1) & h)) == null)
return null;
java // ---------------------------------------------------------------------------
// 自旋2
// 前置條件：擴容后的表對應(yīng)hash的桶位一定不是null，e為此桶位的頭結(jié)點
// e可能為哪些node類型？
// 1.node 類型
// 2.TreeBin 類型
// 3.FWD類型
for (;;) {
// eh 新擴容后表指定桶位的當(dāng)前節(jié)點的hash
// ek 新擴容后表指定桶位的當(dāng)前節(jié)點的key
int eh; K ek;
// CASE1條件成立：說明新擴容后的表，當(dāng)前命中桶位中的數(shù)據(jù)，即為查詢想要數(shù)據(jù)。
if ((eh = e.hash) == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
// 直接將e返回~
return e;
java // CASE2: eh < 0 時
// 1.TreeBin 類型
// 2.FWD類型（新擴容的表，在并發(fā)很大的情況下，可能在此方法再次拿到FWD類型），即可能又發(fā)生了擴容
if (eh < 0) {
// 判斷是否是FWD結(jié)點
if (e instanceof ForwardingNode) {
// 是FWD結(jié)點
tab = ((ForwardingNode<K,V>)e).nextTable;
// 跳轉(zhuǎn)到自旋1
continue outer;
}
else// 不是FWD結(jié)點
// 說明此桶位 為 TreeBin 節(jié)點，使用TreeBin.find 查找紅黑樹中相應(yīng)節(jié)點。
return e.find(h, k);
}
java // 前置條件：當(dāng)前桶位頭結(jié)點 并沒有命中查詢，說明此桶位是鏈表
// 1.將當(dāng)前元素指向鏈表的下一個元素
// 2.判斷當(dāng)前元素的下一個位置是否為空
// true -> 說明迭代到鏈表末尾，未找到對應(yīng)的數(shù)據(jù)，返回Null
if ((e = e.next) == null)
return null;
}
}
}
}
小節(jié)：
（1）hash到元素所在的桶；
（2）如果桶中第一個元素就是該找的元素，直接返回；
（3）如果是樹或者正在遷移元素，則調(diào)用各自Node子類的find()方法尋找元素；
（4）如果是鏈表，遍歷整個鏈表尋找元素；
（5）獲取元素沒有加鎖；
2、remove方法
remove方法：刪除元素跟添加元素一樣，都是先找到元素所在的桶，然后采用分段鎖的思想鎖住整個桶，再進行操作。
public V remove(Object key) {
// 調(diào)用替換節(jié)點方法
return replaceNode(key, null, null);
}
java/**
* 結(jié)點替換：
* 參數(shù)1：Object key -> 就表示當(dāng)前結(jié)點的key
* 參數(shù)2：V value -> 要替換的目標(biāo)值
* 參數(shù)3：Object cv（compare Value） ->
* 如果cv不為null，則需要既比對key，還要比對cv，這樣個參數(shù)都一致，才能替換成目標(biāo)值
*/
final V replaceNode(Object key, V value, Object cv) {
// 計算key經(jīng)過擾動運算后得到的hash
int hash = spread(key.hashCode());
// 自旋
for (Node<K,V>[] tab = table;;) {
// f表示桶位頭結(jié)點
// n表示當(dāng)前table數(shù)組長度
// i表示hash命中桶位下標(biāo)
// fh表示桶位頭結(jié)點hash
Node<K,V> f; int n, i, fh;
java // ----------------------------------------------------------------------------
// CASE1：
// 條件一：tab == null
// true -> 表示當(dāng)前map.table尚未初始化..
// false -> 表示當(dāng)前map.table已經(jīng)初始化
// 條件二：(n = tab.length) == 0
// true -> 表示當(dāng)前map.table尚未初始化..
// false -> 已經(jīng)初始化
// 條件三：(f = tabAt(tab, i = (n - 1) & hash)) == null
// true -> 表示命中桶位中為null，直接break
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
// 如果目標(biāo)key所在的桶不存在，跳出循環(huán)返回null
break;
java // ----------------------------------------------------------------------------
// CASE2：
// 前置條件CASE2 ~ CASE3：當(dāng)前桶位不是null
// 條件成立：fwd結(jié)點，說明當(dāng)前table正在擴容中，當(dāng)前是個寫操作，所以當(dāng)前線程需要協(xié)助table完成擴容。
else if ((fh = f.hash) == MOVED)
// 如果正在擴容中，則協(xié)助擴容
tab = helpTransfer(tab, f);
java // ----------------------------------------------------------------------------
// CASE3:
// 前置條件CASE2 ~ CASE3：當(dāng)前桶位不是null
// 當(dāng)前桶位是一個有數(shù)據(jù)的桶位，桶中可能是 "鏈表"也可能是"紅黑樹"TreeBin
else {
// 保留替換之前的數(shù)據(jù)引用
V oldVal = null;
// 校驗標(biāo)記,在下面的CASEn中的if判斷使用：標(biāo)記是否處理過
boolean validated = false;
// 加鎖當(dāng)前桶位頭結(jié)點，加鎖成功之后會進入代碼塊。
synchronized (f) {
// 判斷sync加鎖是否為當(dāng)前桶位頭節(jié)點，防止其它線程，在當(dāng)前線程加鎖成功之前，修改過桶位 的頭結(jié)點，導(dǎo)致鎖錯對象！
java // --------------------------------------------------------------------
// CASE4: tabAt(tab, i) == f 再次驗證當(dāng)前桶第一個元素是否被修改過
// 條件成立：說明當(dāng)前桶位頭結(jié)點仍然為f，其它線程沒修改過！
if (tabAt(tab, i) == f) {
// --------------------------------------------------------------------
// CASE5: fh >= 0
// 條件成立：說明桶位為鏈表或者單個node
if (fh >= 0) {
// 校驗標(biāo)記置為true
validated = true;
java // e 表示當(dāng)前循環(huán)處理結(jié)點
// pred 表示當(dāng)前循環(huán)節(jié)點的上一個節(jié)點
Node<K,V> e = f, pred = null;
// 遍歷鏈表尋找目標(biāo)節(jié)點
for (;;) {
// 表示當(dāng)前節(jié)點key
K ek;
java // ------------------------------------------------------------
// CASE6:
// 條件一：e.hash == hash
// true->說明當(dāng)前節(jié)點的hash與查找節(jié)點hash一致
// 條件二：((ek = e.key) == key || (ek != null && key.equals(ek)))
// CASE6的if條件成立，說明key 與查詢的key完全一致。
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
// 找到了目標(biāo)節(jié)點：當(dāng)前節(jié)點的value，
V ev = e.val;
java // -----------------------------------------------------
// CASE7: 檢查目標(biāo)節(jié)點舊value是否等于cv
// 條件一：cv == null
// true -> 替換的值為null那么就是一個刪除操作
// 條件二：cv == ev || (ev != null && cv.equals(ev))
// true -> 那么是一個替換操作
if (cv == null || cv == ev ||
(ev != null && cv.equals(ev))) {
// 刪除 或者 替換
// 將當(dāng)前節(jié)點的值 賦值給 oldVal 后續(xù)返回會用到~
oldVal = ev;
java // 目標(biāo)value不等于null
// 如果條件成立：說明當(dāng)前是一個替換操作
if (value != null)
// 直接替換
e.val = value;
// 條件成立：說明當(dāng)前節(jié)點非頭結(jié)點
else if (pred != null)
// 如果前置節(jié)點不為空，刪除當(dāng)前節(jié)點：
// 讓當(dāng)前節(jié)點的上一個節(jié)點，指向當(dāng)前節(jié)點的下一個節(jié)點。
pred.next = e.next;
// 條件成里：說明當(dāng)前節(jié)點即為頭結(jié)點
else
// 如果前置節(jié)點為空，說明是桶中第一個元素，刪除之：
// 只需要將桶位設(shè)置為頭結(jié)點的下一個節(jié)點。
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
// 遍歷到鏈表尾部還沒找到元素，跳出循環(huán)
if ((e = e.next) == null)
break;
}
}
java // --------------------------------------------------------------------
// CASE8: f instanceof TreeBin
// 條件成立：TreeBin節(jié)點。
else if (f instanceof TreeBin) {
// 校驗標(biāo)記置為true
validated = true;
java // 轉(zhuǎn)換為實際類型 TreeBin t
TreeBin<K,V> t = (TreeBin<K,V>)f;
// r 表示 紅黑樹根節(jié)點
// p 表示 紅黑樹中查找到對應(yīng)key 一致的node
TreeNode<K,V> r, p;
java // 遍歷樹找到了目標(biāo)節(jié)點：
// 條件一：(r = t.root) != null 理論上是成立
// 條件二：TreeNode.findTreeNode 以當(dāng)前節(jié)點為入口，向下查找key（包括本身節(jié)點）
// true->說明查找到相應(yīng)key 對應(yīng)的node節(jié)點，會賦值給p
if ((r = t.root) != null &&
(p = r.findTreeNode(hash, key, null)) != null) {
// 保存p.val 到pv
V pv = p.val;
java // 檢查目標(biāo)節(jié)點舊value是否等于cv：
// 條件一：cv == null 成立：不必對比value，就做替換或者刪除操作
// 條件二：cv == pv ||(pv != null && cv.equals(pv)) 成立：說明“對比值”與當(dāng)前p節(jié)點的值 一致
if (cv == null || cv == pv ||
(pv != null && cv.equals(pv))) {
// 替換或者刪除操作
oldVal = pv;
java // 如果value不為空則替換舊值
// 條件成立：替換操作
if (value != null)
p.val = value;
java // 如果value為空則刪除元素
// 刪除操作
else if (t.removeTreeNode(p))
// 如果刪除后樹的元素個數(shù)較少則退化成鏈表
// t.removeTreeNode(p)這個方法返回true表示刪除節(jié)點后樹的元素個數(shù)較少
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
// ----------------------------------------------------------------------------
// CASEn: 如果處理過，不管有沒有找到元素都返回
// 當(dāng)其他線程修改過桶位頭結(jié)點時，當(dāng)前線程 sync 頭結(jié)點 鎖錯對象時，validated 為false，會進入下次for自旋:
if (validated) {
// 如果找到了元素，返回其舊值
if (oldVal != null) {
// 替換的值 為null，說明當(dāng)前是一次刪除操作，oldVal ！=null 成立，說明刪除成功，更新當(dāng)前元素個數(shù)計數(shù)器。
// 如果要替換的值為空，元素個數(shù)減1
if (value == null)
addCount(-1L, -1);
return oldVal;
}
break;
}
}
}
java // 沒找到元素返回空
return null;
}
小節(jié)：
（1）計算hash；
（2）如果所在的桶不存在，表示沒有找到目標(biāo)元素，返回；
（3）如果正在擴容，則協(xié)助擴容完成后再進行刪除操作；
（4）如果是以鏈表形式存儲的，則遍歷整個鏈表查找元素，找到之后再刪除；
（5）如果是以樹形式存儲的，則遍歷樹查找元素，找到之后再刪除；
（6）如果是以樹形式存儲的，刪除元素之后樹較小，則退化成鏈表；
（7）如果確實刪除了元素，則整個map元素個數(shù)減1，并返回舊值；
（8）如果沒有刪除元素，則返回null；
本篇文章結(jié)束，ConcurrentHashMap的大部分知識點分析完畢，下面一篇文章最后再分析一下TreeBin就收尾了！
相關(guān)文章
Java多線程中的wait、notify和park、unpark的使用詳解
這篇文章主要介紹了Java多線程中的wait、notify和park、unpark的使用詳解,它們都是線程之間進行協(xié)作的手段,都屬于 Object 對象的方法,必須獲得此對象的鎖,才能調(diào)用這幾個方法,需要的朋友可以參考下2023-12-12
這篇文章主要介紹了Java如何防止JS腳本注入代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-09-09
本篇將對定義在 XMl 文件中的 bean，從靜態(tài)的的定義到變成可以使用的對象的過程，即 bean 的加載和獲取的過程進行一個整體的了解2017-05-05
SpringBoot實現(xiàn)動態(tài)控制定時任務(wù)支持多參數(shù)功能
這篇文章主要介紹了SpringBoot實現(xiàn)動態(tài)控制定時任務(wù)-支持多參數(shù)功能，本文通過實例代碼給大家介紹的非常詳細，具有一定的參考借鑒價值,需要的朋友可以參考下2019-05-05
Java程序員有許多應(yīng)遵循的守則或最佳實踐方式。本文概述了每個開發(fā)者最應(yīng)該遵循的10條守則或戒律，如果不遵循它們，將會導(dǎo)致災(zāi)難性后果。2015-09-09
這篇文章主要為大家詳細介紹了java簡單實現(xiàn)計算器，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-12-12
這篇文章主要介紹了java compareTo和compare方法比較詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-09-09
這篇文章主要介紹了Java SoftReference類案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-08-08
Spring?Security自定義登錄頁面認(rèn)證過程常用配置
這篇文章主要為大家介紹了Spring?Security自定義登錄頁面認(rèn)證過程常用配置示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-08-08
mybatis執(zhí)行錯誤但sql執(zhí)行正常問題
這篇文章主要介紹了mybatis執(zhí)行錯誤但sql執(zhí)行正常問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-01-01