本章接著上兩章，鏈接直達(dá)：

創(chuàng)新互聯(lián)是專(zhuān)業(yè)的瀘州網(wǎng)站建設(shè)公司，瀘州接單;提供成都網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì),網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專(zhuān)業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行瀘州網(wǎng)站開(kāi)發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專(zhuān)業(yè)做搜索引擎喜愛(ài)的網(wǎng)站,專(zhuān)業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來(lái)合作!

死磕 java集合之ConcurrentHashMap源碼分析（一）

死磕 java集合之ConcurrentHashMap源碼分析（二）

---

刪除元素

刪除元素跟添加元素一樣，都是先找到元素所在的桶，然后采用分段鎖的思想鎖住整個(gè)桶，再進(jìn)行操作。

public V remove(Object key) {
    // 調(diào)用替換節(jié)點(diǎn)方法
    return replaceNode(key, null, null);
}

final V replaceNode(Object key, V value, Object cv) {
    // 計(jì)算hash
    int hash = spread(key.hashCode());
    // 自旋
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0 ||
                (f = tabAt(tab, i = (n - 1) & hash)) == null)
            // 如果目標(biāo)key所在的桶不存在，跳出循環(huán)返回null
            break;
        else if ((fh = f.hash) == MOVED)
            // 如果正在擴(kuò)容中，協(xié)助擴(kuò)容
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            // 標(biāo)記是否處理過(guò)
            boolean validated = false;
            synchronized (f) {
                // 再次驗(yàn)證當(dāng)前桶第一個(gè)元素是否被修改過(guò)
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        // fh>=0表示是鏈表節(jié)點(diǎn)
                        validated = true;
                        // 遍歷鏈表尋找目標(biāo)節(jié)點(diǎn)
                        for (Node<K,V> e = f, pred = null;;) {
                            K ek;
                            if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                            (ek != null && key.equals(ek)))) {
                                // 找到了目標(biāo)節(jié)點(diǎn)
                                V ev = e.val;
                                // 檢查目標(biāo)節(jié)點(diǎn)舊value是否等于cv
                                if (cv == null || cv == ev ||
                                        (ev != null && cv.equals(ev))) {
                                    oldVal = ev;
                                    if (value != null)
                                        // 如果value不為空則替換舊值
                                        e.val = value;
                                    else if (pred != null)
                                        // 如果前置節(jié)點(diǎn)不為空
                                        // 刪除當(dāng)前節(jié)點(diǎn)
                                        pred.next = e.next;
                                    else
                                        // 如果前置節(jié)點(diǎn)為空
                                        // 說(shuō)明是桶中第一個(gè)元素，刪除之
                                        setTabAt(tab, i, e.next);
                                }
                                break;
                            }
                            pred = e;
                            // 遍歷到鏈表尾部還沒(méi)找到元素，跳出循環(huán)
                            if ((e = e.next) == null)
                                break;
                        }
                    }
                    else if (f instanceof TreeBin) {
                        // 如果是樹(shù)節(jié)點(diǎn)
                        validated = true;
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        TreeNode<K,V> r, p;
                        // 遍歷樹(shù)找到了目標(biāo)節(jié)點(diǎn)
                        if ((r = t.root) != null &&
                                (p = r.findTreeNode(hash, key, null)) != null) {
                            V pv = p.val;
                            // 檢查目標(biāo)節(jié)點(diǎn)舊value是否等于cv
                            if (cv == null || cv == pv ||
                                    (pv != null && cv.equals(pv))) {
                                oldVal = pv;
                                if (value != null)
                                    // 如果value不為空則替換舊值
                                    p.val = value;
                                else if (t.removeTreeNode(p))
                                    // 如果value為空則刪除元素
                                    // 如果刪除后樹(shù)的元素個(gè)數(shù)較少則退化成鏈表
                                    // t.removeTreeNode(p)這個(gè)方法返回true表示刪除節(jié)點(diǎn)后樹(shù)的元素個(gè)數(shù)較少
                                    setTabAt(tab, i, untreeify(t.first));
                            }
                        }
                    }
                }
            }
            // 如果處理過(guò)，不管有沒(méi)有找到元素都返回
            if (validated) {
                // 如果找到了元素，返回其舊值
                if (oldVal != null) {
                    // 如果要替換的值為空，元素個(gè)數(shù)減1
                    if (value == null)
                        addCount(-1L, -1);
                    return oldVal;
                }
                break;
            }
        }
    }
    // 沒(méi)找到元素返回空
    return null;
}

（1）計(jì)算hash；

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

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

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

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

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

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

（8）如果沒(méi)有刪除元素，則返回null；

獲取元素

