解析ConcurrentHashMap: get、remove方法分析
前面幾篇文章分析瞭並發HashMap的put方法及其相關方法，transfer方法，那麼接下來本篇文章相對之前幾篇難度會小一些。
本篇文章介紹ConcurrentHashMap的get方法和remove方法。
1、get方法
get方法：獲取元素，根據目標key所在桶的第一個元素的不同采用不同的方式獲取元素，關鍵點在於find()方法的重寫。
public V get(Object key) {
// tab 引用map.table
// e 當前元素(用於循環遍歷)
// p 目標節點
// n table數組長度
// eh 當前元素hash
// ek 當前元素key
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
// 根據key.hashCode()計算hash: 擾動運算後得到得到更散列的hash值
int h = spread(key.hashCode());
java // --------------------------------------------------------------------------------
// CASE1:
// 如果元素所在的桶存在且裡面有元素
// 條件一：(tab = table) != null
// true -> 表示已經put過數據，並且map內部的table也已經初始化完畢
// false -> 表示創建完map後，並沒有put過數據，map內部的table是延遲初始化的，隻有第一次寫數據時會觸發初始化創建table邏輯
// 條件二：(n = tab.length) > 0 如果為 true-> 表示table已經初始化
// 條件三：(e = tabAt(tab, (n - 1) & h)) != null
// true -> 當前key尋址的桶位有值
// false -> 當前key尋址的桶位中是null，是null直接返回null
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 進入if代碼塊內部的前置條件：當前桶位有數據
java // 如果第一個元素就是要找的元素，則直接返回
// 對比頭結點hash與查詢key的hash是否一致
// 條件成立：說明頭結點與查詢Key的hash值完全一致
if ((eh = e.hash) == h) {
// 完全比對 查詢key 和 頭結點的key
// 條件成立：說明頭結點就是查詢數據
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
// 當e的hash值以及e對應的key都匹配目標元素時，則找到瞭，直接返回~
return e.val;
}
java // --------------------------------------------------------------------------------
// CASE2: eh < 0
// 條件成立：即，hash小於0 分2種情況，是樹或者正在擴容,需要借助find方法尋找元素，find的尋找方式依據Node的不同子類有不同的實現方式:
// 情況一：eh=-1 是fwd結點 -> 說明當前table正在擴容，且當前查詢的這個桶位的數據已經被遷移走瞭，需要借助fwd結點的內部方法find去查詢
// 情況二：eh=-2 是TreeBin節點 -> 需要使用TreeBin 提供的find方法查詢。
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
java // --------------------------------------------------------------------------------
// CASE3: 前提條件 -> CASE1和CASE2條件不滿足！
// 說明是當前桶位已經形成鏈表的這種情況: 遍歷整個鏈表尋找元素
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 內部類(FWD結點)
在get方法CASE2中，eh < 0會分2中情況：
情況一：eh=-1 是fwd結點 -> 說明當前table正在擴容，且當前查詢的這個桶位的數據已經被遷移走瞭，需要借助fwd結點的內部方法find去查詢。
情況二：eh = -2 是TreeBin節點 -> 需要使用TreeBin 提供的find方法查詢。
下面就分析一下情況一，即當前桶位中是fwd結點。我們來分析一下FWD這個內部類，以及其內部的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結點的find方法：
Node<K,V> find(int h, Object k) {
// loop to avoid arbitrarily deep recursion on forwarding nodes
// tab 一定不為空：整個ConcurrentHashMap源碼中，隻有一個地方實例化ForwardingNode，就是在transfer遷移數據方法中執行瞭：ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);（當某個桶位數據處理完畢後，將此桶位設置為fwd節點，其它寫線程或讀線程看到後，會有不同邏輯）
Node<K,V>[] tab = nextTable;
java // ------------------------------------------------------------------------------
// 自旋1
outer: for (;;) {
// n 表示為擴容而創建的新表的長度
// e 表示在擴容而創建新表時，使用尋址算法得到的桶位頭結點
Node<K,V> e; int n;
java // 條件一：永遠不成立
// 條件二：永遠不成立
// 條件三：永遠不成立
// 條件四：在新擴容表中重新路由定位 hash 對應的頭結點
// true -> 1.在oldTable中對應的桶位在遷移之前就是null
// false -> 2.擴容完成後，有其它寫線程，將此桶位設置為瞭null
if (k == null || tab == null || (n = tab.length) == 0 ||
(e = tabAt(tab, (n - 1) & h)) == null)
return null;
java // ---------------------------------------------------------------------------
// 自旋2
// 前置條件：擴容後的表對應hash的桶位一定不是null，e為此桶位的頭結點
// e可能為哪些node類型？
// 1.node 類型
// 2.TreeBin 類型
// 3.FWD類型
for (;;) {
// eh 新擴容後表指定桶位的當前節點的hash
// ek 新擴容後表指定桶位的當前節點的key
int eh; K ek;
// CASE1條件成立：說明新擴容後的表，當前命中桶位中的數據，即為查詢想要數據。
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類型（新擴容的表，在並發很大的情況下，可能在此方法再次拿到FWD類型），即可能又發生瞭擴容
if (eh < 0) {
// 判斷是否是FWD結點
if (e instanceof ForwardingNode) {
// 是FWD結點
tab = ((ForwardingNode<K,V>)e).nextTable;
// 跳轉到自旋1
continue outer;
}
else// 不是FWD結點
// 說明此桶位 為 TreeBin 節點，使用TreeBin.find 查找紅黑樹中相應節點。
return e.find(h, k);
}
java // 前置條件：當前桶位頭結點 並沒有命中查詢，說明此桶位是鏈表
// 1.將當前元素指向鏈表的下一個元素
// 2.判斷當前元素的下一個位置是否為空
// true -> 說明迭代到鏈表末尾，未找到對應的數據，返回Null
if ((e = e.next) == null)
return null;
}
}
}
}
小節：
（1）hash到元素所在的桶；
（2）如果桶中第一個元素就是該找的元素，直接返回；
（3）如果是樹或者正在遷移元素，則調用各自Node子類的find()方法尋找元素；
（4）如果是鏈表，遍歷整個鏈表尋找元素；
（5）獲取元素沒有加鎖；
2、remove方法
remove方法：刪除元素跟添加元素一樣，都是先找到元素所在的桶，然後采用分段鎖的思想鎖住整個桶，再進行操作。
public V remove(Object key) {
// 調用替換節點方法
return replaceNode(key, null, null);
}
java/**
* 結點替換：
* 參數1：Object key -> 就表示當前結點的key
* 參數2：V value -> 要替換的目標值
* 參數3：Object cv（compare Value） ->
* 如果cv不為null，則需要既比對key，還要比對cv，這樣個參數都一致，才能替換成目標值
*/
final V replaceNode(Object key, V value, Object cv) {
// 計算key經過擾動運算後得到的hash
int hash = spread(key.hashCode());
// 自旋
for (Node<K,V>[] tab = table;;) {
// f表示桶位頭結點
// n表示當前table數組長度
// i表示hash命中桶位下標
// fh表示桶位頭結點hash
Node<K,V> f; int n, i, fh;
java // ----------------------------------------------------------------------------
// CASE1：
// 條件一：tab == null
// true -> 表示當前map.table尚未初始化..
// false -> 表示當前map.table已經初始化
// 條件二：(n = tab.length) == 0
// true -> 表示當前map.table尚未初始化..
// false -> 已經初始化
// 條件三：(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)
// 如果目標key所在的桶不存在，跳出循環返回null
break;
java // ----------------------------------------------------------------------------
// CASE2：
// 前置條件CASE2 ~ CASE3：當前桶位不是null
// 條件成立：fwd結點，說明當前table正在擴容中，當前是個寫操作，所以當前線程需要協助table完成擴容。
else if ((fh = f.hash) == MOVED)
// 如果正在擴容中，則協助擴容
tab = helpTransfer(tab, f);
java // ----------------------------------------------------------------------------
// CASE3:
// 前置條件CASE2 ~ CASE3：當前桶位不是null
// 當前桶位是一個有數據的桶位，桶中可能是 "鏈表"也可能是"紅黑樹"TreeBin
else {
// 保留替換之前的數據引用
V oldVal = null;
// 校驗標記,在下面的CASEn中的if判斷使用：標記是否處理過
boolean validated = false;
// 加鎖當前桶位頭結點，加鎖成功之後會進入代碼塊。
synchronized (f) {
// 判斷sync加鎖是否為當前桶位頭節點，防止其它線程，在當前線程加鎖成功之前，修改過桶位 的頭結點，導致鎖錯對象！
java // --------------------------------------------------------------------
// CASE4: tabAt(tab, i) == f 再次驗證當前桶第一個元素是否被修改過
// 條件成立：說明當前桶位頭結點仍然為f，其它線程沒修改過！
if (tabAt(tab, i) == f) {
// --------------------------------------------------------------------
// CASE5: fh >= 0
// 條件成立：說明桶位為鏈表或者單個node
if (fh >= 0) {
// 校驗標記置為true
validated = true;
java // e 表示當前循環處理結點
// pred 表示當前循環節點的上一個節點
Node<K,V> e = f, pred = null;
// 遍歷鏈表尋找目標節點
for (;;) {
// 表示當前節點key
K ek;
java // ------------------------------------------------------------
// CASE6:
// 條件一：e.hash == hash
// true->說明當前節點的hash與查找節點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)))) {
// 找到瞭目標節點：當前節點的value，
V ev = e.val;
java // -----------------------------------------------------
// CASE7: 檢查目標節點舊value是否等於cv
// 條件一：cv == null
// true -> 替換的值為null那麼就是一個刪除操作
// 條件二：cv == ev || (ev != null && cv.equals(ev))
// true -> 那麼是一個替換操作
if (cv == null || cv == ev ||
(ev != null && cv.equals(ev))) {
// 刪除 或者 替換
// 將當前節點的值 賦值給 oldVal 後續返回會用到~
oldVal = ev;
java // 目標value不等於null
// 如果條件成立：說明當前是一個替換操作
if (value != null)
// 直接替換
e.val = value;
// 條件成立：說明當前節點非頭結點
else if (pred != null)
// 如果前置節點不為空，刪除當前節點：
// 讓當前節點的上一個節點，指向當前節點的下一個節點。
pred.next = e.next;
// 條件成裡：說明當前節點即為頭結點
else
// 如果前置節點為空，說明是桶中第一個元素，刪除之：
// 隻需要將桶位設置為頭結點的下一個節點。
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
// 遍歷到鏈表尾部還沒找到元素，跳出循環
if ((e = e.next) == null)
break;
}
}
java // --------------------------------------------------------------------
// CASE8: f instanceof TreeBin
// 條件成立：TreeBin節點。
else if (f instanceof TreeBin) {
// 校驗標記置為true
validated = true;
java // 轉換為實際類型 TreeBin t
TreeBin<K,V> t = (TreeBin<K,V>)f;
// r 表示 紅黑樹根節點
// p 表示 紅黑樹中查找到對應key 一致的node
TreeNode<K,V> r, p;
java // 遍歷樹找到瞭目標節點：
// 條件一：(r = t.root) != null 理論上是成立
// 條件二：TreeNode.findTreeNode 以當前節點為入口，向下查找key（包括本身節點）
// true->說明查找到相應key 對應的node節點，會賦值給p
if ((r = t.root) != null &&
(p = r.findTreeNode(hash, key, null)) != null) {
// 保存p.val 到pv
V pv = p.val;
java // 檢查目標節點舊value是否等於cv：
// 條件一：cv == null 成立：不必對比value，就做替換或者刪除操作
// 條件二：cv == pv ||(pv != null && cv.equals(pv)) 成立：說明“對比值”與當前p節點的值 一致
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))
// 如果刪除後樹的元素個數較少則退化成鏈表
// t.removeTreeNode(p)這個方法返回true表示刪除節點後樹的元素個數較少
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
// ----------------------------------------------------------------------------
// CASEn: 如果處理過，不管有沒有找到元素都返回
// 當其他線程修改過桶位頭結點時，當前線程 sync 頭結點 鎖錯對象時，validated 為false，會進入下次for自旋:
if (validated) {
// 如果找到瞭元素，返回其舊值
if (oldVal != null) {
// 替換的值 為null，說明當前是一次刪除操作，oldVal ！=null 成立，說明刪除成功，更新當前元素個數計數器。
// 如果要替換的值為空，元素個數減1
if (value == null)
addCount(-1L, -1);
return oldVal;
}
break;
}
}
}
java // 沒找到元素返回空
return null;
}
小節：
（1）計算hash；
（2）如果所在的桶不存在，表示沒有找到目標元素，返回；
（3）如果正在擴容，則協助擴容完成後再進行刪除操作；
（4）如果是以鏈表形式存儲的，則遍歷整個鏈表查找元素，找到之後再刪除；
（5）如果是以樹形式存儲的，則遍歷樹查找元素，找到之後再刪除；
（6）如果是以樹形式存儲的，刪除元素之後樹較小，則退化成鏈表；
（7）如果確實刪除瞭元素，則整個map元素個數減1，並返回舊值；
（8）如果沒有刪除元素，則返回null；
本篇文章結束，ConcurrentHashMap的大部分知識點分析完畢，下面一篇文章最後再分析一下TreeBin就收尾瞭！
推薦閱讀：
- 淺談Java源碼ConcurrentHashMap
- 解析ConcurrentHashMap: 紅黑樹的代理類(TreeBin)
- JDK1.8中的ConcurrentHashMap使用及場景分析
- Java源碼解析之ConcurrentHashMap
- ConcurrentHashMap是如何保證線程安全