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