獲取元素，根據(jù)目標(biāo)key所在桶的第一個(gè)元素的不同采用不同的方式獲取元素，關(guān)鍵點(diǎn)在于find()方法的重寫(xiě)。

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    // 計(jì)算hash
    int h = spread(key.hashCode());
    // 如果元素所在的桶存在且里面有元素
    if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
        // 如果第一個(gè)元素就是要找的元素，直接返回
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0)
            // hash小于0，說(shuō)明是樹(shù)或者正在擴(kuò)容
            // 使用find尋找元素，find的尋找方式依據(jù)Node的不同子類(lèi)有不同的實(shí)現(xiàn)方式
            return (p = e.find(h, key)) != null ? p.val : null;

        // 遍歷整個(gè)鏈表尋找元素
        while ((e = e.next) != null) {
            if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

（1）hash到元素所在的桶；

（2）如果桶中第一個(gè)元素就是該找的元素，直接返回；

（3）如果是樹(shù)或者正在遷移元素，則調(diào)用各自Node子類(lèi)的find()方法尋找元素；

（4）如果是鏈表，遍歷整個(gè)鏈表尋找元素；

（5）獲取元素沒(méi)有加鎖；

獲取元素個(gè)數(shù)

元素個(gè)數(shù)的存儲(chǔ)也是采用分段的思想，獲取元素個(gè)數(shù)時(shí)需要把所有段加起來(lái)。

public int size() {
    // 調(diào)用sumCount()計(jì)算元素個(gè)數(shù)
    long n = sumCount();
    return ((n < 0L) ? 0 :
            (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                    (int)n);
}

final long sumCount() {
    // 計(jì)算CounterCell所有段及baseCount的數(shù)量之和
    CounterCell[] as = counterCells; CounterCell a;
    long sum = baseCount;
    if (as != null) {
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                sum += a.value;
        }
    }
    return sum;
}

（1）元素的個(gè)數(shù)依據(jù)不同的線程存在在不同的段里；（見(jiàn)addCounter()分析）

（2）計(jì)算CounterCell所有段及baseCount的數(shù)量之和；

（3）獲取元素個(gè)數(shù)沒(méi)有加鎖；

總結(jié)

（1）ConcurrentHashMap是HashMap的線程安全版本；

（2）ConcurrentHashMap采用（數(shù)組 + 鏈表 + 紅黑樹(shù)）的結(jié)構(gòu)存儲(chǔ)元素；

（3）ConcurrentHashMap相比于同樣線程安全的HashTable，效率要高很多；

（4）ConcurrentHashMap采用的鎖有 synchronized，CAS，自旋鎖，分段鎖，volatile等；

（5）ConcurrentHashMap中沒(méi)有threshold和loadFactor這兩個(gè)字段，而是采用sizeCtl來(lái)控制；

（6）sizeCtl = -1，表示正在進(jìn)行初始化；

（7）sizeCtl = 0，默認(rèn)值，表示后續(xù)在真正初始化的時(shí)候使用默認(rèn)容量；

（8）sizeCtl > 0，在初始化之前存儲(chǔ)的是傳入的容量，在初始化或擴(kuò)容后存儲(chǔ)的是下一次的擴(kuò)容門(mén)檻；

（9）sizeCtl = (resizeStamp << 16) + (1 + nThreads)，表示正在進(jìn)行擴(kuò)容，高位存儲(chǔ)擴(kuò)容郵戳，低位存儲(chǔ)擴(kuò)容線程數(shù)加1；

（10）更新操作時(shí)如果正在進(jìn)行擴(kuò)容，當(dāng)前線程協(xié)助擴(kuò)容；

（11）更新操作會(huì)采用synchronized鎖住當(dāng)前桶的第一個(gè)元素，這是分段鎖的思想；

（12）整個(gè)擴(kuò)容過(guò)程都是通過(guò)CAS控制sizeCtl這個(gè)字段來(lái)進(jìn)行的，這很關(guān)鍵；

（13）遷移完元素的桶會(huì)放置一個(gè)ForwardingNode節(jié)點(diǎn)，以標(biāo)識(shí)該桶遷移完畢；

（14）元素個(gè)數(shù)的存儲(chǔ)也是采用的分段思想，類(lèi)似于LongAdder的實(shí)現(xiàn)；

（15）元素個(gè)數(shù)的更新會(huì)把不同的線程hash到不同的段上，減少資源爭(zhēng)用；

（16）元素個(gè)數(shù)的更新如果還是出現(xiàn)多個(gè)線程同時(shí)更新一個(gè)段，則會(huì)擴(kuò)容段（CounterCell）；

（17）獲取元素個(gè)數(shù)是把所有的段（包括baseCount和CounterCell）相加起來(lái)得到的；

（18）查詢(xún)操作是不會(huì)加鎖的，所以ConcurrentHashMap不是強(qiáng)一致性的；

（19）ConcurrentHashMap中不能存儲(chǔ)key或value為null的元素；

彩蛋——值得學(xué)習(xí)的技術(shù)

ConcurrentHashMap中有哪些值得學(xué)習(xí)的技術(shù)呢？

我認(rèn)為有以下幾點(diǎn)：

（1）CAS + 自旋，樂(lè)觀鎖的思想，減少線程上下文切換的時(shí)間；

（2）分段鎖的思想，減少同一把鎖爭(zhēng)用帶來(lái)的低效問(wèn)題；

（3）CounterCell，分段存儲(chǔ)元素個(gè)數(shù)，減少多線程同時(shí)更新一個(gè)字段帶來(lái)的低效；

（4）@sun.misc.Contended（CounterCell上的注解），避免偽共享；（p.s.偽共享我們后面也會(huì)講的^^）

（5）多線程協(xié)同進(jìn)行擴(kuò)容；

（6）你又學(xué)到了哪些呢？

彩蛋——不能解決的問(wèn)題

ConcurrentHashMap不能解決什么問(wèn)題呢？

請(qǐng)看下面的例子：

private static final Map<Integer, Integer> map = new ConcurrentHashMap<>();

public void unsafeUpdate(Integer key, Integer value) {
    Integer oldValue = map.get(key);
    if (oldValue == null) {
        map.put(key, value);
    }
}

這里如果有多個(gè)線程同時(shí)調(diào)用unsafeUpdate()這個(gè)方法，ConcurrentHashMap還能保證線程安全嗎？

答案是不能。因?yàn)間et()之后if之前可能有其它線程已經(jīng)put()了這個(gè)元素，這時(shí)候再put()就把那個(gè)線程put()的元素覆蓋了。

