成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

JDK源碼那些事兒之并發(fā)ConcurrentHashMap下篇

Zack / 3029人閱讀

摘要:上一篇文章已經(jīng)就進(jìn)行了部分說(shuō)明,介紹了其中涉及的常量和變量的含義,有些部分需要結(jié)合方法源碼來(lái)理解,今天這篇文章就繼續(xù)講解并發(fā)前言本文主要介紹中的一些重要方法,結(jié)合上篇文章中的講解部分進(jìn)行更進(jìn)一步的介紹回顧下上篇文章,我們應(yīng)該已經(jīng)知道的整體結(jié)

上一篇文章已經(jīng)就ConcurrentHashMap進(jìn)行了部分說(shuō)明,介紹了其中涉及的常量和變量的含義,有些部分需要結(jié)合方法源碼來(lái)理解,今天這篇文章就繼續(xù)講解并發(fā)ConcurrentHashMap

前言

本文主要介紹ConcurrentHashMap中的一些重要方法,結(jié)合上篇文章中的講解部分進(jìn)行更進(jìn)一步的介紹

回顧下上篇文章,我們應(yīng)該已經(jīng)知道ConcurrentHashMap的整體結(jié)構(gòu)和HashMap基本一致,不同的是處理多線程并發(fā)下保證操作的正確性,ConcurrentHashMap通過(guò)CAS和synchronized進(jìn)行并發(fā)控制,當(dāng)然,這種情況下各種處理都會(huì)變的更為復(fù)雜,下面我們就通過(guò)方法來(lái)深入理解ConcurrentHashMap的操作

重要方法

在一些方法中展示了各個(gè)變量以及常量的使用,能讓我們更好的理解其中的操作

tabAt/casTabAt/setTabAt

下列方法用于讀寫table數(shù)組,使用Unsafe提供的更新獲取volatile變量,CAS更新數(shù)組元素等操作

    // 讀取table[i]
    @SuppressWarnings("unchecked")
    static final  Node tabAt(Node[] tab, int i) {
        return (Node)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
    }
    // CAS更新table[i]
    static final  boolean casTabAt(Node[] tab, int i,
                                        Node c, Node v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
    }
    // 插入table[i]
    static final  void setTabAt(Node[] tab, int i, Node v) {
        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
    }
size

