欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java?ConcurrentHashMap的源碼分析詳解

 更新時(shí)間:2023年03月02日 08:40:37   作者:code_writer  
ConcurrentHashMap(CHM)是日常開(kāi)發(fā)中使用頻率非常高的一種數(shù)據(jù)結(jié)構(gòu),想對(duì)于普通的HashMap,CHM提供了線程安全的讀寫(xiě),CHM里面使用了許多比較精妙的優(yōu)化&操作。本文主要對(duì)CHM的整體結(jié)構(gòu)、初始化,查找,插入等做分析

概述

ConcurrentHashMap(CHM)是日常開(kāi)發(fā)中使用頻率非常高的一種數(shù)據(jù)結(jié)構(gòu),想對(duì)于普通的HashMap,CHM提供了線程安全的讀寫(xiě),CHM里面使用了許多比較精妙的優(yōu)化&操作。本文主要對(duì)CHM的整體結(jié)構(gòu)、初始化,查找,插入等做分析。

CHM在1.8之前和之后有比較大的變動(dòng),1.8之前主要通過(guò)Segment 分段鎖 來(lái)解決并發(fā)問(wèn)題,1.8及之后就沒(méi)有這些臃腫的數(shù)據(jù)結(jié)構(gòu)了,其數(shù)據(jù)結(jié)構(gòu)與普通的HashMap一樣,都是Node數(shù)組+鏈表+紅黑樹(shù)

一顆紅黑樹(shù)應(yīng)滿足如下性質(zhì):

1.根節(jié)點(diǎn)是黑色的

  • 外部節(jié)點(diǎn)均為黑色(圖中的 leaf 節(jié)點(diǎn),通常在表述的時(shí)候會(huì)省略)
  • 紅色節(jié)點(diǎn)的孩子節(jié)點(diǎn)必為黑色(通常插入的節(jié)點(diǎn)為紅色)
  • 從任一外部節(jié)點(diǎn)到根節(jié)點(diǎn)的沿途,黑節(jié)點(diǎn)的數(shù)目相等

除了上面基本的數(shù)據(jù)結(jié)構(gòu)之外,Node節(jié)點(diǎn)也是一個(gè)需要關(guān)心的數(shù)據(jù)結(jié)構(gòu),Node節(jié)點(diǎn)本質(zhì)上是單向鏈表的節(jié)點(diǎn),其中包含keyvalue、Hashnext屬性

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;  
    final K key;
    volatile V val;
    volatile Node<K,V> next;
}

ForwardingNode節(jié)點(diǎn)

ForwardingNode節(jié)點(diǎn)(簡(jiǎn)稱(chēng)fwd節(jié)點(diǎn))繼承自Node節(jié)點(diǎn),主要用于擴(kuò)容,該節(jié)點(diǎn)里面固定Hash值為MOVED(值為-1),同時(shí)持有新表的引用

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;
    }

    Node<K,V> find(int h, Object k) {
        ...
    }
}

TreeNode

TreeNode節(jié)點(diǎn)也繼承自Node節(jié)點(diǎn),用于表示紅黑樹(shù)上的節(jié)點(diǎn),主要屬性如下所示

static final class TreeNode<K,V> extends Node<K,V> {
    TreeNode<K,V> parent;  // 父節(jié)點(diǎn)
    TreeNode<K,V> left;    // 左兒子
    TreeNode<K,V> right;   // 右兒子
    TreeNode<K,V> prev;    // 記錄前驅(qū)節(jié)點(diǎn),用于恢復(fù)鏈表
    boolean red;
}

TreeBin

TreeBin節(jié)點(diǎn)內(nèi)部持有TreeNode節(jié)點(diǎn)的引用,內(nèi)部實(shí)現(xiàn)了讀寫(xiě)鎖用于控制多線程并發(fā)在紅黑樹(shù)上的操作,主要屬性如下所示

