一、前言

ConcurrentHashMap是線程安全并且高效的HashMap，其它的類似容器有以下缺點：

• HashMap在并發(fā)執(zhí)行put操作時，會導(dǎo)致Entry鏈表形成環(huán)形數(shù)據(jù)結(jié)構(gòu)，就會產(chǎn)生死循環(huán)獲取Entry，參考文章 HashMap并發(fā)導(dǎo)致死循環(huán)
• HashTable使用synchronized來保證線程安全，但在線程競爭激烈的情況下HashTable的效率非常低下。

ConcurrentHashMap高效的原因在于它采用 鎖分段技術(shù)，首先將數(shù)據(jù)分成一段一段地存儲，然后給每段數(shù)據(jù)配一把鎖，當(dāng)一個線程占用鎖并且訪問一段數(shù)據(jù)的時候，其他段的數(shù)據(jù)也能被其他線程訪問。

二、 ConcurrentHashMap 的結(jié)構(gòu)

ConcurrentHashMap是由Segment數(shù)組結(jié)構(gòu)和HashEntry數(shù)組結(jié)構(gòu)組成：

• Segment是一種可重入鎖，在ConcurrentHashMap里面扮演鎖的角色。
• HashEntry則用于存儲鍵值對數(shù)據(jù)。

一個ConcurrentHashMap里包含一個Segment數(shù)組，它的結(jié)構(gòu)和HashMap類似，是一種數(shù)組和鏈表結(jié)構(gòu)。

segment

Segment 結(jié)構(gòu)

static final class Segment<K,V> extends ReentrantLock implements Serializable {
    transient volatile int count;
    transient int modCount;
    transient int threshold;
    transient volatile HashEntry<K,V>[] table;
    final float loadFactor;
}

• count：Segment中元素的數(shù)量
• modCount：對table的大小造成影響的操作的數(shù)量
• threshold：閾值，Segment里面元素的數(shù)量超過這個值依舊就會對Segment進(jìn)行擴(kuò)容
• table：鏈表數(shù)組，數(shù)組中的每一個元素代表了一個鏈表的頭部
• loadFactor：負(fù)載因子，用于確定threshold

HashEntry 結(jié)構(gòu)

static final class HashEntry<K,V> {
    final K key;
    final int hash;
    volatile V value;
    final HashEntry<K,V> next;
}

2.1 初始化

ConcurrentHashMap的初始化方法是通過initialCapacity、loadFactor和concurrencyLevel等幾個參數(shù)來初始化segment數(shù)組、段偏移量segmentShift、段掩碼segmentMask和每個segment里的HashEntry來實現(xiàn)的。

2.1.1 初始化 segment 數(shù)組

初始化segment的源代碼如下，它會計算出：

• ssize：segment數(shù)組的長度
• segmentShift：sshift等于ssize從1向左移位的次數(shù)，segmentShift等于32-sshift，segmentShift用于 定位參與散列運算的位數(shù)
• segmentMask：散列運算的掩碼，等于ssize-1

if (concurrencyLevel > MAX_SEGMENTS)
    concurrencyLevel = MAX_SEGMENTS;
int sshift = 0;
int ssize = 1;
//計算 segments 數(shù)組的長度，它是大于等于 concurrencyLevel 的最小的 2 的 N 次方。
while (ssize < concurrencyLevel) {
    ++sshift;
    ssize <<= 1;
}
segmentShift = 32 - sshift;
segmentMask = ssize - 1;
this.segments = Segment.newArray(ssize);

2.1.2 初始化每個 segment

輸入?yún)?shù)initialCapacity是ConcurrentHashMap的初始化容量，loadFactor是每個segment的負(fù)載因子，在構(gòu)造方法里通過這兩個參數(shù)來初始化數(shù)組中的每個segment。

if (initialCapacity < MAXIMUM_CAPACITY) {
    initialCapacity = MAXIMUM_CAPACITY;
}
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity) {
    ++c;
}
int cap = 1;
while (cap < c) {
    cap <<= 1;
}
for (int i = 0; i < this.segments.length; i++) {
    this.segments[i] = new Segment<K, V>(cap, loadFactor);
}

cap 是 segment 里 HashEntry 數(shù)組的長度，它等于initialCapacity / ssize，如果c大于1，就會取大于等于c的2的N次方。segment的容量threshold等于(int) cap * loadFactor，默認(rèn)情況下initialCapacity等于16，ssize等于16，loadFactor等于0.75，因此cap等于1，threshold等于0。

2.2 定位 segment

在插入和獲取元素的時候，必須先通過散列算法定位到Segment，ConcurrentHashMap會首先對元素的hashCode()進(jìn)行一次再散列。

private static int hash(int h) {
    h += (h << 15) ^ 0xffffcd7d;
    h ^= (h >>> 10);
    h += (h << 3);
    h ^= (h >>> 6);
    h += (h << 2) + (h << 14);
    return h ^ (h >>> 16);
}

再散列的目的是減少散列沖突，使元素能夠均勻地分布在不同的Segment上，從而提高容器的存取效率。

2.3 操作

2.3.1 get 操作

segment的get操作過程為：先進(jìn)行一次再散列，然后使用這個散列值通過散列運算定位到Segment，再通過散列算法定位到元素。

public V get(Object key) {
    int hash = hash(key.hashCode());
    return segmentFor(hash).get(key, hash);
}

get操作的高效之處在于整個get過程不需要加鎖，除非讀到的值為空才加鎖重讀。在它的get方法里，將要使用的共享變量都定義成volatile類型，如用于統(tǒng)計當(dāng)前segment大小的count字段和用于存儲值的HashEntry的value，定義成volatile的變量，能夠在線程之間保持可見性，能夠被多線程同時讀，并且保證不會讀到過期的值，在get操作里，只需要讀而不需要寫共享變量count和value，所以可以不用加鎖。

transient volatile int count;
volatile V value;

2.3.2 put 操作

由于put方法需要對共享變量進(jìn)行寫入，所以為了線程安全，在操作共享變量時必須加鎖。put方法首先定位到Segment，然后在Segment里進(jìn)行插入操作。插入操作需要經(jīng)歷兩個步驟：

• 判斷是否需要對Segment里的HashEntry數(shù)組進(jìn)行擴(kuò)容
• 定位添加元素的位置，然后將其放在HashEntry數(shù)組里

2.3.3 size 操作

如果要統(tǒng)計整個ConcurrentHashMap里元素的大小，就必須統(tǒng)計所有Segment元素的大小后求和，雖然每個Segment的全局變量count是一個volatile變量，在相加時可以獲取最新值，但是不能保證之前累加過的Segment大小不發(fā)生變化。

因此，ConcurrentHashMap會先嘗試2次通過不鎖住Segment的方式來統(tǒng)計各個Segment大小，如果統(tǒng)計的過程中，容器的count發(fā)生了變化，則再采用加鎖的方式來統(tǒng)計所有Segment的大小。

檢測容器大小是否發(fā)生變化的原理為：在put、remove和clean方法里操作元素前會將變量modCount進(jìn)行加1，那么在統(tǒng)計size前后比較modCount是否發(fā)生變化，從而得知容器的大小是否發(fā)生變化。

三、參考文獻(xiàn)

<<Java并發(fā)編程的藝術(shù)>> - Java并發(fā)容器和框架