size方法返回了一個(gè)不精確的值,在多線程環(huán)境下,返回一個(gè)不精確的值,通過(guò)sumCount迭代counterCells統(tǒng)計(jì)sum值。

    public int size() {
        long n = sumCount();
        return ((n < 0L) ? 0 :
                (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                (int)n);
    }
    final long sumCount() {
        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;
    }

這里很多人可能會(huì)問(wèn),為什么需要疊加counterCells數(shù)組的值呢?

其實(shí)這和ConcurrentHashMap特點(diǎn)有關(guān),多線程環(huán)境下,同時(shí)插入值,執(zhí)行CAS操作,執(zhí)行成功的更新了baseCount,而執(zhí)行失敗的則將值放入到了counterCells數(shù)組中,可以查閱CounterCell內(nèi)部類源碼,只有一個(gè)long類型變量,每次進(jìn)行插入或者刪除時(shí)調(diào)用addCount通過(guò)CAS操作更新baseCount,失敗時(shí)執(zhí)行fullAddCount方法,初始化counterCells數(shù)組,并將1(相當(dāng)于插入或刪除一個(gè)元素)插入到CounterCell類中,這樣盡可能保證了Map長(zhǎng)度的正確性,這里理解流程即可,不深入,addCount部分有具體操作可查看

    @sun.misc.Contended static final class CounterCell {
        volatile long value;
        CounterCell(long x) { value = x; }
    }
get

參考HashMap,類似操作流程,需要注意的也就是在eh < 0處,如果是特殊節(jié)點(diǎn),比如TreeBin或者ForwardingNode節(jié)點(diǎn),則調(diào)用其具體類實(shí)現(xiàn)的find方法完成遍歷查詢,內(nèi)部類解釋可以參考我的上一篇文章

計(jì)算hash值

判斷table是否為空,不為空,找到對(duì)應(yīng)hash桶根節(jié)點(diǎn)判斷

非根節(jié)點(diǎn)繼續(xù)遍歷樹(shù)或者鏈表,存在對(duì)應(yīng)值則返回對(duì)應(yīng)值,否則返回null

    public V get(Object key) {
        Node[] tab; Node e, p; int n, eh; K ek;
        // 計(jì)算key的hash值
        int h = spread(key.hashCode());
        // table非空并且對(duì)應(yīng)的hash桶根節(jié)點(diǎn)不為空
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            // 查找節(jié)點(diǎn)為根節(jié)點(diǎn)
            if ((eh = e.hash) == h) {
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            // 樹(shù)節(jié)點(diǎn)或者擴(kuò)容中(FN節(jié)點(diǎn))
            else if (eh < 0)
                return (p = e.find(h, key)) != null ? p.val : null;
            // 鏈表遍歷查找
            while ((e = e.next) != null) {
                if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }
        }
        return null;
    }
    // 參考HashMap的hash方法,不同之處在于和HASH_BITS進(jìn)行了一次與操作,最高位變?yōu)榱?,即為正數(shù),因?yàn)榍耙黄恼乱惨呀?jīng)說(shuō)過(guò)負(fù)數(shù)hash值有特殊意義
    static final int spread(int h) {
        return (h ^ (h >>> 16)) & HASH_BITS;
    }
containsValue

這里通過(guò)靜態(tài)內(nèi)部類實(shí)現(xiàn)Traverser來(lái)遍歷數(shù)組,具體的內(nèi)部實(shí)現(xiàn)查看上篇文章里中的內(nèi)部類說(shuō)明,advance相當(dāng)于查找到下一個(gè)非空節(jié)點(diǎn)

    public boolean containsValue(Object value) {
        if (value == null)
            throw new NullPointerException();
        Node[] t;
        if ((t = table) != null) {
            Traverser it = new Traverser(t, t.length, 0, t.length);
            for (Node p; (p = it.advance()) != null; ) {
                V v;
                if ((v = p.val) == value || (v != null && value.equals(v)))
                    return true;
            }
        }
        return false;
    }

遍歷時(shí)遇見(jiàn)特殊節(jié)點(diǎn)的處理上一篇文章中已經(jīng)畫圖說(shuō)明,如下:

putVal

putVal整體同HashMap的putVal操作,操作流程上基本類似,只是在多線程操作下需要正確的處理插入值操作,同時(shí)如果發(fā)現(xiàn)有線程在進(jìn)行擴(kuò)容操作時(shí),需幫助擴(kuò)容,然后再進(jìn)行插入值的流程操作

    final V putVal(K key, V value, boolean onlyIfAbsent) {
        // 空值判斷
        if (key == null || value == null) throw new NullPointerException();
        // hash值計(jì)算,保證了hash值為正數(shù)
        int hash = spread(key.hashCode());
        // 當(dāng)前bin中元素的個(gè)數(shù),判斷是否樹(shù)化處理
        int binCount = 0;
        // 無(wú)限循環(huán)直到被正確處理
        for (Node[] tab = table;;) {
            Node f; int n, i, fh;
            // 空表進(jìn)行初始化操作
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            // 計(jì)算出的hash桶位置鏈表頭節(jié)點(diǎn)無(wú)值則通過(guò)CAS插入值
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            // 如果hash桶鏈表頭節(jié)點(diǎn)為MOVED狀態(tài),即說(shuō)明有線程在進(jìn)行擴(kuò)容操作,則通過(guò)helpTransfer幫助擴(kuò)容操作
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                // hash桶鏈表頭節(jié)點(diǎn)加鎖,在多線程環(huán)境下其他線程不能同時(shí)操作當(dāng)前相同的頭節(jié)點(diǎn)代碼塊
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        // 正常鏈表插入操作
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node e = f;; ++binCount) {
                                K ek;
                                // key和hash值相同則進(jìn)行替換
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node pred = e;
                                // 沒(méi)匹配到則直接插入到鏈表尾部
                                if ((e = e.next) == null) {
                                    pred.next = new Node(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        // 紅黑樹(shù)插入操作
                        else if (f instanceof TreeBin) {
                            Node p;
                            binCount = 2;
                            if ((p = ((TreeBin)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    // 達(dá)到樹(shù)化閾值,則可能進(jìn)行樹(shù)化操作
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        // size+1操作
        addCount(1L, binCount);
        return null;
    }
resizeStamp

前一篇文章在對(duì)sizeCtl說(shuō)明時(shí)在多個(gè)線程幫忙擴(kuò)容時(shí)其值小于0時(shí)做過(guò)一些說(shuō)明,在源碼中涉及到了下面這個(gè)方法,先理解清楚這個(gè)方法比較重要

這里的參數(shù)每次傳入的都是當(dāng)前數(shù)組的長(zhǎng)度,也就是說(shuō)每次這里生成的數(shù)都與當(dāng)時(shí)擴(kuò)容時(shí)的數(shù)組長(zhǎng)度有關(guān),Integer.numberOfLeadingZeros(n),返回二進(jìn)制表示,前面有多少個(gè)連續(xù)的0,RESIZE_STAMP_BITS固定為16,沒(méi)發(fā)現(xiàn)有提供方法來(lái)修改這個(gè)變量,位或運(yùn)算得到一個(gè)值,這個(gè)值表示了與擴(kuò)容時(shí)數(shù)組的長(zhǎng)度相關(guān),這里需記得是左移了(RESIZE_STAMP_BITS - 1),因?yàn)楹筮叴a中我們需要反向操作右移來(lái)重新獲取

這里通過(guò)這個(gè)方法與數(shù)組長(zhǎng)度關(guān)聯(lián),同時(shí)sizeCtl也會(huì)與之關(guān)聯(lián),同時(shí)也記錄當(dāng)前擴(kuò)容中的線程數(shù),故sizeCtl在擴(kuò)容中同時(shí)兼顧了兩種作用,一是判斷是否是在同一個(gè)批次的擴(kuò)容中(都是從16擴(kuò)容到32),同時(shí)判斷當(dāng)前擴(kuò)容中參與的線程數(shù)來(lái)確定是否結(jié)束和初始化操作

    /**
     * Returns the stamp bits for resizing a table of size n.
     * Must be negative when shifted left by RESIZE_STAMP_SHIFT.
     */
    static final int resizeStamp(int n) {
        return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
    }
addCount

整體來(lái)看主要進(jìn)行了兩部分內(nèi)容,一是更新baseCount,二是檢查是否進(jìn)行擴(kuò)容操作。其實(shí)這個(gè)方法里還是相當(dāng)復(fù)雜的,涉及到了線程私有的偽隨機(jī)數(shù)生成器ThreadLocalRandom,并發(fā)效率更高的LongAdder,不過(guò)初學(xué)者可以不用研究那么深入,這里不詳細(xì)說(shuō)明,大概了解就好

    private final void addCount(long x, int check) {
        CounterCell[] as; long b, s;
        // 通過(guò)CAS更新baseCount
        if ((as = counterCells) != null ||
            !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
            // 更新baseCount失敗
            CounterCell a; long v; int m;
            boolean uncontended = true;
            // 相當(dāng)于每個(gè)線程的probe就是它在CounterCell數(shù)組中的hash code,用來(lái)定位counterCells數(shù)組
            if (as == null || (m = as.length - 1) < 0 ||
                (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
                !(uncontended =
                  U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
                // 更新cellvalue失敗則執(zhí)行fullAddCount,具體不看了,比較復(fù)雜,不停嘗試更新計(jì)數(shù)
                // 源碼注釋上也寫了類似LongAdder
                fullAddCount(x, uncontended);
                return;
            }
            // 執(zhí)行到此說(shuō)明更新計(jì)數(shù)器成功,判斷是否退出,為什么是1其實(shí)還是有點(diǎn)困惑
            if (check <= 1)
                return;
            s = sumCount();
        }
        // check大于0代表著對(duì)應(yīng)hash桶下的節(jié)點(diǎn)數(shù),檢查是否擴(kuò)容
        // 滿足條件幫助擴(kuò)容,不滿足退出
        if (check >= 0) {
            Node[] tab, nt; int n, sc;
            // 注意,這里條件中3個(gè)變量賦值同時(shí)while判斷
            // sc = sizeCtl,tab = table,n = tab.length
            // 在并發(fā)操作中可能會(huì)出現(xiàn)變量錯(cuò)誤的情況造成擴(kuò)容處理出錯(cuò),通過(guò)resizeStamp保證擴(kuò)容時(shí)版本一致
            while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                   (n = tab.length) < MAXIMUM_CAPACITY) {
                // resizeStamp根據(jù)n返回一個(gè)擴(kuò)容版本戳,保證唯一性,上邊一個(gè)方法我已經(jīng)說(shuō)明了
                int rs = resizeStamp(n);
                // 說(shuō)明有別的線程在擴(kuò)容
                if (sc < 0) {
                    // 判斷是否幫助擴(kuò)容,滿足條件,不幫助擴(kuò)容,這里會(huì)分析下,看下面的分析部分
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;
                    // 幫助擴(kuò)容,線程數(shù)+1
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                        transfer(tab, nt);
                }
                // 無(wú)線程幫助擴(kuò)容,當(dāng)前線程嘗試成為第一個(gè)擴(kuò)容的線程
                else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2))
                    transfer(tab, null);
                s = sumCount();
            }
        }
    }

在上面這段代碼中,不幫助擴(kuò)容的條件中有些地方讓人困惑

    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
        transferIndex <= 0)
        break;
(sc >>> RESIZE_STAMP_SHIFT) != rs

首先需要明白上邊整個(gè)擴(kuò)容中的第一個(gè)線程會(huì)通過(guò)U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)設(shè)置sizeCtl,之后擴(kuò)容線程增加則通過(guò)U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)更新

sc右移RESIZE_STAMP_SHIFT(由于RESIZE_STAMP_BITS不提供修改方法,RESIZE_STAMP_SHIFT也只能取到16),第一個(gè)條件為什么是這個(gè)?需要結(jié)合擴(kuò)容代碼來(lái)看,首個(gè)線程搶到擴(kuò)容任務(wù)時(shí)需先創(chuàng)建nextTable,設(shè)置transferIndex,在執(zhí)行之前需要將sizeCtl更新,即U.compareAndSwapInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT) + 2),代碼存在于addCount和tryPresize方法中,sizeCtl在每次擴(kuò)容時(shí)會(huì)更新成(rs << RESIZE_STAMP_SHIFT) + 2。判斷條件里sc無(wú)符號(hào)右移,如果是相同的一次擴(kuò)容過(guò)程,則與rs相等是肯定的,rs是由resizeStamp根據(jù)長(zhǎng)度n計(jì)算得來(lái),其實(shí)最終這里比較的也就是table的長(zhǎng)度,防止多次擴(kuò)容下錯(cuò)誤的幫助了擴(kuò)容

另外在已經(jīng)有線程擴(kuò)容的情況下增加擴(kuò)容線程會(huì)會(huì)更新sizeCtl,U.compareAndSwapInt(this, SIZECTL, sc, sc + 1) 看出在首次更新的基礎(chǔ)上加1即可,擴(kuò)容線程完成自己的任務(wù)同理減1,結(jié)合上邊對(duì)resizeStamp的說(shuō)明應(yīng)該算很清楚了

以上部分也證實(shí)了上篇文章中sizeCtl注釋是不正確的

sc == rs + 1 || sc == rs + MAX_RESIZERS

這個(gè)條件是有問(wèn)題的,sc小于0,rs大于0,兩個(gè)條件一直為false,沒(méi)有true的可能,從這個(gè)條件上看,應(yīng)該是判斷擴(kuò)容完畢和擴(kuò)容線程數(shù)達(dá)到最大時(shí)不能幫助擴(kuò)容。

我們想一下,第一次線程擴(kuò)容時(shí)已經(jīng)將sc更新成(rs << RESIZE_STAMP_SHIFT) + 2,這里判斷的話需要改為sc == ( rs << RESIZE_STAMP_SHIFT ) +1 才對(duì),不能將sc右移,右移將會(huì)導(dǎo)致低16位記錄的線程數(shù)數(shù)據(jù)丟失,最大線程數(shù)判斷同理,應(yīng)改為sc == ( rs << RESIZE_STAMP_SHIFT ) + MAX_RESIZERS

我在Oracle官網(wǎng)bug庫(kù)里看到已經(jīng)提到了這個(gè)問(wèn)題:https://bugs.java.com/bugdata...

(nt = nextTable) == null

此時(shí)狀態(tài)可能表明擴(kuò)容已經(jīng)結(jié)束或者第一個(gè)線程在擴(kuò)容中,不能幫助擴(kuò)容

transferIndex <= 0

transfer任務(wù)已經(jīng)被分配完畢,不能分配任務(wù)給當(dāng)前線程,不能幫助擴(kuò)容,幫助擴(kuò)容部分下面會(huì)說(shuō)到

helpTransfer

如果正在進(jìn)行擴(kuò)容操作,則幫助擴(kuò)容

    /**
     * Helps transfer if a resize is in progress.
     */
    final Node[] helpTransfer(Node[] tab, Node f) {
        Node[] nextTab; int sc;
        // 判斷是否為ForwardingNode并且nextTable是否已經(jīng)被創(chuàng)建
        if (tab != null && (f instanceof ForwardingNode) &&
            (nextTab = ((ForwardingNode)f).nextTable) != null) {
            // 根據(jù)長(zhǎng)度獲取擴(kuò)容戳
            int rs = resizeStamp(tab.length);
            // 再次驗(yàn)證是否正在擴(kuò)容
            while (nextTab == nextTable && table == tab &&
                   (sc = sizeCtl) < 0) {
                // 幾個(gè)條件上邊已經(jīng)解釋過(guò)了,滿足不幫助擴(kuò)容
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || transferIndex <= 0)
                    break;
                // sizeCtl加1,表示當(dāng)前線程加入擴(kuò)容,多了一個(gè)線程幫忙
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                    transfer(tab, nextTab);
                    break;
                }
            }
            return nextTab;
        }
        return table;
    }
