還不懂 ConcurrentHashMap ?這份源碼分析了解一下

上一篇文章介紹了 HashMap 源碼跷坝,反響不錯酵镜,也有很多同學發(fā)表了自己的觀點,這次又來了柴钻,這次是 ConcurrentHashMap 了笋婿,作為線程安全的HashMap ,它的使用頻率也是很高顿颅。那么它的存儲結(jié)構(gòu)和實現(xiàn)原理是怎么樣的呢缸濒?

1. ConcurrentHashMap 1.7

1. 存儲結(jié)構(gòu)

Java 7 ConcurrentHashMap 存儲結(jié)構(gòu)

Java 7 中 ConcurrentHashMap 的存儲結(jié)構(gòu)如上圖,ConcurrnetHashMap 由很多個 Segment 組合粱腻,而每一個 Segment 是一個類似于 HashMap 的結(jié)構(gòu)庇配,所以每一個 HashMap 的內(nèi)部可以進行擴容。但是 Segment 的個數(shù)一旦初始化就不能改變绍些,默認 Segment 的個數(shù)是 16 個捞慌,你也可以認為 ConcurrentHashMap 默認支持最多 16 個線程并發(fā)。

2. 初始化

通過 ConcurrentHashMap 的無參構(gòu)造探尋 ConcurrentHashMap 的初始化流程柬批。

    /**
     * Creates a new, empty map with a default initial capacity (16),
     * load factor (0.75) and concurrencyLevel (16).
     */
    public ConcurrentHashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
    }

無參構(gòu)造中調(diào)用了有參構(gòu)造啸澡,傳入了三個參數(shù)的默認值,他們的值是氮帐。

    /**
     * 默認初始化容量
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * 默認負載因子
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * 默認并發(fā)級別
     */
    static final int DEFAULT_CONCURRENCY_LEVEL = 16;

接著看下這個有參構(gòu)造函數(shù)的內(nèi)部實現(xiàn)邏輯嗅虏。

@SuppressWarnings("unchecked")
public ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel) {
    // 參數(shù)校驗
    if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
        throw new IllegalArgumentException();
    // 校驗并發(fā)級別大小,大于 1<<16上沐,重置為 65536
    if (concurrencyLevel > MAX_SEGMENTS)
        concurrencyLevel = MAX_SEGMENTS;
    // Find power-of-two sizes best matching arguments
    // 2的多少次方
    int sshift = 0;
    int ssize = 1;
    // 這個循環(huán)可以找到 concurrencyLevel 之上最近的 2的次方值
    while (ssize < concurrencyLevel) {
        ++sshift;
        ssize <<= 1;
    }
    // 記錄段偏移量
    this.segmentShift = 32 - sshift;
    // 記錄段掩碼
    this.segmentMask = ssize - 1;
    // 設(shè)置容量
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // c = 容量 / ssize 皮服,默認 16 / 16 = 1,這里是計算每個 Segment 中的類似于 HashMap 的容量
    int c = initialCapacity / ssize;
    if (c * ssize < initialCapacity)
        ++c;
    int cap = MIN_SEGMENT_TABLE_CAPACITY;
    //Segment 中的類似于 HashMap 的容量至少是2或者2的倍數(shù)
    while (cap < c)
        cap <<= 1;
    // create segments and segments[0]
    // 創(chuàng)建 Segment 數(shù)組参咙,設(shè)置 segments[0]
    Segment<K,V> s0 = new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
                         (HashEntry<K,V>[])new HashEntry[cap]);
    Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
    UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
    this.segments = ss;
}

總結(jié)一下在 Java 7 中 ConcurrnetHashMap 的初始化邏輯龄广。

  1. 必要參數(shù)校驗。
  2. 校驗并發(fā)級別 concurrencyLevel 大小蕴侧,如果大于最大值择同,重置為最大值。無慘構(gòu)造默認值是 16.
  3. 尋找并發(fā)級別 concurrencyLevel 之上最近的 2 的冪次方值净宵,作為初始化容量大小敲才,默認是 16裹纳。
  4. 記錄 segmentShift 偏移量,這個值為【容量 = 2 的N次方】中的 N归斤,在后面 Put 時計算位置時會用到。默認是 32 - sshift = 28.
  5. 記錄 segmentMask刁岸,默認是 ssize - 1 = 16 -1 = 15.
  6. 初始化 segments[0]脏里,默認大小為 2負載因子 0.75虹曙,擴容閥值是 20.75=1.5*迫横,插入第二個值時才會進行擴容。

