版權(quán)聲明：本文為斑馬君學(xué)習(xí)總結(jié)文章蛇更，轉(zhuǎn)載請注明出處！

JDK5中添加了新的concurrent包绿鸣，相對同步容器而言谆棺，并發(fā)容器通過一些機(jī)制改進(jìn)了并發(fā)性能栽燕。因為同步容器將所有對容器狀態(tài)的訪問都串行化了，這樣保證了線程的安全性，所以這種方法的代價就是嚴(yán)重降低了并發(fā)性纫谅，當(dāng)多個線程競爭容器時，吞吐量嚴(yán)重降低溅固。因此Java5.0開

始針對多線程并發(fā)訪問設(shè)計付秕，提供了并發(fā)性能較好的并發(fā)容器，引入了java.util.concurrent包侍郭。與Vector和Hashtable询吴、

Collections.synchronizedXxx()同步容器等相比，util.concurrent中引入的并發(fā)容器主要解決了兩個問題：

• 1）根據(jù)具體場景進(jìn)行設(shè)計亮元，盡量避免synchronized猛计，提供并發(fā)性。
• 2）定義了一些并發(fā)安全的復(fù)合操作爆捞，并且保證并發(fā)環(huán)境下的迭代操作不會出錯奉瘤。

util.concurrent中容器在迭代時，可以不封裝在synchronized中煮甥，可以保證不拋異常盗温，但是未必每次看到的都是"最新的、當(dāng)前的"數(shù)據(jù)成肘。
下面是對并發(fā)容器的簡單介紹：

ConcurrentHashMap代替同步的Map（Collections.synchronized（new HashMap()））卖局，眾所周知，HashMap是根據(jù)散列值分段存儲的双霍，同步Map在同步的時候鎖住了所有的段砚偶，而ConcurrentHashMap加鎖的時候根據(jù)散列值鎖住了散列值鎖對應(yīng)的那段，因此提高了并發(fā)性能洒闸。ConcurrentHashMap也增加了對常用復(fù)合操作的支持染坯，比如"若沒有則添加"：putIfAbsent()，替換：replace()顷蟀。這2個操作都是原子操作酒请。

CopyOnWriteArrayList和CopyOnWriteArraySet分別代替List和Set，主要是在遍歷操作為主的情況下來代替同步的List和同步的Set鸣个，這也就是上面所述的思路：迭代過程要保證不出錯羞反，除了加鎖，另外一種方法就是"克隆"容器對象囤萤。

ConcurrentLinkedQuerue是一個先進(jìn)先出的隊列昼窗。它是非阻塞隊列。

ConcurrentSkipListMap可以在高效并發(fā)中替代SoredMap（例如用Collections.synchronzedMap包裝的TreeMap）涛舍。

ConcurrentSkipListSet可以在高效并發(fā)中替代SoredSet（例如用Collections.synchronzedSet包裝的TreeMap）澄惊。

大家都知道HashMap是非線程安全的，Hashtable是線程安全的，但是由于Hashtable是采用synchronized進(jìn)行同步掸驱，相當(dāng)于所有線程進(jìn)行讀寫時都去競爭一把鎖肛搬，導(dǎo)致效率非常低下。

ConcurrentHashMap可以做到讀取數(shù)據(jù)不加鎖毕贼，并且其內(nèi)部的結(jié)構(gòu)可以讓其在進(jìn)行寫操作的時候能夠?qū)㈡i的粒度保持地盡量地小温赔，不用對整個ConcurrentHashMap加鎖。

一鬼癣、ConcurrentHashMap的內(nèi)部結(jié)構(gòu)

ConcurrentHashMap為了提高本身的并發(fā)能力陶贼，在內(nèi)部采用了一個叫做Segment的結(jié)構(gòu)，一個Segment其實就是一個類Hash Table的結(jié)構(gòu)待秃，Segment內(nèi)部維護(hù)了一個鏈表數(shù)組拜秧，我們用下面這一幅圖來看下ConcurrentHashMap的內(nèi)部結(jié)構(gòu)：

二爷速、Segment

我們再來具體了解一下Segment的數(shù)據(jù)結(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;
}

詳細(xì)解釋一下Segment里面的成員變量的意義：
count：Segment中元素的數(shù)量
modCount：對table的大小造成影響的操作的數(shù)量（比如put或者remove操作）
threshold：閾值，Segment里面元素的數(shù)量超過這個值依舊就會對Segment進(jìn)行擴(kuò)容
table：鏈表數(shù)組霞怀，數(shù)組中的每一個元素代表了一個鏈表的頭部
loadFactor：負(fù)載因子惫东，用于確定threshold

三、HashEntry

Segment中的元素是以HashEntry的形式存放在鏈表數(shù)組中的毙石，看一下HashEntry的結(jié)構(gòu)：

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