tryPresize

預(yù)先擴(kuò)容,putAll和treeifyBin中使用到,不滿足table容量時(shí),進(jìn)行一次擴(kuò)容操作

    /**
     * Tries to presize table to accommodate the given number of elements.
     *
     * @param size number of elements (doesn"t need to be perfectly accurate)
     */
    private final void tryPresize(int size) {
        // 判斷長(zhǎng)度是否超過(guò)最大值,超過(guò)則賦值為最大值,正常則通過(guò)tableSizeFor計(jì)算擴(kuò)容后的長(zhǎng)度
        int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
            tableSizeFor(size + (size >>> 1) + 1);
        int sc;
        // 未初始化或擴(kuò)容完成才能執(zhí)行本次擴(kuò)容操作
        while ((sc = sizeCtl) >= 0) {
            Node[] tab = table; int n;
            // table未初始化
            if (tab == null || (n = tab.length) == 0) {
                n = (sc > c) ? sc : c;
                // 置為-1表示數(shù)組初始化,前一篇文章已經(jīng)說(shuō)明
                if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                    try {
                        if (table == tab) {
                            @SuppressWarnings("unchecked")
                            Node[] nt = (Node[])new Node[n];
                            table = nt;
                            sc = n - (n >>> 2);
                        }
                    } finally {
                        // 此時(shí)相當(dāng)于閾值
                        sizeCtl = sc;
                    }
                }
            }
            // 已經(jīng)初始化,擴(kuò)容長(zhǎng)度小于閾值或者大于最大值,不進(jìn)行擴(kuò)容操作
            else if (c <= sc || n >= MAXIMUM_CAPACITY)
                break;
            // 再次驗(yàn)證table未改變
            else if (tab == table) {
                int rs = resizeStamp(n);
                // 同上邊代碼部分,判斷是否幫助擴(kuò)容
                if (sc < 0) {
                    Node[] nt;
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                        transfer(tab, nt);
                }
                else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2))
                    transfer(tab, null);
            }
        }
    }