3. put

接著上面的初始化參數(shù)繼續(xù)查看 put 方法源碼酝碳。

/**
 * Maps the specified key to the specified value in this table.
 * Neither the key nor the value can be null.
 *
 * <p> The value can be retrieved by calling the <tt>get</tt> method
 * with a key that is equal to the original key.
 *
 * @param key key with which the specified value is to be associated
 * @param value value to be associated with the specified key
 * @return the previous value associated with <tt>key</tt>, or
 *         <tt>null</tt> if there was no mapping for <tt>key</tt>
 * @throws NullPointerException if the specified key or value is null
 */
public V put(K key, V value) {
    Segment<K,V> s;
    if (value == null)
        throw new NullPointerException();
    int hash = hash(key);
    // hash 值無符號右移 28位(初始化時獲得)矾踱,然后與 segmentMask=15 做與運算
    // 其實也就是把高4位與segmentMask(1111)做與運算
    int j = (hash >>> segmentShift) & segmentMask;
    if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
         (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
        // 如果查找到的 Segment 為空,初始化
        s = ensureSegment(j);
    return s.put(key, hash, value, false);
}

/**
 * Returns the segment for the given index, creating it and
 * recording in segment table (via CAS) if not already present.
 *
 * @param k the index
 * @return the segment
 */
@SuppressWarnings("unchecked")
private Segment<K,V> ensureSegment(int k) {
    final Segment<K,V>[] ss = this.segments;
    long u = (k << SSHIFT) + SBASE; // raw offset
    Segment<K,V> seg;
    // 判斷 u 位置的 Segment 是否為null
    if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
        Segment<K,V> proto = ss[0]; // use segment 0 as prototype
        // 獲取0號 segment 里的 HashEntry<K,V> 初始化長度
        int cap = proto.table.length;
        // 獲取0號 segment 里的 hash 表里的擴容負載因子疏哗,所有的 segment 的 loadFactor 是相同的
        float lf = proto.loadFactor;
        // 計算擴容閥值
        int threshold = (int)(cap * lf);
        // 創(chuàng)建一個 cap 容量的 HashEntry 數(shù)組
        HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
        if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) { // recheck
            // 再次檢查 u 位置的 Segment 是否為null呛讲,因為這時可能有其他線程進行了操作
            Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
            // 自旋檢查 u 位置的 Segment 是否為null
            while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
                   == null) {
                // 使用CAS 賦值,只會成功一次
                if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
                    break;
            }
        }
    }
    return seg;
}

上面的源碼分析了 ConcurrentHashMap 在 put 一個數(shù)據(jù)時的處理流程返奉,下面梳理下具體流程贝搁。

  1. 計算要 put 的 key 的位置,獲取指定位置的 Segment芽偏。

  2. 如果指定位置的 Segment 為空雷逆,則初始化這個 Segment.

    初始化 Segment 流程:

    1. 檢查計算得到的位置的 Segment 是否為null.
    2. 為 null 繼續(xù)初始化,使用 Segment[0] 的容量和負載因子創(chuàng)建一個 HashEntry 數(shù)組污尉。
    3. 再次檢查計算得到的指定位置的 Segment 是否為null.
    4. 使用創(chuàng)建的 HashEntry 數(shù)組初始化這個 Segment.
    5. 自旋判斷計算得到的指定位置的 Segment 是否為null膀哲,使用 CAS 在這個位置賦值為 Segment.
  3. Segment.put 插入 key,value 值。