那怎么修改呢？

答案也很簡(jiǎn)單，使用putIfAbsent()方法，它會(huì)保證元素不存在時(shí)才插入元素，如下：

public void safeUpdate(Integer key, Integer value) {
    map.putIfAbsent(key, value);
}

那么，如果上面oldValue不是跟null比較，而是跟一個(gè)特定的值比如1進(jìn)行比較怎么辦？也就是下面這樣：

public void unsafeUpdate(Integer key, Integer value) {
    Integer oldValue = map.get(key);
    if (oldValue == 1) {
        map.put(key, value);
    }
}

這樣的話(huà)就沒(méi)辦法使用putIfAbsent()方法了。

其實(shí)，ConcurrentHashMap還提供了另一個(gè)方法叫replace(K key, V oldValue, V newValue)可以解決這個(gè)問(wèn)題。

replace(K key, V oldValue, V newValue)這個(gè)方法可不能亂用，如果傳入的newValue是null，則會(huì)刪除元素。

public void safeUpdate(Integer key, Integer value) {
    map.replace(key, 1, value);
}

那么，如果if之后不是簡(jiǎn)單的put()操作，而是還有其它業(yè)務(wù)操作，之后才是put()，比如下面這樣，這該怎么辦呢？

public void unsafeUpdate(Integer key, Integer value) {
    Integer oldValue = map.get(key);
    if (oldValue == 1) {
        System.out.println(System.currentTimeMillis());
        /**
         * 其它業(yè)務(wù)操作
         */
        System.out.println(System.currentTimeMillis());

        map.put(key, value);
    }
}

這時(shí)候就沒(méi)辦法使用ConcurrentHashMap提供的方法了，只能業(yè)務(wù)自己來(lái)保證線程安全了，比如下面這樣：

public void safeUpdate(Integer key, Integer value) {
    synchronized (map) {
        Integer oldValue = map.get(key);
        if (oldValue == null) {
            System.out.println(System.currentTimeMillis());
            /**
             * 其它業(yè)務(wù)操作
             */
            System.out.println(System.currentTimeMillis());

            map.put(key, value);
        }
    }
}

這樣雖然不太友好，但是最起碼能保證業(yè)務(wù)邏輯是正確的。

當(dāng)然，這里使用ConcurrentHashMap的意義也就不大了，可以換成普通的HashMap了。

上面只是舉一個(gè)簡(jiǎn)單的例子，我們不能聽(tīng)說(shuō)ConcurrentHashMap是線程安全的，就認(rèn)為它無(wú)論什么情況下都是線程安全的，還是那句話(huà)盡信書(shū)不如無(wú)書(shū)。

這也正是我們讀源碼的目的之一，了解其本質(zhì)，才能在我們的實(shí)際工作中少挖坑，不論是挖給別人還是挖給自己^^。

---

網(wǎng)頁(yè)標(biāo)題：死磕java集合之ConcurrentHashMap源碼分析（三）
瀏覽路徑：http://aaarwkj.com/article24/jeegje.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、營(yíng)銷(xiāo)型網(wǎng)站建設(shè)、面包屑導(dǎo)航、ChatGPT、商城網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)