transfer

table遷移操作,通過(guò)transferIndex來(lái)完成任務(wù)的分配,之前文章變量中也提及了MIN_TRANSFER_STRIDE(最小步長(zhǎng)),對(duì)每個(gè)擴(kuò)容線程申請(qǐng)遷移的hash桶數(shù)量做了限制,每次需要擴(kuò)容線程執(zhí)行完畢已經(jīng)領(lǐng)取完的hash桶遷移任務(wù)才可以繼續(xù)領(lǐng)取任務(wù)幫助遷移,最后一個(gè)遷移線程在遷移完畢后會(huì)進(jìn)行檢查

    private final void transfer(Node[] tab, Node[] nextTab) {
        int n = tab.length, stride;
        // 設(shè)置步長(zhǎng),即每個(gè)遷移任務(wù)遷移多少個(gè)hash桶,默認(rèn)最小遷移步長(zhǎng)16
        // 即每個(gè)擴(kuò)容線程最小遷移16個(gè)hash桶
        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
            stride = MIN_TRANSFER_STRIDE; // subdivide range
        // nextTab未初始化,則進(jìn)行初始化操作,這里不需要CAS,調(diào)用的地方已經(jīng)做了控制,保證只有一個(gè)線程能執(zhí)行
        if (nextTab == null) {            // initiating
            try {
                @SuppressWarnings("unchecked")
                // 新數(shù)組長(zhǎng)度擴(kuò)容為原有數(shù)組的2倍
                Node[] nt = (Node[])new Node[n << 1];
                nextTab = nt;
            } catch (Throwable ex) {      // try to cope with OOME
                // 內(nèi)存溢出時(shí)不能繼續(xù)擴(kuò)容
                sizeCtl = Integer.MAX_VALUE;
                return;
            }
            nextTable = nextTab;
            transferIndex = n;
        }
        int nextn = nextTab.length;
        // 設(shè)置ForwardingNode節(jié)點(diǎn)
        ForwardingNode fwd = new ForwardingNode(nextTab);
        // 線程可以繼續(xù)分配遷移任務(wù)的標(biāo)識(shí)
        boolean advance = true;
        // 設(shè)置結(jié)束標(biāo)識(shí)
        boolean finishing = false; // to ensure sweep before committing nextTab
        // i表示數(shù)組下標(biāo),bound表示遷移任務(wù)的最小下標(biāo)
        for (int i = 0, bound = 0;;) {
            Node f; int fh;
            // advance為false則表明當(dāng)前線程分配的遷移任務(wù)未完成或已經(jīng)擴(kuò)容完畢
            while (advance) {
                int nextIndex, nextBound;
                // --i 大于等于 bound 則表明本次分配的遷移任務(wù)還未完成,將advance置為false
                // 表明不能繼續(xù)分配遷移任務(wù)
                if (--i >= bound || finishing)
                    advance = false;
                // 設(shè)置nextIndex
                // 如果小于等于0則表示遷移hash桶已被分配完畢,不用繼續(xù),將advance置為false
                else if ((nextIndex = transferIndex) <= 0) {
                    i = -1;
                    advance = false;
                }
                // 設(shè)置遷移任務(wù)區(qū)間bound到i
                else if (U.compareAndSwapInt
                         (this, TRANSFERINDEX, nextIndex,
                          nextBound = (nextIndex > stride ?
                                       nextIndex - stride : 0))) {
                    bound = nextBound;
                    i = nextIndex - 1;
                    advance = false;
                }
            }
            // 上邊計(jì)算了區(qū)間和任務(wù)狀態(tài)
            // i < 0 上邊代碼已經(jīng)說(shuō)明,transfer任務(wù)已經(jīng)執(zhí)行完畢,退出
            // i >= n 這里n表示的是傳入的tab數(shù)組長(zhǎng)度,而i有可能因?yàn)閠ransferIndex改變而改變
            // 比如連續(xù)擴(kuò)容從16擴(kuò)容到32,然后又從32擴(kuò)容到64,此時(shí)這個(gè)條件是可能成立的,這里的i有可能在32到64之間,大于n的32
            // 不在一個(gè)擴(kuò)容維度內(nèi),需退出。最后一個(gè)條件沒(méi)看明白是什么情況出現(xiàn)這種狀態(tài)
            if (i < 0 || i >= n || i + n >= nextn) {
                int sc;
                if (finishing) {
                    // 擴(kuò)容遷移完畢設(shè)置table和sizeCtl
                    nextTable = null;
                    table = nextTab;
                    sizeCtl = (n << 1) - (n >>> 1);
                    return;
                }
                // 線程數(shù)減1,表明當(dāng)前線程退出
                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                    // 判斷當(dāng)前線程是否為最后一個(gè)擴(kuò)容線程,不是,則退出,條件可以看上邊的說(shuō)明,已經(jīng)講解過(guò)
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                        return;
                    // 確定當(dāng)前線程為最后一個(gè)擴(kuò)容線程,則需要進(jìn)行檢查工作
                    // 檢查所有的舊數(shù)組hash桶是否被正確的遷移
                    finishing = advance = true;
                    i = n; // recheck before commit
                }
            }
            // i處的hash桶為null則直接放置ForwardingNode節(jié)點(diǎn)
            else if ((f = tabAt(tab, i)) == null)
                advance = casTabAt(tab, i, null, fwd);
            // i處的hash桶為ForwardingNode節(jié)點(diǎn)
            else if ((fh = f.hash) == MOVED)
                // 最后的線程執(zhí)行檢查
                advance = true; // already processed
            else {
                synchronized (f) {
                    // 再次驗(yàn)證hash桶頭節(jié)點(diǎn)為f
                    if (tabAt(tab, i) == f) {
                        // 進(jìn)行遷移任務(wù),類似HashMap,分高位和低位,不明白的可以看我HashMap的文章
                        Node ln, hn;
                        if (fh >= 0) {
                            // 正常鏈表操作
                            // runBit表明首節(jié)點(diǎn)的位置,0則表示在低位,非0表示在高位
                            int runBit = fh & n;
                            Node lastRun = f;
                            // 找到尾部最后一個(gè)高低位不同的節(jié)點(diǎn),之后的節(jié)點(diǎn)不需要進(jìn)行操作,直接進(jìn)行復(fù)用
                            for (Node p = f.next; p != null; p = p.next) {
                                int b = p.hash & n;
                                if (b != runBit) {
                                    runBit = b;
                                    lastRun = p;
                                }
                            }
                            // 低位lastRun在下面循環(huán)時(shí)使用
                            if (runBit == 0) {
                                ln = lastRun;
                                hn = null;
                            }
                            // 高位lastRun在下面循環(huán)時(shí)使用
                            else {
                                hn = lastRun;
                                ln = null;
                            }
                            // 確定lastRun為了提高效率,復(fù)用原有鏈表
                            for (Node p = f; p != lastRun; p = p.next) {
                                int ph = p.hash; K pk = p.key; V pv = p.val;
                                // 低位鏈表
                                if ((ph & n) == 0)
                                    ln = new Node(ph, pk, pv, ln);
                                // 高位鏈表
                                else
                                    hn = new Node(ph, pk, pv, hn);
                            }
                            // 新數(shù)組上設(shè)置低位鏈表
                            setTabAt(nextTab, i, ln);
                            // 新數(shù)組上設(shè)置高位鏈表
                            setTabAt(nextTab, i + n, hn);
                            // 舊數(shù)組i處設(shè)置為ForwardingNode節(jié)點(diǎn)
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                        // 紅黑樹(shù)通過(guò)TreeBin操作
                        else if (f instanceof TreeBin) {
                            TreeBin t = (TreeBin)f;
                            // 同樣劃分為高低位進(jìn)行處理,通過(guò)鏈表來(lái)操作
                            TreeNode lo = null, loTail = null;
                            TreeNode hi = null, hiTail = null;
                            int lc = 0, hc = 0;
                            for (Node e = t.first; e != null; e = e.next) {
                                int h = e.hash;
                                TreeNode p = new TreeNode
                                    (h, e.key, e.val, null, null);
                                // 判斷是低位還是高位然后修改鏈表關(guān)系
                                if ((h & n) == 0) {
                                    if ((p.prev = loTail) == null)
                                        lo = p;
                                    else
                                        loTail.next = p;
                                    loTail = p;
                                    ++lc;
                                }
                                else {
                                    if ((p.prev = hiTail) == null)
                                        hi = p;
                                    else
                                        hiTail.next = p;
                                    hiTail = p;
                                    ++hc;
                                }
                            }
                            // 同鏈表類似,判斷下是否需轉(zhuǎn)成鏈表,通過(guò)TreeBin將高低位鏈表構(gòu)建成紅黑樹(shù)
                            ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                                (hc != 0) ? new TreeBin(lo) : t;
                            hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                                (lc != 0) ? new TreeBin(hi) : t;
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                    }
                }
            }
        }
    }

遷移任務(wù)是從數(shù)組尾部向頭部進(jìn)行,這樣做的目的應(yīng)該是與迭代正向操作相反來(lái)減少?zèng)_突,當(dāng)?shù)鷷r(shí)是已經(jīng)遷移好的hash桶,遷移時(shí)是已經(jīng)迭代完畢的hash桶