static final class TreeBin<K,V> extends Node<K,V> {
    TreeNode<K,V> root;  // 紅黑樹(shù)根節(jié)點(diǎn)
    volatile TreeNode<K,V> first;  // 鏈表根節(jié)點(diǎn),讀寫(xiě)分離時(shí)會(huì)用到
    volatile Thread waiter;  // 當(dāng)前線程
    volatile int lockState;  // 當(dāng)前紅黑樹(shù)的鎖狀態(tài)
    // values for lockState
    static final int WRITER = 1; // set while holding write lock
    static final int WAITER = 2; // set when waiting for write lock
    static final int READER = 4; // 讀鎖標(biāo)記
}

SizeCtl

除了數(shù)據(jù)結(jié)構(gòu)需要說(shuō)明外,SizeCtl也是理解CHM十分重要的一個(gè)字段,他是一個(gè)整數(shù),不同的值表示不同的狀態(tài)

  • 當(dāng)SizeCtl > 0時(shí),表示下次擴(kuò)展的閾值,其中閾值計(jì)算方式:數(shù)組長(zhǎng)度 * 擴(kuò)展閾值(注意這里是固定的0.75)
  • 當(dāng)SizeCtl = 0時(shí),表示還沒(méi)有開(kāi)始初始化
  • 當(dāng)sizeCtl = -1是,表示此時(shí)正在進(jìn)行初始化
  • 當(dāng)SizeCtl < -1時(shí),表示此時(shí)正在進(jìn)行擴(kuò)展,其中高16位表示擴(kuò)容標(biāo)識(shí)戳,低16位表示參與擴(kuò)容的線程數(shù)+1

初始化

CHM的初始化是惰性初始化的,即當(dāng)我們使用ConCurrentHashMap<String,string> map = new ConcurrentHashMap(20);創(chuàng)建一個(gè)CHM對(duì)象時(shí),并不會(huì)真正的創(chuàng)建對(duì)象,而是只有在put時(shí)才會(huì)真正開(kāi)始創(chuàng)建對(duì)象。

public ConcurrentHashMap(int initialCapacity) {
    // 只是檢查參數(shù)是否合理,并設(shè)置好數(shù)組容量和擴(kuò)容閾值
    if (initialCapacity < 0)
    throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
           MAXIMUM_CAPACITY :
           tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}

