歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

JDK1.7 ConcurrentHashMap 源碼淺析

概述

ConcurrentHashMap是HashMap的線程安全版本,使用了分段加鎖的方案,在高並發時有比較好的性能。

本文分析JDK1.7中ConcurrentHashMap的實現。

正文

ConcurrentHashMap概述

HashMap不是線程安全的,要實現線程安全除非加鎖,但這樣性能很低。ConcurrentHashMap把整個HashMap數組分成了若干個Segment,每個Segment裡有一個數組。添加一個Key時,需要先根據hash值計算出其所在Segment,然後再根據hash值計算出在該Segment中的位置。Segment繼承自ReentrantLock,每個Segment就是一個鎖。在多線程的情況下,就減少了鎖競爭,提升了性能。

ConcurrentHashMap存儲結構如下圖所示:

下面我們來分析源碼,看數據是怎麼存儲的。

構造函數

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
    if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
        throw new IllegalArgumentException();
    if (concurrencyLevel > MAX_SEGMENTS)
        concurrencyLevel = MAX_SEGMENTS;
    // Find power-of-two sizes best matching arguments
    int sshift = 0;
    int ssize = 1;
    //concurrencyLevel為並發級別,這一步就是計算出大於concurrencyLevel的最小的2的N次方
    //為什麼不用HashMap中的Integer.highestOneBit((number - 1) << 1)來計算這個值
    //我的理解是concurrencyLevel一般都比較小(默認為16),采用這種計算方法效率更高。
    while (ssize < concurrencyLevel) {
        ++sshift;
        ssize <<= 1;
    }
    //後面根據hash計算segment位置時需要用到
    this.segmentShift = 32 - sshift;
    this.segmentMask = ssize - 1;
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //計算每一個segment中table的length
    int c = initialCapacity / ssize;
    if (c * ssize < initialCapacity)
        ++c;
    int cap = MIN_SEGMENT_TABLE_CAPACITY;
    while (cap < c)
        cap <<= 1;
    // create segments and 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;
}

和HashMap最大的不同就是多了Segment的初始化。

Segment的Size也初始化為2的N次方,這為後面的Map整體resize以及確定一個hash值所在Segment都提供簡便方法。

每個Segment中的table同HashMap中table一樣,接著來看PUT時怎麼計算Segment的位置。

PUT

public V put(K key, V value) {
    Segment<K,V> s;
    if (value == null)
        throw new NullPointerException();
    int hash = hash(key);
    //取得Key的Segment位置
    int j = (hash >>> segmentShift) & segmentMask;
    if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
        (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
        s = ensureSegment(j);
    return s.put(key, hash, value, false);
}

segmentShift:在構造函數中計算出來的,假設concurrencyLevel為16,segmentShift=28(32-4)

segmentMask:15(16-1)

可見求Key所在Segment的算法和HashMap中求Key所在table中的位置一樣,都是 hash & (length-1)。

所以這裡Segment的length也必須是2的N次方。

hash >>> segmentShift是為了使用hash的高位進行與運算。

s.put方法,就是把Key放到Segment中table的響應位置,它的算法和HashMap中類似,只是加入了鎖。

線程安全

HashMap - 非線程安全

Put一個Key時有下面這段代碼:

void createEntry(int hash, K key, V value, int bucketIndex) {
    //1.取得鏈表
    Entry<K,V> e = table[bucketIndex];
    //2.將新Key設置為鏈表的第一個
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

假設有兩個線程A、B,同時進行第1步,它們獲取到的e是同一個,如:x,y,z

然後線程A運行到第2步,為e添加了一個新元素a,並賦值給table[bucketIndex],此時table[bucketIndex]為:a,x,y,z

而後線程B運行到第2步,為e添加了一個新元素b,並賦值給table[bucketIndex],此時table[bucketIndex]為:b,x,y,z

所以這種情況下就會有問題,這只是其中的一個例子,所以HashMap是非線程安全的。

ConcurrentHashMap - 線程安全

Put一個Key到Table時,使用如下代碼:

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
            HashEntry<K,V> node = tryLock() ? null :
                scanAndLockForPut(key, hash, value);
            V oldValue;
            try {
                ......
            } finally {
                unlock();
            }
            return oldValue;
}

可以看到put時,加入了Lock,這就保證了線程的安全性。

查看ConcurrentHashMap源代碼可以發現,ConcurrentHashMap的remove、replace等有可能引起線程安全問題的地方都加了Lock。

ConcurrentHashMap的Get方法並不是完全線程安全,因為Get時沒有加鎖,但JDK用了很多volatile類型變量來保證在大多數情況下的線程安全。

總結:

ConcurrentHashMap在絕大多數情況下是線程安全的,在多線程情況下請使用ConcurrentHashMap。

Copyright © Linux教程網 All Rights Reserved