本節(jié)介紹一個常用的并發(fā)容器 - ConcurrentHashMap，它是HashMap的并發(fā)版本，與HashMap相比，它有如下特點：

  • 并發(fā)安全

  • 直接支持一些原子復(fù)合操作

  • 支持高并發(fā)、讀操作完全并行、寫操作支持一定程度的并行

  • 與同步容器Collections.synchronizedMap相比，迭代不用加鎖，不會拋出ConcurrentModificationException

  • 弱一致性

我們分別來看下。

并發(fā)安全

我們知道，HashMap不是并發(fā)安全的，在并發(fā)更新的情況下，HashMap的鏈表結(jié)構(gòu)可能形成環(huán)，出現(xiàn)死循環(huán)，占滿CPU，我們看個例子：

Android培訓(xùn),安卓培訓(xùn),手機開發(fā)培訓(xùn),移動開發(fā)培訓(xùn),云培訓(xùn)培訓(xùn)

public static void unsafeConcurrentUpdate() {    final Map<Integer, Integer> map = new HashMap<>();    for (int i = 0; i < 100; i++) {
        Thread t = new Thread() {
            Random rnd = new Random();

            @Override            public void run() {                for (int i = 0; i < 100; i++) {
                    map.put(rnd.nextInt(), 1);
                }
            }
        };
        t.start();
    }
}

Android培訓(xùn),安卓培訓(xùn),手機開發(fā)培訓(xùn),移動開發(fā)培訓(xùn),云培訓(xùn)培訓(xùn)

運行上面的代碼，在我的機器上，每次都會出現(xiàn)死循環(huán)，占滿CPU。

為什么會出現(xiàn)死循環(huán)呢？死循環(huán)出現(xiàn)在多個線程同時擴容哈希表的時候，不是同時更新一個鏈表的時候，那種情況可能會出現(xiàn)更新丟失，但不會死循環(huán)，具體過程比較復(fù)雜，我們就不解釋了，感興趣的讀者可以參考這篇文章，http://coolshell.cn/articles/9606.html。

使用Collections.synchronizedMap方法可以生成一個同步容器，避免該問題，替換第一行代碼即可：

final Map<Integer, Integer> map = Collections.synchronizedMap(new HashMap<Integer, Integer>());

在Java中，HashMap還有一個同步版本Hashtable，它與使用synchronizedMap生成的Map基本是一樣的，也是在每個方法調(diào)用上加了synchronized，我們就不贅述了。

同步容器有幾個問題：

  • 每個方法都需要同步，支持的并發(fā)度比較低

  • 對于迭代和復(fù)合操作，需要調(diào)用方加鎖，使用比較麻煩，且容易忘記

ConcurrentHashMap沒有這些問題，它同樣實現(xiàn)了Map接口，也是基于哈希表實現(xiàn)的，上面的代碼替換第一行即可：

final Map<Integer, Integer> map = new ConcurrentHashMap<>();

原子復(fù)合操作

除了Map接口，ConcurrentHashMap還實現(xiàn)了一個接口ConcurrentMap，接口定義了一些條件更新操作，具體定義為：

Android培訓(xùn),安卓培訓(xùn),手機開發(fā)培訓(xùn),移動開發(fā)培訓(xùn),云培訓(xùn)培訓(xùn)

public interface ConcurrentMap<K, V> extends Map<K, V> {    //條件更新，如果Map中沒有key，設(shè)置key為value，返回原來key對應(yīng)的值，如果沒有，返回null
    V putIfAbsent(K key, V value);    //條件刪除，如果Map中有key，且對應(yīng)的值為value，則刪除，如果刪除了，返回true，否則false
    boolean remove(Object key, Object value);    //條件替換，如果Map中有key，且對應(yīng)的值為oldValue，則替換為newValue，如果替換了，返回ture，否則false
    boolean replace(K key, V oldValue, V newValue);    //條件替換，如果Map中有key，則替換值為value，返回原來key對應(yīng)的值，如果原來沒有，返回null    V replace(K key, V value);
}

Android培訓(xùn),安卓培訓(xùn),手機開發(fā)培訓(xùn),移動開發(fā)培訓(xùn),云培訓(xùn)培訓(xùn)

如果使用同步容器，調(diào)用方必須加鎖，而ConcurrentMap將它們實現(xiàn)為了原子操作。實際上，使用ConcurrentMap，調(diào)用方也沒有辦法進行加鎖，它沒有暴露鎖接口，也不使用synchronized。

高并發(fā)

ConcurrentHashMap是為高并發(fā)設(shè)計的，它是怎么做的呢？具體實現(xiàn)比較復(fù)雜，我們簡要介紹其思路，主要有兩點：

  • 分段鎖

  • 讀不需要鎖

同步容器使用synchronized，所有方法，競爭同一個鎖，而ConcurrentHashMap采用分段鎖技術(shù)，將數(shù)據(jù)分為多個段，而每個段有一個獨立的鎖，每一個段相當(dāng)于一個獨立的哈希表，分段的依據(jù)也是哈希值，無論是保存鍵值對還是根據(jù)鍵查找，都先根據(jù)鍵的哈希值映射到段，再在段對應(yīng)的哈希表上進行操作。