上面探究了獲取 Segment 段和初始化 Segment 段的操作被碗。最后一行的 Segment 的 put 方法還沒有查看某宪,繼續(xù)分析。

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    // 獲取 ReentrantLock 獨占鎖锐朴,獲取不到缩抡,scanAndLockForPut 獲取。
    HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
        HashEntry<K,V>[] tab = table;
        // 計算要put的數(shù)據(jù)位置
        int index = (tab.length - 1) & hash;
        // CAS 獲取 index 坐標的值
        HashEntry<K,V> first = entryAt(tab, index);
        for (HashEntry<K,V> e = first;;) {
            if (e != null) {
                // 檢查是否 key 已經(jīng)存在包颁,如果存在瞻想,則遍歷鏈表尋找位置,找到后替換 value
                K k;
                if ((k = e.key) == key ||
                    (e.hash == hash && key.equals(k))) {
                    oldValue = e.value;
                    if (!onlyIfAbsent) {
                        e.value = value;
                        ++modCount;
                    }
                    break;
                }
                e = e.next;
            }
            else {
                // first 有值沒說明 index 位置已經(jīng)有值了娩嚼,有沖突蘑险,鏈表頭插法。
                if (node != null)
                    node.setNext(first);
                else
                    node = new HashEntry<K,V>(hash, key, value, first);
                int c = count + 1;
                // 容量大于擴容閥值岳悟,小于最大容量佃迄,進行擴容
                if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                    rehash(node);
                else
                    // index 位置賦值 node泼差,node 可能是一個元素,也可能是一個鏈表的表頭
                    setEntryAt(tab, index, node);
                ++modCount;
                count = c;
                oldValue = null;
                break;
            }
        }
    } finally {
        unlock();
    }
    return oldValue;
}

由于 Segment 繼承了 ReentrantLock呵俏,所以 Segment 內(nèi)部可以很方便的獲取鎖堆缘,put 流程就用到了這個功能。

  1. tryLock() 獲取鎖普碎,獲取不到使用 scanAndLockForPut 方法繼續(xù)獲取吼肥。

  2. 計算 put 的數(shù)據(jù)要放入的 index 位置,然后獲取這個位置上的 HashEntry 麻车。

  3. 遍歷 put 新元素缀皱,為什么要遍歷?因為這里獲取的 HashEntry 可能是一個空元素动猬,也可能是鏈表已存在啤斗,所以要區(qū)別對待。

    如果這個位置上的 HashEntry 不存在

    1. 如果當前容量大于擴容閥值赁咙,小于最大容量钮莲,進行擴容
    2. 直接頭插法插入彼水。

    如果這個位置上的 HashEntry 存在

    1. 判斷鏈表當前元素 Key 和 hash 值是否和要 put 的 key 和 hash 值一致臂痕。一致則替換值
    2. 不一致,獲取鏈表下一個節(jié)點猿涨,直到發(fā)現(xiàn)相同進行值替換握童,或者鏈表表里完畢沒有相同的。
      1. 如果當前容量大于擴容閥值叛赚,小于最大容量澡绩,進行擴容
      2. 直接鏈表頭插法插入俺附。
  4. 如果要插入的位置之前已經(jīng)存在肥卡,替換后返回舊值,否則返回 null.

這里面的第一步中的 scanAndLockForPut 操作這里沒有介紹事镣,這個方法做的操作就是不斷的自旋 tryLock() 獲取鎖步鉴。當自旋次數(shù)大于指定次數(shù)時,使用 lock() 阻塞獲取鎖璃哟。在自旋時順表獲取下 hash 位置的 HashEntry氛琢。

private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
    HashEntry<K,V> first = entryForHash(this, hash);
    HashEntry<K,V> e = first;
    HashEntry<K,V> node = null;
    int retries = -1; // negative while locating node
    // 自旋獲取鎖
    while (!tryLock()) {
        HashEntry<K,V> f; // to recheck first below
        if (retries < 0) {
            if (e == null) {
                if (node == null) // speculatively create node
                    node = new HashEntry<K,V>(hash, key, value, null);
                retries = 0;
            }
            else if (key.equals(e.key))
                retries = 0;
            else
                e = e.next;
        }
        else if (++retries > MAX_SCAN_RETRIES) {
            // 自旋達到指定次數(shù)后,阻塞等到只到獲取到鎖
            lock();
            break;
        }
        else if ((retries & 1) == 0 &&
                 (f = entryForHash(this, hash)) != first) {
            e = first = f; // re-traverse if entry changed
            retries = -1;
        }
    }
    return node;
}

4. 擴容 rehash