可以看到HashEntry的一個特點廉沮，除了value以外，其他的幾個變量都是final的徐矩，這樣做是為了防止鏈表結(jié)構(gòu)被破壞滞时，出現(xiàn)ConcurrentModification的情況。

四滤灯、ConcurrentHashMap的初始化

下面我們來結(jié)合源代碼來具體分析一下ConcurrentHashMap的實現(xiàn)坪稽，先看下初始化方法：

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;
while (ssize < concurrencyLevel) {
    ++sshift;
    ssize <<= 1;
}
segmentShift = 32 - sshift;
segmentMask = ssize - 1;
this.segments = Segment.newArray(ssize);

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

CurrentHashMap的初始化一共有三個參數(shù)曼玩，一個initialCapacity，表示初始的容量窒百，一個loadFactor黍判，表示負(fù)載參數(shù)，最后一個是concurrentLevel篙梢，代表ConcurrentHashMap內(nèi)部的Segment的數(shù)量样悟，ConcurrentLevel一經(jīng)指定，不可改變庭猩，后續(xù)如果ConcurrentHashMap的元素數(shù)量增加導(dǎo)致ConrruentHashMap需要擴(kuò)容，ConcurrentHashMap不會增加Segment的數(shù)量陈症，而只會增加Segment中鏈表數(shù)組的容量大小蔼水，這樣的好處是擴(kuò)容過程不需要對整個ConcurrentHashMap做rehash，而只需要對Segment里面的元素做一次rehash就可以了录肯。
整個ConcurrentHashMap的初始化方法還是非常簡單的趴腋，先是根據(jù)concurrentLevel來new出Segment，這里Segment的數(shù)量是不大于concurrentLevel的最大的2的指數(shù)论咏，就是說Segment的數(shù)量永遠(yuǎn)是2的指數(shù)個优炬，這樣的好處是方便采用移位操作來進(jìn)行hash，加快hash的過程厅贪。接下來就是根據(jù)intialCapacity確定Segment的容量的大小蠢护，每一個Segment的容量大小也是2的指數(shù)，同樣使為了加快hash的過程养涮。

這邊需要特別注意一下兩個變量葵硕，分別是segmentShift和segmentMask，這兩個變量在后面將會起到很大的作用贯吓，假設(shè)構(gòu)造函數(shù)確定了Segment的數(shù)量是2的n次方懈凹，那么segmentShift就等于32減去n，而segmentMask就等于2的n次方減一悄谐。

五介评、ConcurrentHashMap的get操作

前面提到過ConcurrentHashMap的get操作是不用加鎖的魁亦，我們這里看一下其實現(xiàn)：

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

看第三行笙蒙，segmentFor這個函數(shù)用于確定操作應(yīng)該在哪一個segment中進(jìn)行滔吠，幾乎對ConcurrentHashMap的所有操作都需要用到這個函數(shù)僧著，我們看下這個函數(shù)的實現(xiàn)：

final Segment<K,V> segmentFor(int hash) {
    return segments[(hash >>> segmentShift) & segmentMask];
}

這個函數(shù)用了位操作來確定Segment被冒，根據(jù)傳入的hash值向右無符號右移segmentShift位粥喜，然后和segmentMask進(jìn)行與操作厉萝，結(jié)合我們之前說的segmentShift和segmentMask的值立莉，就可以得出以下結(jié)論：假設(shè)Segment的數(shù)量是2的n次方屁商，根據(jù)元素的hash值的高n位就可以確定元素到底在哪一個Segment中烟很。
在確定了需要在哪一個segment中進(jìn)行操作以后颈墅，接下來的事情就是調(diào)用對應(yīng)的Segment的get方法：