采用分段鎖，可以大大提高并發(fā)度，多個段之間可以并行讀寫。默認情況下，段是16個，不過，這個數(shù)字可以通過構(gòu)造方法進行設(shè)置，如下所示：

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)

concurrencyLevel表示估計的并行更新的線程個數(shù)，ConcurrentHashMap會將該數(shù)轉(zhuǎn)換為2的整數(shù)次冪，比如14轉(zhuǎn)換為16，25轉(zhuǎn)換為32。

在對每個段的數(shù)據(jù)進行讀寫時，ConcurrentHashMap也不是簡單的使用鎖進行同步，內(nèi)部使用了CAS、對一些寫采用原子方式，實現(xiàn)比較復(fù)雜，我們就不介紹了，實現(xiàn)的效果是，對于寫操作，需要獲取鎖，不能并行，但是讀操作可以，多個讀可以并行，寫的同時也可以讀，這使得ConcurrentHashMap的并行度遠遠大于同步容器。

迭代

我們在66節(jié)介紹過，使用同步容器，在迭代中需要加鎖，否則可能會拋出ConcurrentModificationException。ConcurrentHashMap沒有這個問題，在迭代器創(chuàng)建后，在迭代過程中，如果另一個線程對容器進行了修改，迭代會繼續(xù)，不會拋出異常。

問題是，迭代會反映別的線程的修改？還是像上節(jié)介紹的CopyOnWriteArrayList一樣，反映的是創(chuàng)建時的副本？答案是，都不是！我們看個例子：

Android培訓(xùn),安卓培訓(xùn),手機開發(fā)培訓(xùn),移動開發(fā)培訓(xùn),云培訓(xùn)培訓(xùn)

public class ConcurrentHashMapIteratorDemo {    public static void test() {        final ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
        map.put("a", "abstract");
        map.put("b", "basic");

        Thread t1 = new Thread() {
            @Override            public void run() {                for (Entry<String, String> entry : map.entrySet()) {                    try {
                        Thread.sleep(1000);
                    } catch (InterruptedException e) {
                    }
                    System.out.println(entry.getKey() + "," + entry.getValue());
                }
            }
        };
        t1.start();        // 確保線程t1啟動
        try {
            Thread.sleep(100);
        } catch (InterruptedException e) {
        }
        map.put("c", "call");
    }    public static void main(String[] args) {
        test();
    }
}

Android培訓(xùn),安卓培訓(xùn),手機開發(fā)培訓(xùn),移動開發(fā)培訓(xùn),云培訓(xùn)培訓(xùn)

t1啟動后，創(chuàng)建迭代器，但在迭代輸出每個元素前，先睡眠1秒鐘，主線程啟動t1后，先睡眠一下，確保t1先運行，然后給map增加了一個元素，程序輸出為：

a,abstract
b,basic
c,call

說明，迭代器反映了最新的更新，但我們將添加語句更改為：

map.put("g", "call");

你會發(fā)現(xiàn)，程序輸出為：

a,abstract
b,basic

這說明，迭代器沒有反映最新的更新，這是怎么回事呢？我們需要理解ConcurrentHashMap的弱一致性。

弱一致性

ConcurrentHashMap的迭代器創(chuàng)建后，就會按照哈希表結(jié)構(gòu)遍歷每個元素，但在遍歷過程中，內(nèi)部元素可能會發(fā)生變化，如果變化發(fā)生在已遍歷過的部分，迭代器就不會反映出來，而如果變化發(fā)生在未遍歷過的部分，迭代器就會發(fā)現(xiàn)并反映出來，這就是弱一致性。

類似的情況還會出現(xiàn)在ConcurrentHashMap的另一個方法：

//批量添加m中的鍵值對到當(dāng)前Mappublic void putAll(Map<? extends K, ? extends V> m)

該方法并非原子操作，而是調(diào)用put方法逐個元素進行添加的，在該方法沒有結(jié)束的時候，部分修改效果就會體現(xiàn)出來。

小結(jié)

本節(jié)介紹了ConcurrentHashMap，它是并發(fā)版的HashMap，通過分段鎖和其他技術(shù)實現(xiàn)了高并發(fā)，支持原子條件更新操作，不會拋出ConcurrentModificationException，實現(xiàn)了弱一致性。

Java中沒有并發(fā)版的HashSet，但可以通過Collections.newSetFromMap方法基于ConcurrentHashMap構(gòu)建一個。

我們知道HashMap/HashSet基于哈希，不能對元素排序，對應(yīng)的可排序的容器類是TreeMap/TreeSet，并發(fā)包中可排序的對應(yīng)版本不是基于樹，而是基于Skip List（跳躍表）的，類分別是ConcurrentSkipListMap和ConcurrentSkipListSet，它們到底是什么呢？

(與其他章節(jié)一樣，本節(jié)所有代碼位于 https://github.com/swiftma/program-logic)

----------------

未完待續(xù)，查看最新文章，敬請關(guān)注微信公眾號“老馬說編程”(掃描下方二維碼)，從入門到高級，深入淺出，老馬和你一起探索Java編程及計算機技術(shù)的本質(zhì)。用心原創(chuàng)，保留所有版權(quán)。

http://www.cnblogs.com/swiftma/p/6557685.html