ConcurrentHashMap 的擴容只會擴容到原來的兩倍随闪。老數(shù)組里的數(shù)據(jù)移動到新的數(shù)組時阳似,位置要么不變,要么變?yōu)?index+ oldSize铐伴,參數(shù)里的 node 會在擴容之后使用鏈表頭插法插入到指定位置撮奏。

private void rehash(HashEntry<K,V> node) {
    HashEntry<K,V>[] oldTable = table;
    // 老容量
    int oldCapacity = oldTable.length;
    // 新容量俏讹,擴大兩倍
    int newCapacity = oldCapacity << 1;
    // 新的擴容閥值 
    threshold = (int)(newCapacity * loadFactor);
    // 創(chuàng)建新的數(shù)組
    HashEntry<K,V>[] newTable = (HashEntry<K,V>[]) new HashEntry[newCapacity];
    // 新的掩碼,默認2擴容后是4畜吊,-1是3泽疆,二進制就是11。
    int sizeMask = newCapacity - 1;
    for (int i = 0; i < oldCapacity ; i++) {
        // 遍歷老數(shù)組
        HashEntry<K,V> e = oldTable[i];
        if (e != null) {
            HashEntry<K,V> next = e.next;
            // 計算新的位置玲献,新的位置只可能是不便或者是老的位置+老的容量殉疼。
            int idx = e.hash & sizeMask;
            if (next == null)   //  Single node on list
                // 如果當前位置還不是鏈表,只是一個元素青自,直接賦值
                newTable[idx] = e;
            else { // Reuse consecutive sequence at same slot
                // 如果是鏈表了
                HashEntry<K,V> lastRun = e;
                int lastIdx = idx;
                // 新的位置只可能是不便或者是老的位置+老的容量株依。
                // 遍歷結(jié)束后驱证,lastRun 后面的元素位置都是相同的
                for (HashEntry<K,V> last = next; last != null; last = last.next) {
                    int k = last.hash & sizeMask;
                    if (k != lastIdx) {
                        lastIdx = k;
                        lastRun = last;
                    }
                }
                // 延窜,lastRun 后面的元素位置都是相同的,直接作為鏈表賦值到新位置抹锄。
                newTable[lastIdx] = lastRun;
                // Clone remaining nodes
                for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
                    // 遍歷剩余元素逆瑞,頭插法到指定 k 位置。
                    V v = p.value;
                    int h = p.hash;
                    int k = h & sizeMask;
                    HashEntry<K,V> n = newTable[k];
                    newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
                }
            }
        }
    }
    // 頭插法插入新的節(jié)點
    int nodeIndex = node.hash & sizeMask; // add the new node
    node.setNext(newTable[nodeIndex]);
    newTable[nodeIndex] = node;
    table = newTable;
}

有些同學可能會對最后的兩個 for 循環(huán)有疑惑伙单,這里第一個 for 是為了尋找這樣一個節(jié)點获高,這個節(jié)點后面的所有 next 節(jié)點的新位置都是相同的。然后把這個作為一個鏈表賦值到新位置吻育。第二個 for 循環(huán)是為了把剩余的元素通過頭插法插入到指定位置鏈表念秧。這樣實現(xiàn)的原因可能是基于概率統(tǒng)計屿岂,有深入研究的同學可以發(fā)表下意見胡诗。

5. get

到這里就很簡單了,get 方法只需要兩步即可菱蔬。

  1. 計算得到 key 的存放位置游两。
  2. 遍歷指定位置查找相同 key 的 value 值砾层。
public V get(Object key) {
    Segment<K,V> s; // manually integrate access methods to reduce overhead
    HashEntry<K,V>[] tab;
    int h = hash(key);
    long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
    // 計算得到 key 的存放位置
    if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
        (tab = s.table) != null) {
        for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
                 (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
             e != null; e = e.next) {
            // 如果是鏈表,遍歷查找到相同 key 的 value贱案。
            K k;
            if ((k = e.key) == key || (e.hash == h && key.equals(k)))
                return e.value;
        }
    }
    return null;
}

2. ConcurrentHashMap 1.8

1. 存儲結(jié)構(gòu)

Java8 ConcurrentHashMap 存儲結(jié)構(gòu)(圖片來自 javadoop)

