ConcurrentHashMap: get、remove方法的示例分析

小編給大家分享一下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ù)組長度
    // 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過數(shù)據(jù)，并且map內(nèi)部的table也已經(jīng)初始化完畢
    // 		false -> 表示創(chuàng)建完map后，并沒有put過數(shù)據(jù)，map內(nèi)部的table是延遲初始化的，只有第一次寫數(shù)據(jù)時(shí)會觸發(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è)元素就是要找的元素，則直接返回
        // 對比頭結(jié)點(diǎn)hash與查詢key的hash是否一致
        // 條件成立：說明頭結(jié)點(diǎn)與查詢Key的hash值完全一致
        if ((eh = e.hash) == h) {
            // 完全比對 查詢key 和 頭結(jié)點(diǎn)的key
            // 條件成立：說明頭結(jié)點(diǎn)就是查詢數(shù)據(jù)
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                // 當(dāng)e的hash值以及e對應(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) -> 說明當(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條件不滿足！
		// 說明是當(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會分2中情況：

情況一：eh=-1 是fwd結(jié)點(diǎn) -> 說明當(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)。我們來分析一下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)，其它寫線程或讀線程看到后，會有不同邏輯）
        Node<K,V>[] tab = nextTable;
java        // ------------------------------------------------------------------------------
        // 自旋1
        outer: for (;;) {
            // n 表示為擴(kuò)容而創(chuàng)建的新表的長度
            // e 表示在擴(kuò)容而創(chuàng)建新表時(shí)，使用尋址算法得到的桶位頭結(jié)點(diǎn)
            Node<K,V> e; int n;
java            // 條件一：永遠(yuǎn)不成立
            // 條件二：永遠(yuǎn)不成立
            // 條件三：永遠(yuǎn)不成立
            // 條件四：在新擴(kuò)容表中重新路由定位 hash 對應(yīng)的頭結(jié)點(diǎn)
            //        true ->  1.在oldTable中對應(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ò)容后的表對應(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條件成立：說明新擴(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)
                        // 說明此桶位 為 TreeBin 節(jié)點(diǎn)，使用TreeBin.find 查找紅黑樹中相應(yīng)節(jié)點(diǎn)。
                        return e.find(h, k);
                }
java                // 前置條件：當(dāng)前桶位頭結(jié)點(diǎn) 并沒有命中查詢，說明此桶位是鏈表
                // 1.將當(dāng)前元素指向鏈表的下一個(gè)元素
                // 2.判斷當(dāng)前元素的下一個(gè)位置是否為空
                //   	true -> 說明迭代到鏈表末尾，未找到對應(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）獲取元素沒有加鎖；

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，則需要既比對key，還要比對cv，這樣個(gè)參數(shù)都一致，才能替換成目標(biāo)值
 */
final V replaceNode(Object key, V value, Object cv) {
    // 計(jì)算key經(jīng)過擾動(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ù)組長度
        // 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)，說明當(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)記是否處理過
            boolean validated = false;
            // 加鎖當(dāng)前桶位頭結(jié)點(diǎn)，加鎖成功之后會進(jìn)入代碼塊。
            synchronized (f) {
                // 判斷sync加鎖是否為當(dāng)前桶位頭節(jié)點(diǎn)，防止其它線程，在當(dāng)前線程加鎖成功之前，修改過桶位 的頭結(jié)點(diǎn)，導(dǎo)致鎖錯(cuò)對象！
java                // --------------------------------------------------------------------
        		// CASE4:  tabAt(tab, i) == f 再次驗(yàn)證當(dāng)前桶第一個(gè)元素是否被修改過
                // 條件成立：說明當(dāng)前桶位頭結(jié)點(diǎn)仍然為f，其它線程沒修改過！
                if (tabAt(tab, i) == f) {
                    // --------------------------------------------------------------------
        			// CASE5:  fh >= 0 
                    // 條件成立：說明桶位為鏈表或者單個(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->說明當(dāng)前節(jié)點(diǎn)的hash與查找節(jié)點(diǎn)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é)點(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ù)返回會用到~
                                    oldVal = ev;
java                                    // 目標(biāo)value不等于null
                                    // 如果條件成立：說明當(dāng)前是一個(gè)替換操作
                                    if (value != null)
                                        // 直接替換
                                        e.val = value;
                                    // 條件成立：說明當(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;
									// 條件成里：說明當(dāng)前節(jié)點(diǎn)即為頭結(jié)點(diǎn)
                                    else
                                        // 如果前置節(jié)點(diǎn)為空，說明是桶中第一個(gè)元素，刪除之：
                                        // 只需要將桶位設(shè)置為頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。
                                        setTabAt(tab, i, e.next);
                                }
                                break;
                            }
                            pred = e;
                            // 遍歷到鏈表尾部還沒找到元素，跳出循環(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 表示 紅黑樹中查找到對應(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->說明查找到相應(yīng)key 對應(yīng)的node節(jié)點(diǎn)，會賦值給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 成立：不必對比value，就做替換或者刪除操作
                            // 條件二：cv == pv ||(pv != null && cv.equals(pv)) 成立：說明“對比值”與當(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: 如果處理過，不管有沒有找到元素都返回
            // 當(dāng)其他線程修改過桶位頭結(jié)點(diǎn)時(shí)，當(dāng)前線程 sync 頭結(jié)點(diǎn) 鎖錯(cuò)對象時(shí)，validated 為false，會進(jìn)入下次for自旋:
            if (validated) {
                // 如果找到了元素，返回其舊值
                if (oldVal != null) {
                    // 替換的值 為null，說明當(dāng)前是一次刪除操作，oldVal ！=null 成立，說明刪除成功，更新當(dāng)前元素個(gè)數(shù)計(jì)數(shù)器。
                    // 如果要替換的值為空，元素個(gè)數(shù)減1
                    if (value == null)
                        addCount(-1L, -1);
                    return oldVal;
                }
                break;
            }
        }
    }
java	// 沒找到元素返回空
    return null;
}

小節(jié)：

（1）計(jì)算hash；

（2）如果所在的桶不存在，表示沒有找到目標(biāo)元素，返回；

（3）如果正在擴(kuò)容，則協(xié)助擴(kuò)容完成后再進(jìn)行刪除操作；

（4）如果是以鏈表形式存儲的，則遍歷整個(gè)鏈表查找元素，找到之后再刪除；

（5）如果是以樹形式存儲的，則遍歷樹查找元素，找到之后再刪除；

（6）如果是以樹形式存儲的，刪除元素之后樹較小，則退化成鏈表；

（7）如果確實(shí)刪除了元素，則整個(gè)map元素個(gè)數(shù)減1，并返回舊值；

（8）如果沒有刪除元素，則返回null；

看完了這篇文章，相信你對“ConcurrentHashMap: get、remove方法的示例分析”有了一定的了解，如果想了解更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！