初始化流程

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    // 判空,注意這里是while,當(dāng)線程蘇醒后會(huì)記性檢查直到初始化完畢
    while ((tab = table) == null || tab.length == 0) {
        // 如果其他線程正在初始化,則讓出cpu
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // lost initialization race; just spin
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { // 當(dāng)前線程嘗試獲取創(chuàng)建數(shù)組的重任
            try {
                // 這里需要再進(jìn)行判斷是否為空,防止當(dāng)前線程創(chuàng)建完畢后又有其他線程進(jìn)來(lái)重復(fù)創(chuàng)建
                if ((tab = table) == null || tab.length == 0) {
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    // 設(shè)置閾值為0.75n
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

查找

get方法進(jìn)行查找,針對(duì)不同情況有不同處理

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
// 擾動(dòng)運(yùn)算
int h = spread(key.hashCode());
// 判斷表是否為空,表長(zhǎng)度是否為0,以及元素對(duì)應(yīng)下標(biāo)是否為空
if ((tab = table) != null && (n = tab.length) > 0 &&
    (e = tabAt(tab, (n - 1) & h)) != null) {
    // 判斷當(dāng)前下邊下是否是我們要找到值
    if ((eh = e.hash) == h) {
        if ((ek = e.key) == key || (ek != null && key.equals(ek)))
            return e.val;
    }
    else if (eh < 0) // 判斷Node節(jié)點(diǎn)的Hash值是否小于0,如果小于0的話,則會(huì)在他的子類(lèi)上進(jìn)行查找
        //這里情況比較復(fù)雜,不同的節(jié)點(diǎn)有不同的處理,如果當(dāng)前節(jié)點(diǎn)為fwd節(jié)點(diǎn),則去新表上找,如果為紅黑樹(shù)
        //節(jié)點(diǎn),則在紅黑樹(shù)上進(jìn)行查找,后文會(huì)展開(kāi)紅黑樹(shù)上的查找流程
        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;
}

插入

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) { // 注意這里是個(gè)死循環(huán)
        Node<K,V> f; int n, i, fh;
        // 判斷是否初始化
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 判斷對(duì)應(yīng)節(jié)點(diǎn)是否是空節(jié)點(diǎn),如果是
            //直接通過(guò)cas創(chuàng)建節(jié)點(diǎn)
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED) // 如果當(dāng)前節(jié)點(diǎn)是fwd節(jié)點(diǎn)(正在擴(kuò)容),則幫助擴(kuò)容
            tab = helpTransfer(tab, f);
        else { 
            V oldVal = null;
            synchronized (f) { // 這里加鎖
                if (tabAt(tab, i) == f) { // 這里需要繼續(xù)判斷是否當(dāng)前位置的節(jié)點(diǎn)沒(méi)有變化,因?yàn)槠渌€程可能
                    // 改變此節(jié)點(diǎn)
                    if (fh >= 0) { // fh >= 0表示當(dāng)前節(jié)點(diǎn)是鏈表節(jié)點(diǎn),直接next往下找就行
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) { // 如果此時(shí)節(jié)點(diǎn)是TreeBin節(jié)點(diǎn),則需要再紅黑樹(shù)上進(jìn)行插入,具體
                        // 插入流程后文展開(kāi)
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                              value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            // 判斷是否需要樹(shù)化
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    // 計(jì)數(shù)器加1,這里使用了計(jì)數(shù)器而不是AtomicLong這種
    addCount(1L, binCount);
    return null;
}

擴(kuò)容

CHM的擴(kuò)容利用了多線程并發(fā)的去擴(kuò)容

CHM在兩種條件下會(huì)發(fā)生擴(kuò)容:

  • 單個(gè)鏈表長(zhǎng)度大于8,并且數(shù)組長(zhǎng)度小于64時(shí),會(huì)發(fā)生擴(kuò)容
  • 元素個(gè)數(shù)超過(guò)閾值會(huì)發(fā)生擴(kuò)容

擴(kuò)容流程:

  • 創(chuàng)建新的Node表,長(zhǎng)度為當(dāng)前數(shù)組長(zhǎng)度的兩倍
  • 從后往前分配任務(wù)區(qū)間,最小長(zhǎng)度是16,即每個(gè)線程每次擴(kuò)容最少需要遷移16個(gè)桶,具體遷移數(shù)量由cpu核數(shù)決定
  • 判斷當(dāng)前元素是否為空,為空直接cas操作當(dāng)前節(jié)點(diǎn)為fwd節(jié)點(diǎn),否則判斷當(dāng)前元素是否為fwd節(jié)點(diǎn),如果是,則說(shuō)明其他線程再次區(qū)間擴(kuò)容,此時(shí)需要重新選定區(qū)間,否則就對(duì)當(dāng)前桶開(kāi)始進(jìn)行遷移
  • 其他元素在put時(shí)如果發(fā)現(xiàn)當(dāng)前桶位是fwd節(jié)點(diǎn),會(huì)先協(xié)助擴(kuò)容再put
  • 最后一個(gè)擴(kuò)容線程退出擴(kuò)容時(shí)再次檢查一遍舊桶,更新sizeCtl的值,同時(shí)引用新桶
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    // 確定任務(wù)長(zhǎng)度
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; // subdivide range
    if (nextTab == null) {            // 第一個(gè)擴(kuò)容的線程需要?jiǎng)?chuàng)建新數(shù)組
        try {
            @SuppressWarnings("unchecked")
                Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
            nextTab = nt;
        } catch (Throwable ex) {      // try to cope with OOME
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        nextTable = nextTab;
        transferIndex = n;
    }
    int nextn = nextTab.length;
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    boolean advance = true;
    boolean finishing = false; // 用于最后一次檢查
    for (int i = 0, bound = 0;;) {
        Node<K,V> f; int fh;
        while (advance) {
            int nextIndex, nextBound;
            if (--i >= bound || finishing) //當(dāng)前任務(wù)是否完成
                advance = false;
            else if ((nextIndex = transferIndex) <= 0) { // 沒(méi)有任務(wù)了
                i = -1;
                advance = false;
            }
            else if (U.compareAndSwapInt
                     (this, TRANSFERINDEX, nextIndex,
                      nextBound = (nextIndex > stride ?
                                   nextIndex - stride : 0))) { //cas更新transferIndex
                bound = nextBound;
                i = nextIndex - 1;
                advance = false;
            }
        }
        if (i < 0 || i >= n || i + n >= nextn) { // 擴(kuò)容完畢
            int sc;
            if (finishing) { // 二次檢查后引用新表
                nextTable = null;
                table = nextTab;
                sizeCtl = (n << 1) - (n >>> 1);
                return;
            }
            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                    return;
                finishing = advance = true; 
                i = n; // recheck before commit
            }
        }
        else if ((f = tabAt(tab, i)) == null) // 當(dāng)前節(jié)點(diǎn)為空,直接賦為fwd
            advance = casTabAt(tab, i, null, fwd);
        else if ((fh = f.hash) == MOVED) // 其他線程已經(jīng)遷移好了,此時(shí)需要重新分配區(qū)間
            advance = true; // already processed
        else {
            synchronized (f) { //當(dāng)前節(jié)點(diǎn)開(kāi)始遷移,這里需要加鎖,可能會(huì)有讀寫(xiě)操作
                if (tabAt(tab, i) == f) {
                    Node<K,V> ln, hn;
                    if (fh >= 0) { //鏈表節(jié)點(diǎn) 這里只需要判斷對(duì)應(yīng)位置是0還是1就可決定遷移到高桶位還是低桶位
                        int runBit = fh & n;
                        Node<K,V> lastRun = f;
                        for (Node<K,V> p = f.next; p != null; p = p.next) {
                            int b = p.hash & n;
                            if (b != runBit) {
                                runBit = b;
                                lastRun = p;
                            }
                        }
                        if (runBit == 0) {
                            ln = lastRun;
                            hn = null;
                        }
                        else {
                            hn = lastRun;
                            ln = null;
                        }
                        for (Node<K,V> 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<K,V>(ph, pk, pv, ln);
                            else
                                hn = new Node<K,V>(ph, pk, pv, hn);
                        }
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                    else if (f instanceof TreeBin) { // 紅黑樹(shù)節(jié)點(diǎn),通過(guò)判斷對(duì)應(yīng)位是否為0決定放到高
                        // 桶位還是低桶位
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        TreeNode<K,V> lo = null, loTail = null;
                        TreeNode<K,V> hi = null, hiTail = null;
                        int lc = 0, hc = 0;
                        for (Node<K,V> e = t.first; e != null; e = e.next) {
                            int h = e.hash;
                            TreeNode<K,V> p = new TreeNode<K,V>
                                (h, e.key, e.val, null, null);
                            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;
                            }
                        }
                        ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                            (hc != 0) ? new TreeBin<K,V>(lo) : t;
                        hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                            (lc != 0) ? new TreeBin<K,V>(hi) : t;
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                }
            }
        }
    }
}

紅黑樹(shù)的讀&寫(xiě)

紅黑樹(shù)上的讀寫(xiě)操作是基于TreeBin進(jìn)行的,上文也對(duì)其進(jìn)行了說(shuō)明。TreeBin其中的lockState表示當(dāng)前的讀寫(xiě)狀態(tài)

讀操作

讀操作和寫(xiě)操作可可以是并行的,當(dāng)有現(xiàn)成正在寫(xiě)或者正在等待寫(xiě)時(shí),讀線程可以讀,通過(guò)代碼我們可以發(fā)現(xiàn),此時(shí)并沒(méi)有從紅黑樹(shù)上去讀,而是通過(guò)鏈表去讀了,這里和IO多路復(fù)用里面的epoll函數(shù)的底層原理一樣。

final Node<K,V> find(int h, Object k) {
    if (k != null) {
        for (Node<K,V> e = first; e != null; ) {
            int s; K ek;
            // WAITER : .....010
            // WRITER : .....001
            // READER : .....100
            if (((s = lockState) & (WAITER|WRITER)) != 0) { //這里表明此時(shí)有正在寫(xiě)或者等待寫(xiě)的線程,直接從鏈表讀
                if (e.hash == h &&
                    ((ek = e.key) == k || (ek != null && k.equals(ek))))
                    return e;
                e = e.next;
            }
            else if (U.compareAndSwapInt(this, LOCKSTATE, s, // 表明此時(shí)處于無(wú)鎖或者讀鎖狀態(tài),直接紅黑樹(shù)上查找
                                         s + READER)) {
                TreeNode<K,V> r, p;
                try {
                    p = ((r = root) == null ? null :
                         r.findTreeNode(h, k, null));
                } finally {
                    Thread w;
                    // 讀操作完畢后檢查是否有寫(xiě)線程在等待,如果有,需要喚醒等待線程
                    // READER|WAITER 表示此時(shí)是最后一個(gè)讀線程
                    if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
                        (READER|WAITER) && (w = waiter) != null)
                        LockSupport.unpark(w);
                }
                return p;
            }
        }
    }
    return null;
}

寫(xiě)操作

紅黑樹(shù)上的寫(xiě)會(huì)先查找是否有對(duì)應(yīng)的值,如果有,則更新值即可,如果沒(méi)有找到,則插入新的節(jié)點(diǎn),再插入節(jié)點(diǎn)的過(guò)程中,會(huì)調(diào)用lockRoot加寫(xiě)鎖,如果沒(méi)有搶到鎖,則會(huì)調(diào)用contentLock方法繼續(xù)嘗試或者將自己掛起

final TreeNode<K,V> putTreeVal(int h, K k, V v) {
    Class<?> kc = null;
    boolean searched = false;
    for (TreeNode<K,V> p = root;;) {
        // 查找是否有值
        int dir, ph; K pk;
        if (p == null) {
            first = root = new TreeNode<K,V>(h, k, v, null, null);
            break;
        }
        else if ((ph = p.hash) > h)
            dir = -1;
        else if (ph < h)
            dir = 1;
        else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
            return p;
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            if (!searched) {
                TreeNode<K,V> q, ch;
                searched = true;
                if (((ch = p.left) != null &&
                     (q = ch.findTreeNode(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.findTreeNode(h, k, kc)) != null))
                    return q;
            }
            dir = tieBreakOrder(k, pk);
        }

        TreeNode<K,V> xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            TreeNode<K,V> x, f = first;
            first = x = new TreeNode<K,V>(h, k, v, f, xp);
            if (f != null)
                f.prev = x;
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            if (!xp.red)
                x.red = true;
            else {
                // 鎖住節(jié)點(diǎn),平衡操作可能會(huì)導(dǎo)致樹(shù)結(jié)構(gòu)發(fā)生變化
                lockRoot();
                try { 
                    root = balanceInsertion(root, x);
                } finally {
                    unlockRoot();
                }
            }
            break;
        }
    }
    assert checkInvariants(root);
    return null;
}
private final void lockRoot() {
    // 這里嘗試去獲取寫(xiě)鎖,獲取不到就調(diào)用contenedLock方法
    if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
        contendedLock(); // offload to separate method
}

private final void contendedLock() {
    boolean waiting = false;
    for (int s;;) {
        // ~WAITER 1111111101
        // 如果此時(shí)處于無(wú)鎖,則重新獲取鎖
        if (((s = lockState) & ~WAITER) == 0) {
            if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
                if (waiting)
                    waiter = null;
                return;
            }
        } // 此時(shí)不是處于waiter狀態(tài),即其他線程沒(méi)有等待,則自己進(jìn)行等待。如果已經(jīng)有線程在等待了,會(huì)一直自旋,也可看出這里是非公平鎖
        else if ((s & WAITER) == 0) {
            if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
                waiting = true;
                waiter = Thread.currentThread();
            }
        }
        else if (waiting) // 將當(dāng)前線程掛起
            LockSupport.park(this);
    }
}

小結(jié)

在紅黑樹(shù)上進(jìn)行讀寫(xiě)時(shí),我們可以發(fā)現(xiàn),當(dāng)有線程在樹(shù)上寫(xiě)時(shí),讀線程是可以讀的,不過(guò)不是從紅黑樹(shù)上去讀,而不用阻塞,這里可能導(dǎo)致短暫的數(shù)據(jù)不一致的問(wèn)題,類(lèi)似于COW;當(dāng)有線程在樹(shù)上讀時(shí),此時(shí)寫(xiě)線程會(huì)將自己掛起,當(dāng)最后一個(gè)讀線程查找完畢后會(huì)檢查是否有些線程在等待,如果有,則喚醒等待寫(xiě)的線程

容器計(jì)數(shù)

對(duì)于一個(gè)并發(fā)容器來(lái)說(shuō),當(dāng)多線程同時(shí)寫(xiě)入時(shí),此時(shí)容器如何計(jì)數(shù)成為了一個(gè)問(wèn)題,最簡(jiǎn)單的是通過(guò)AtomicLong來(lái)保證原子性與可見(jiàn)性,但是在多線程情況下絕大多數(shù)線程會(huì)cas失敗,然后重試。這無(wú)疑是浪費(fèi)cpu性能的且會(huì)有性能瓶頸的。在CHM中引入了,使用分段計(jì)數(shù)思想,即通過(guò)一個(gè)數(shù)組來(lái)計(jì)數(shù),當(dāng)多線程并發(fā)計(jì)數(shù)時(shí),記在數(shù)組的不同位置上,最后進(jìn)行統(tǒng)計(jì)。

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) {
        // 累計(jì)cells數(shù)組
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                sum += a.value;
        }
    }
    return sum;
}