clear

清空操作,比較簡(jiǎn)單

    public void clear() {
        // 刪除節(jié)點(diǎn)數(shù)記錄最后需要更新
        long delta = 0L; // negative number of deletions
        // 數(shù)組下標(biāo)
        int i = 0;
        Node[] tab = table;
        while (tab != null && i < tab.length) {
            int fh;
            Node f = tabAt(tab, i);
            // hash桶首節(jié)點(diǎn)為null表明不需要執(zhí)行
            if (f == null)
                ++i;
            // 擴(kuò)容中幫助擴(kuò)容然后重新開(kāi)始循環(huán)清空操作
            else if ((fh = f.hash) == MOVED) {
                tab = helpTransfer(tab, f);
                i = 0; // restart
            }
            // 正常鏈表或TreeBin節(jié)點(diǎn)
            else {
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        Node p = (fh >= 0 ? f :
                                       (f instanceof TreeBin) ?
                                       ((TreeBin)f).first : null);
                        // 獲取hash桶的節(jié)點(diǎn)數(shù)
                        while (p != null) {
                            --delta;
                            p = p.next;
                        }
                        // 將hash桶置null
                        setTabAt(tab, i++, null);
                    }
                }
            }
        }
        // 更新數(shù)組長(zhǎng)度
        if (delta != 0L)
            addCount(delta, -1);
    }