可以發(fā)現(xiàn) Java8 的 ConcurrentHashMap 相對于 Java7 來說變化比較大肛炮,不再是之前的 Segment 數(shù)組 + HashEntry 數(shù)組 + 鏈表,而是 Node 數(shù)組 + 鏈表 / 紅黑樹宝踪。當沖突鏈表達到一定長度時侨糟,鏈表會轉(zhuǎn)換成紅黑樹。

2. 初始化 initTable

/**
 * Initializes table, using the size recorded in sizeCtl.
 */
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        // 如果 sizeCtl < 0 ,說明另外的線程執(zhí)行CAS 成功瘩燥,正在進行初始化粟害。
        if ((sc = sizeCtl) < 0)
            // 讓出 CPU 使用權(quán)
            Thread.yield(); // lost initialization race; just spin
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                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;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

從源碼中可以發(fā)現(xiàn) ConcurrentHashMap 的初始化是通過自旋和 CAS 操作完成的。里面需要注意的是變量 sizeCtl 颤芬,它的值決定著當前的初始化狀態(tài)悲幅。

  1. -1 說明正在初始化
  2. -N 說明有N-1個線程正在進行擴容
  3. 表示 table 初始化大小套鹅,如果 table 沒有初始化
  4. 表示 table 容量,如果 table 已經(jīng)初始化汰具。

3. put

直接過一遍 put 源碼卓鹿。

public V put(K key, V value) {
    return putVal(key, value, false);
}

/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
    // key 和 value 不能為空
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        // f = 目標位置元素
        Node<K,V> f; int n, i, fh;// fh 后面存放目標位置的元素 hash 值
        if (tab == null || (n = tab.length) == 0)
            // 數(shù)組桶為空,初始化數(shù)組桶(自旋+CAS)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 桶內(nèi)為空留荔,CAS 放入吟孙,不加鎖,成功了就直接 break 跳出
            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)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            // 使用 synchronized 加鎖加入節(jié)點
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    // 說明是鏈表
                    if (fh >= 0) {
                        binCount = 1;
                        // 循環(huán)加入新的或者覆蓋節(jié)點
                        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) {
                        // 紅黑樹
                        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;
                        }
                    }
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}
  1. 根據(jù) key 計算出 hashcode 聚蝶。

  2. 判斷是否需要進行初始化杰妓。

  3. 即為當前 key 定位出的 Node,如果為空表示當前位置可以寫入數(shù)據(jù)碘勉,利用 CAS 嘗試寫入巷挥,失敗則自旋保證成功。

  4. 如果當前位置的 hashcode == MOVED == -1,則需要進行擴容验靡。

  5. 如果都不滿足倍宾,則利用 synchronized 鎖寫入數(shù)據(jù)。

  6. 如果數(shù)量大于 TREEIFY_THRESHOLD 則要轉(zhuǎn)換為紅黑樹胜嗓。

4. get

get 流程比較簡單高职,直接過一遍源碼。

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    // key 所在的 hash 位置
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        // 如果指定位置元素存在辞州,頭結(jié)點hash值相同
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                // key hash 值相等怔锌,key值相同,直接返回元素 value
                return e.val;
        }
        else if (eh < 0)
            // 頭結(jié)點hash值小于0变过,說明正在擴容或者是紅黑樹埃元,find查找
            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;
}

總結(jié)一下 get 過程:

  1. 根據(jù) hash 值計算位置牵啦。
  2. 查找到指定位置亚情,如果頭節(jié)點就是要找的,直接返回它的 value.
  3. 如果頭節(jié)點 hash 值小于 0 哈雏,說明正在擴容或者是紅黑樹楞件,查找之。
  4. 如果是鏈表裳瘪,遍歷查找之土浸。

總結(jié):

總的來說 ConcruuentHashMap 在 Java8 中相對于 Java7 來說變化還是挺大的,

3. 總結(jié)

Java7 中 ConcruuentHashMap 使用的分段鎖彭羹,也就是每一個 Segment 上同時只有一個線程可以操作黄伊,每一個 Segment 都是一個類似 HashMap 數(shù)組的結(jié)構(gòu),它可以擴容派殷,它的沖突會轉(zhuǎn)化為鏈表还最。但是 Segment 的個數(shù)一但初始化就不能改變墓阀。