// 計(jì)數(shù)
private final void addCount(long x, int check) {
    CounterCell[] as; long b, s;
    // 如果cells數(shù)組不為空或者cas操作baseCount失敗,說(shuō)明此時(shí)出現(xiàn)了競(jìng)爭(zhēng),需要再cells數(shù)組上計(jì)數(shù)
    if ((as = counterCells) != null ||
        !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        CounterCell a; long v; int m;
        boolean uncontended = true;
        if (as == null || (m = as.length - 1) < 0 ||
            (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
            !(uncontended =
              U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
            fullAddCount(x, uncontended);
            return;
        }
        if (check <= 1)
            return;
        s = sumCount();
    }
    // 判斷是否需要擴(kuò)容
    if (check >= 0) {
        Node<K,V>[] tab, nt; int n, sc;
        while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
               (n = tab.length) < MAXIMUM_CAPACITY) {
            int rs = resizeStamp(n);
            if (sc < 0) {
                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);
            s = sumCount();
        }
    }
}

總結(jié)

CHM作為線程安全的Map,同時(shí)又要兼顧性能,使用了許多巧妙的設(shè)計(jì)與思想,如位運(yùn)算,紅黑樹(shù),無(wú)鎖并發(fā)等等,里面的思想值得我們?nèi)W(xué)習(xí)和借鑒。本篇文章對(duì)其進(jìn)行簡(jiǎn)單的解讀,如有不當(dāng)之處,還望指出,萬(wàn)分感謝。