總結(jié)

本文緊接上一篇文章講解了ConcurrentHashMap的重要的方法,對(duì)于一些變量和常量結(jié)合方法進(jìn)行了更多的解釋說(shuō)明,本身而言還是比較復(fù)雜,其中部分筆者也不能完全理解,不過(guò)整體的流程有了一個(gè)更清晰的認(rèn)知,重點(diǎn)需要理解的在下面幾點(diǎn):

涉及到Map長(zhǎng)度的計(jì)算:通過(guò)counterCells完成以及通過(guò)addCount進(jìn)行長(zhǎng)度的更新

擴(kuò)容操作:sizeCtl的設(shè)置以及更新和各種情況下對(duì)應(yīng)的含義

遷移操作:遷移步長(zhǎng),線程檢查

節(jié)點(diǎn)類型:幾種節(jié)點(diǎn)類型的不同處理方式

當(dāng)然,有些條件可能比較復(fù)雜,難以理解,只能盡力多看多想,希望對(duì)各位有所幫助

以上內(nèi)容如有問(wèn)題歡迎指出,筆者驗(yàn)證后將及時(shí)修正,謝謝

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://systransis.cn/yun/75191.html

相關(guān)文章

  • JDK源碼那些事兒并發(fā)ConcurrentHashMap上篇

    前面已經(jīng)說(shuō)明了HashMap以及紅黑樹(shù)的一些基本知識(shí),對(duì)JDK8的HashMap也有了一定的了解,本篇就開(kāi)始看看并發(fā)包下的ConcurrentHashMap,說(shuō)實(shí)話,還是比較復(fù)雜的,筆者在這里也不會(huì)過(guò)多深入,源碼層次上了解一些主要流程即可,清楚多線程環(huán)境下整個(gè)Map的運(yùn)作過(guò)程就算是很大進(jìn)步了,更細(xì)的底層部分需要時(shí)間和精力來(lái)研究,暫不深入 前言 jdk版本:1.8 JDK7中,ConcurrentH...

    Leck1e 評(píng)論0 收藏0
  • JDK源碼那些事兒紅黑樹(shù)基礎(chǔ)下篇

    摘要:強(qiáng)調(diào)一下,紅黑樹(shù)中的葉子節(jié)點(diǎn)指的都是節(jié)點(diǎn)。故刪除之后紅黑樹(shù)平衡不用調(diào)整。將達(dá)到紅黑樹(shù)平衡。到此關(guān)于紅黑樹(shù)的基礎(chǔ)已經(jīng)介紹完畢,下一章我將就源碼中的進(jìn)行講解說(shuō)明,看一看紅黑樹(shù)是如何在源碼中實(shí)現(xiàn)的。 說(shuō)到HashMap,就一定要說(shuō)到紅黑樹(shù),紅黑樹(shù)作為一種自平衡二叉查找樹(shù),是一種用途較廣的數(shù)據(jù)結(jié)構(gòu),在jdk1.8中使用紅黑樹(shù)提升HashMap的性能,今天就來(lái)說(shuō)一說(shuō)紅黑樹(shù),上一講已經(jīng)給出插入平衡...

    羅志環(huán) 評(píng)論0 收藏0
  • JDK源碼那些事兒常用的ArrayList

    摘要:前面已經(jīng)講解集合中的并且也對(duì)其中使用的紅黑樹(shù)結(jié)構(gòu)做了對(duì)應(yīng)的說(shuō)明,這次就來(lái)看下簡(jiǎn)單一些的另一個(gè)集合類,也是日常經(jīng)常使用到的,整體來(lái)說(shuō),算是比較好理解的集合了,一起來(lái)看下前言版本類定義繼承了,實(shí)現(xiàn)了,提供對(duì)數(shù)組隊(duì)列的增刪改查操作實(shí)現(xiàn)接口,提供隨 前面已經(jīng)講解集合中的HashMap并且也對(duì)其中使用的紅黑樹(shù)結(jié)構(gòu)做了對(duì)應(yīng)的說(shuō)明,這次就來(lái)看下簡(jiǎn)單一些的另一個(gè)集合類,也是日常經(jīng)常使用到的ArrayL...

    hizengzeng 評(píng)論0 收藏0
  • ConcurrentHashMap 源碼閱讀小結(jié)

    摘要:如果沖突了,同步頭節(jié)點(diǎn),進(jìn)行鏈表操作,如果鏈表長(zhǎng)度達(dá)到,分成紅黑樹(shù)。每次加入一個(gè)線程都會(huì)將的低位加一。擴(kuò)容最大的幫助線程是,這是低位的最大值限制的。線程處理完之后,如果沒(méi)有可選區(qū)間,且任務(wù)沒(méi)有完成,就會(huì)將整個(gè)表檢查一遍,防止遺漏。 前言 每一次總結(jié)都意味著重新開(kāi)始,同時(shí)也是為了更好的開(kāi)始。ConcurrentHashMap 一直是我心中的痛。雖然不敢說(shuō)完全讀懂了,但也看了幾個(gè)重要的方法...

    The question 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<