Java8 中的 ConcruuentHashMap 使用的 Synchronized 鎖加 CAS 的機制。結(jié)構(gòu)也由 Java7 中的 Segment 數(shù)組 + HashEntry 數(shù)組 + 鏈表 進化成了 Node 數(shù)組 + 鏈表 / 紅黑樹拓轻,Node 是類似于一個 HashEntry 的結(jié)構(gòu)斯撮。它的沖突再達到一定大小時會轉(zhuǎn)化成紅黑樹,在沖突小于一定數(shù)量時又退回鏈表扶叉。

有些同學可能對 Synchronized 的性能存在疑問勿锅,其實 Synchronized 鎖自從引入鎖升級策略后,性能不再是問題枣氧,有興趣的同學可以自己了解下 Synchronized 的鎖升級溢十。

<完>

如果你喜歡這篇文章,可以關(guān)注公眾號达吞,一起成長张弛。回復 666 還有資料獲取宗挥。
出處:https://www.wdbyte.com

image
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末乌庶,一起剝皮案震驚了整個濱河市种蝶,隨后出現(xiàn)的幾起案子契耿,更是在濱河造成了極大的恐慌,老刑警劉巖螃征,帶你破解...
    沈念sama閱讀 216,744評論 6 502
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件搪桂,死亡現(xiàn)場離奇詭異,居然都是意外死亡盯滚,警方通過查閱死者的電腦和手機踢械,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,505評論 3 392
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來魄藕,“玉大人内列,你說我怎么就攤上這事”陈剩” “怎么了话瞧?”我有些...
    開封第一講書人閱讀 163,105評論 0 353
  • 文/不壞的土叔 我叫張陵,是天一觀的道長寝姿。 經(jīng)常有香客問我交排,道長,這世上最難降的妖魔是什么饵筑? 我笑而不...
    開封第一講書人閱讀 58,242評論 1 292
  • 正文 為了忘掉前任埃篓,我火速辦了婚禮,結(jié)果婚禮上根资,老公的妹妹穿的比我還像新娘架专。我一直安慰自己同窘,他們只是感情好,可當我...
    茶點故事閱讀 67,269評論 6 389
  • 文/花漫 我一把揭開白布部脚。 她就那樣靜靜地躺著塞椎,像睡著了一般睛低。 火紅的嫁衣襯著肌膚如雪案狠。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,215評論 1 299
  • 那天钱雷,我揣著相機與錄音骂铁,去河邊找鬼。 笑死罩抗,一個胖子當著我的面吹牛拉庵,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播套蒂,決...
    沈念sama閱讀 40,096評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼钞支,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了操刀?” 一聲冷哼從身側(cè)響起烁挟,我...
    開封第一講書人閱讀 38,939評論 0 274
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎骨坑,沒想到半個月后撼嗓,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,354評論 1 311
  • 正文 獨居荒郊野嶺守林人離奇死亡欢唾,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,573評論 2 333
  • 正文 我和宋清朗相戀三年且警,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片礁遣。...
    茶點故事閱讀 39,745評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡斑芜,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出祟霍,到底是詐尸還是另有隱情杏头,我是刑警寧澤,帶...
    沈念sama閱讀 35,448評論 5 344
  • 正文 年R本政府宣布浅碾,位于F島的核電站大州,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏垂谢。R本人自食惡果不足惜厦画,卻給世界環(huán)境...
    茶點故事閱讀 41,048評論 3 327
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧根暑,春花似錦力试、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,683評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至淳地,卻和暖如春怖糊,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背颇象。 一陣腳步聲響...
    開封第一講書人閱讀 32,838評論 1 269
  • 我被黑心中介騙來泰國打工伍伤, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人遣钳。 一個月前我還...
    沈念sama閱讀 47,776評論 2 369
  • 正文 我出身青樓扰魂,卻偏偏與公主長得像,于是被迫代替她去往敵國和親蕴茴。 傳聞我的和親對象是個殘疾皇子劝评,可洞房花燭夜當晚...
    茶點故事閱讀 44,652評論 2 354

推薦閱讀更多精彩內(nèi)容