到此這篇關(guān)于Java ConcurrentHashMap的源碼分析詳解的文章就介紹到這了,更多相關(guān)Java ConcurrentHashMap內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • mybaties?plus?selectMaps和selectList的區(qū)別說(shuō)明

    mybaties?plus?selectMaps和selectList的區(qū)別說(shuō)明

    這篇文章主要介紹了mybaties?plus?selectMaps和selectList的區(qū)別說(shuō)明,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2021-12-12
  • CorsFilter 過(guò)濾器解決跨域的處理

    CorsFilter 過(guò)濾器解決跨域的處理

    這篇文章主要介紹了CorsFilter 過(guò)濾器解決跨域的處理操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2021-06-06
  • java開(kāi)源區(qū)塊鏈jdchain入門(mén)

    java開(kāi)源區(qū)塊鏈jdchain入門(mén)

    這篇文章主要介紹了java開(kāi)源區(qū)塊鏈jdchain入門(mén),文中為大家講解了關(guān)于部署及組件遇到的一些問(wèn)題,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步
    2022-02-02
  • Java語(yǔ)言實(shí)現(xiàn)Blowfish加密算法完整代碼分享

    Java語(yǔ)言實(shí)現(xiàn)Blowfish加密算法完整代碼分享

    這篇文章主要介紹了Java語(yǔ)言實(shí)現(xiàn)Blowfish加密算法完整代碼分享,簡(jiǎn)單介紹了blowfish加密算法,具有一定借鑒價(jià)值,需要的朋友可以參考下。
    2017-11-11
  • Java多線程實(shí)現(xiàn)聊天客戶(hù)端和服務(wù)器

    Java多線程實(shí)現(xiàn)聊天客戶(hù)端和服務(wù)器

    這篇文章主要為大家詳細(xì)介紹了Java多線程聊天客戶(hù)端和服務(wù)器實(shí)現(xiàn)代碼,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2016-10-10
  • hibernate5.2的基本配置方法(詳解)

    hibernate5.2的基本配置方法(詳解)

    下面小編就為大家?guī)?lái)一篇hibernate5.2的基本配置方法(詳解)。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2017-06-06
  • Java如何加載外部Jar的類(lèi)并通過(guò)反射調(diào)用類(lèi)的方法

    Java如何加載外部Jar的類(lèi)并通過(guò)反射調(diào)用類(lèi)的方法

    這篇文章主要介紹了Java如何加載外部Jar的類(lèi)并通過(guò)反射調(diào)用類(lèi)的方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2024-06-06
  • Spark集群框架的搭建與入門(mén)

    Spark集群框架的搭建與入門(mén)

    Spark是專(zhuān)為大規(guī)模數(shù)據(jù)處理而設(shè)計(jì)的,基于內(nèi)存快速通用,可擴(kuò)展的集群計(jì)算引擎,實(shí)現(xiàn)了高效的DAG執(zhí)行引擎,可以通過(guò)基于內(nèi)存來(lái)高效處理數(shù)據(jù)流,運(yùn)算速度相比于MapReduce得到了顯著的提高。
    2021-06-06
  • 淺談Java非阻塞同步機(jī)制和CAS

    淺談Java非阻塞同步機(jī)制和CAS

    我們知道在java 5之前同步是通過(guò)Synchronized關(guān)鍵字來(lái)實(shí)現(xiàn)的,在java 5之后,java.util.concurrent包里面添加了很多性能更加強(qiáng)大的同步類(lèi)。這些強(qiáng)大的類(lèi)中很多都實(shí)現(xiàn)了非阻塞的同步機(jī)制從而幫助其提升性能。
    2021-06-06
  • spring cloud feign實(shí)現(xiàn)遠(yuǎn)程調(diào)用服務(wù)傳輸文件的方法

    spring cloud feign實(shí)現(xiàn)遠(yuǎn)程調(diào)用服務(wù)傳輸文件的方法

    這篇文章主要介紹了spring cloud feign實(shí)現(xiàn)遠(yuǎn)程調(diào)用服務(wù)傳輸文件的方法,小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2018-09-09

最新評(píng)論