V get(Object key, int hash) {
if (count != 0) { // read-volatile
    HashEntry<K,V> e = getFirst(hash);
    while (e != null) {
        if (e.hash == hash && key.equals(e.key)) {
            V v = e.value;
            if (v != null)
                return v;
            return readValueUnderLock(e); // recheck
        }
        e = e.next;
    }
}
return null;

先看第二行代碼，這里對count進(jìn)行了一次判斷雾袱，其中count表示Segment中元素的數(shù)量恤筛，我們可以來看一下count的定義：

transient volatile int count;

可以看到count是volatile的，實際上這里里面利用了volatile的語義：

對volatile字段的寫入操作happens-before于每一個后續(xù)的同一個字段的讀操作芹橡。

因為實際上put毒坛、remove等操作也會更新count的值，所以當(dāng)競爭發(fā)生的時候林说，volatile的語義可以保證寫操作在讀操作之前煎殷，也就保證了寫操作對后續(xù)的讀操作都是可見的，這樣后面get的后續(xù)操作就可以拿到完整的元素內(nèi)容腿箩。
然后豪直，在第三行，調(diào)用了getFirst()來取得鏈表的頭部：

HashEntry<K,V> getFirst(int hash) {
    HashEntry<K,V>[] tab = table;
    return tab[hash & (tab.length - 1)];
}

同樣珠移，這里也是用位操作來確定鏈表的頭部弓乙，hash值和HashTable的長度減一做與操作，最后的結(jié)果就是hash值的低n位钧惧，其中n是HashTable的長度以2為底的結(jié)果暇韧。

在確定了鏈表的頭部以后，就可以對整個鏈表進(jìn)行遍歷浓瞪，看第4行懈玻，取出key對應(yīng)的value的值，如果拿出的value的值是null乾颁，則可能這個key酪刀，value對正在put的過程中，如果出現(xiàn)這種情況钮孵，那么就加鎖來保證取出的value是完整的骂倘，如果不是null，則直接返回value巴席。

五历涝、ConcurrentHashMap的put操作

看完了get操作，再看下put操作漾唉，put操作的前面也是確定Segment的過程荧库，這里不再贅述，直接看關(guān)鍵的segment的put方法：

V put(K key, int hash, V value, boolean onlyIfAbsent) {
lock();
try {
    int c = count;
    if (c++ > threshold) // ensure capacity
        rehash();
    HashEntry<K,V>[] tab = table;
    int index = hash & (tab.length - 1);
    HashEntry<K,V> first = tab[index];
    HashEntry<K,V> e = first;
    while (e != null && (e.hash != hash || !key.equals(e.key)))
        e = e.next;

    V oldValue;
    if (e != null) {
        oldValue = e.value;
        if (!onlyIfAbsent)
            e.value = value;
    }
    else {
        oldValue = null;
        ++modCount;
        tab[index] = new HashEntry<K,V>(key, hash, first, value);
        count = c; // write-volatile
    }
    return oldValue;
} finally {
    unlock();
}

首先對Segment的put操作是加鎖完成的赵刑，然后在第五行分衫，如果Segment中元素的數(shù)量超過了閾值（由構(gòu)造函數(shù)中的loadFactor算出）這需要進(jìn)行對Segment擴(kuò)容，并且要進(jìn)行rehash般此，關(guān)于rehash的過程大家可以自己去了解蚪战，這里不詳細(xì)講了牵现。

第8和第9行的操作就是getFirst的過程，確定鏈表頭部的位置邀桑。

第11行這里的這個while循環(huán)是在鏈表中尋找和要put的元素相同key的元素瞎疼，如果找到，就直接更新更新key的value壁畸，如果沒有找到贼急，則進(jìn)入21行這里，生成一個新的HashEntry并且把它加到整個Segment的頭部捏萍，然后再更新count的值太抓。

六、ConcurrentHashMap的remove操作

Remove操作的前面一部分和前面的get和put操作一樣令杈，都是定位Segment的過程走敌，然后再調(diào)用Segment的remove方法：

V remove(Object key, int hash, Object value) {
lock();
try {
    int c = count - 1;
    HashEntry<K,V>[] tab = table;
    int index = hash & (tab.length - 1);
    HashEntry<K,V> first = tab[index];
    HashEntry<K,V> e = first;
    while (e != null && (e.hash != hash || !key.equals(e.key)))
        e = e.next;

    V oldValue = null;
    if (e != null) {
        V v = e.value;
        if (value == null || value.equals(v)) {
            oldValue = v;
            // All entries following removed node can stay
            // in list, but all preceding ones need to be
            // cloned.
            ++modCount;
            HashEntry<K,V> newFirst = e.next;
            for (HashEntry<K,V> p = first; p != e; p = p.next)
                newFirst = new HashEntry<K,V>(p.key, p.hash,
                                              newFirst, p.value);
            tab[index] = newFirst;
            count = c; // write-volatile
        }
    }
    return oldValue;
} finally {
    unlock();
}

七皆辽、ConcurrentHashMap的size操作

在前面的章節(jié)中柑蛇，我們涉及到的操作都是在單個Segment中進(jìn)行的，但是ConcurrentHashMap有一些操作是在多個Segment中進(jìn)行驱闷，比如size操作耻台，ConcurrentHashMap的size操作也采用了一種比較巧的方式，來盡量避免對所有的Segment都加鎖空另。

前面我們提到了一個Segment中的有一個modCount變量盆耽，代表的是對Segment中元素的數(shù)量造成影響的操作的次數(shù)，這個值只增不減扼菠，size操作就是遍歷了兩次Segment摄杂，每次記錄Segment的modCount值，然后將兩次的modCount進(jìn)行比較循榆，如果相同析恢，則表示期間沒有發(fā)生過寫入操作，就將原先遍歷的結(jié)果返回秧饮，如果不相同映挂，則把這個過程再重復(fù)做一次泽篮，如果再不相同，則就需要將所有的Segment都鎖住袖肥，然后一個一個遍歷了咪辱，具體的實現(xiàn)大家可以看ConcurrentHashMap的源碼，這里就不貼了椎组。