摘要：線程安全的線程安全的，在讀多寫少的場合性能非常好，遠(yuǎn)遠(yuǎn)好于高效的并發(fā)隊列，使用鏈表實現(xiàn)。這樣帶來的好處是在高并發(fā)的情況下，你會需要一個全局鎖來保證整個平衡樹的線程安全。

該文已加入開源項目：JavaGuide（一份涵蓋大部分Java程序員所需要掌握的核心知識的文檔類項目，Star 數(shù)接近 14 k）。地址:https://github.com/Snailclimb...

實戰(zhàn)Java高并發(fā)程序設(shè)計》為我們總結(jié)了下面幾種大家可能會在高并發(fā)程序設(shè)計中經(jīng)常遇到和使用的 JDK 為我們提供的并發(fā)容器。先帶大家概覽一下，下面會一一介紹到。

JDK提供的這些容器大部分在 java.util.concurrent 包中。

ConcurrentHashMap： 線程安全的HashMap

CopyOnWriteArrayList: 線程安全的List，在讀多寫少的場合性能非常好，遠(yuǎn)遠(yuǎn)好于Vector.

ConcurrentLinkedQueue：高效的并發(fā)隊列，使用鏈表實現(xiàn)?？梢钥醋鲆粋€線程安全的 LinkedList，這是一個非阻塞隊列。

BlockingQueue: 這是一個接口，JDK內(nèi)部通過鏈表、數(shù)組等方式實現(xiàn)了這個接口。表示阻塞隊列，非常適合用于作為數(shù)據(jù)共享的通道。

ConcurrentSkipListMap: 跳表的實現(xiàn)。這是一個Map，使用跳表的數(shù)據(jù)結(jié)構(gòu)進行快速查找。

我們知道 HashMap 不是線程安全的，在并發(fā)場景下如果要保證一種可行的方式是使用 Collections.synchronizedMap() 方法來包裝我們的 HashMap。但這是通過使用一個全局的鎖來同步不同線程間的并發(fā)訪問，因此會帶來不可忽視的性能問題。

所以就有了 HashMap 的線程安全版本—— ConcurrentHashMap 的誕生。在ConcurrentHashMap中，無論是讀操作還是寫操作都能保證很高的性能：在進行讀操作時(幾乎)不需要加鎖，而在寫操作時通過鎖分段技術(shù)只對所操作的段加鎖而不影響客戶端對其它段的訪問。

關(guān)于 ConcurrentHashMap 相關(guān)問題，我在 《這幾道Java集合框架面試題幾乎必問》 這篇文章中已經(jīng)提到過。下面梳理一下關(guān)于 ConcurrentHashMap 比較重要的問題：

ConcurrentHashMap 和 Hashtable 的區(qū)別

ConcurrentHashMap線程安全的具體實現(xiàn)方式/底層具體實現(xiàn)

public class CopyOnWriteArrayList
extends Object
implements List, RandomAccess, Cloneable, Serializable

在很多應(yīng)用場景中，讀操作可能會遠(yuǎn)遠(yuǎn)大于寫操作。由于讀操作根本不會修改原有的數(shù)據(jù)，因此對于每次讀取都進行加鎖其實是一種資源浪費。我們應(yīng)該允許多個線程同時訪問List的內(nèi)部數(shù)據(jù)，畢竟讀取操作是安全的。

這和我們之前在多線程章節(jié)講過 ReentrantReadWriteLock 讀寫鎖的思想非常類似，也就是讀讀共享、寫寫互斥、讀寫互斥、寫讀互斥。JDK中提供了 CopyOnWriteArravList 類比相比于在讀寫鎖的思想又更進一步。為了將讀取的性能發(fā)揮到極致，CopyOnWriteArravList 讀取是完全不用加鎖的，并且更厲害的是：寫入也不會阻塞讀取操作。只有寫入和寫入之間需要進行同步等待。這樣一來，讀操作的性能就會大幅度提升。那它是怎么做的呢？

CopyOnWriteArravList 類的所有可變操作（add，set等等）都是通過創(chuàng)建底層數(shù)組的新副本來實現(xiàn)的。當(dāng) List 需要被修改的時候，我并不修改原有內(nèi)容，而是對原有數(shù)據(jù)進行一次復(fù)制，將修改的內(nèi)容寫入副本。寫完之后，再將修改完的副本替換原來的數(shù)據(jù)，這樣就可以保證寫操作不會影響讀操作了。

從 CopyOnWriteArravList 的名字就能看出CopyOnWriteArravList 是滿足CopyOnWrite 的ArrayList，所謂CopyOnWrite 也就是說：在計算機，如果你想要對一塊內(nèi)存進行修改時，我們不在原有內(nèi)存塊中進行寫操作，而是將內(nèi)存拷貝一份，在新的內(nèi)存中進行寫操作，寫完之后呢，就將指向原來內(nèi)存指針指向新的內(nèi)存，原來的內(nèi)存就可以被回收掉了。

讀取操作沒有任何同步控制和鎖操作，理由就是內(nèi)部數(shù)組 array 不會發(fā)生修改，只會被另外一個 array 替換，因此可以保證數(shù)據(jù)安全。

    /** The array, accessed only via getArray/setArray. */
    private transient volatile Object[] array;
    public E get(int index) {
        return get(getArray(), index);
    }
    @SuppressWarnings("unchecked")
    private E get(Object[] a, int index) {
        return (E) a[index];
    }
    final Object[] getArray() {
        return array;
    }

CopyOnWriteArravList 寫入操作 add() 方法在添加集合的時候加了鎖，保證了同步，避免了多線程寫的時候會 copy 出多個副本出來。

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();//加鎖
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);//拷貝新數(shù)組
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();//釋放鎖
        }
    }

Java提供的線程安全的 Queue 可以分為阻塞隊列和非阻塞隊列，其中阻塞隊列的典型例子是 BlockingQueue，非阻塞隊列的典型例子是ConcurrentLinkedQueue，在實際應(yīng)用中要根據(jù)實際需要選用阻塞隊列或者非阻塞隊列。 阻塞隊列可以通過加鎖來實現(xiàn)，非阻塞隊列可以通過 CAS 操作實現(xiàn)。

從名字可以看出，ConcurrentLinkedQueue這個隊列使用鏈表作為其數(shù)據(jù)結(jié)構(gòu)．ConcurrentLinkedQueue 應(yīng)該算是在高并發(fā)環(huán)境中性能最好的隊列了。它之所有能有很好的性能，是因為其內(nèi)部復(fù)雜的實現(xiàn)。

ConcurrentLinkedQueue 內(nèi)部代碼我們就不分析了，大家知道ConcurrentLinkedQueue 主要使用 CAS 非阻塞算法來實現(xiàn)線程安全就好了。

ConcurrentLinkedQueue 適合在對性能要求相對較高，同時對隊列的讀寫存在多個線程同時進行的場景，即如果對隊列加鎖的成本較高則適合使用無鎖的ConcurrentLinkedQueue來替代。

上面我們己經(jīng)提到了 ConcurrentLinkedQueue 作為高性能的非阻塞隊列。下面我們要講到的是阻塞隊列——BlockingQueue。阻塞隊列（BlockingQueue）被廣泛使用在“生產(chǎn)者-消費者”問題中，其原因是BlockingQueue提供了可阻塞的插入和移除的方法。當(dāng)隊列容器已滿，生產(chǎn)者線程會被阻塞，直到隊列未滿；當(dāng)隊列容器為空時，消費者線程會被阻塞，直至隊列非空時為止。

BlockingQueue 是一個接口，繼承自 Queue，所以其實現(xiàn)類也可以作為 Queue 的實現(xiàn)來使用，而 Queue 又繼承自 Collection 接口。下面是 BlockingQueue 的相關(guān)實現(xiàn)類：

下面主要介紹一下:ArrayBlockingQueue、LinkedBlockingQueue、PriorityBlockingQueue，這三個 BlockingQueue 的實現(xiàn)類。

ArrayBlockingQueue 是 BlockingQueue 接口的有界隊列實現(xiàn)類，底層采用數(shù)組來實現(xiàn)。ArrayBlockingQueue一旦創(chuàng)建，容量不能改變。其并發(fā)控制采用可重入鎖來控制，不管是插入操作還是讀取操作，都需要獲取到鎖才能進行操作。當(dāng)隊列容量滿時，嘗試將元素放入隊列將導(dǎo)致操作阻塞;嘗試從一個空隊列中取一個元素也會同樣阻塞。

ArrayBlockingQueue 默認(rèn)情況下不能保證線程訪問隊列的公平性，所謂公平性是指嚴(yán)格按照線程等待的絕對時間順序，即最先等待的線程能夠最先訪問到 ArrayBlockingQueue。而非公平性則是指訪問 ArrayBlockingQueue 的順序不是遵守嚴(yán)格的時間順序，有可能存在，當(dāng) ArrayBlockingQueue 可以被訪問時，長時間阻塞的線程依然無法訪問到 ArrayBlockingQueue。如果保證公平性，通常會降低吞吐量。如果需要獲得公平性的 ArrayBlockingQueue，可采用如下代碼：

private static ArrayBlockingQueue blockingQueue = new ArrayBlockingQueue(10,true);

LinkedBlockingQueue 底層基于單向鏈表實現(xiàn)的阻塞隊列，可以當(dāng)做無界隊列也可以當(dāng)做有界隊列來使用，同樣滿足FIFO的特性，與ArrayBlockingQueue 相比起來具有更高的吞吐量，為了防止 LinkedBlockingQueue 容量迅速增，損耗大量內(nèi)存。通常在創(chuàng)建LinkedBlockingQueue 對象時，會指定其大小，如果未指定，容量等于Integer.MAX_VALUE。

相關(guān)構(gòu)造方法:

    /**
     *某種意義上的無界隊列
     * Creates a {@code LinkedBlockingQueue} with a capacity of
     * {@link Integer#MAX_VALUE}.
     */
    public LinkedBlockingQueue() {
        this(Integer.MAX_VALUE);
    }

    /**
     *有界隊列
     * Creates a {@code LinkedBlockingQueue} with the given (fixed) capacity.
     *
     * @param capacity the capacity of this queue
     * @throws IllegalArgumentException if {@code capacity} is not greater
     *         than zero
     */
    public LinkedBlockingQueue(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException();
        this.capacity = capacity;
        last = head = new Node(null);
    }

PriorityBlockingQueue 是一個支持優(yōu)先級的無界阻塞隊列。默認(rèn)情況下元素采用自然順序進行排序，也可以通過自定義類實現(xiàn) compareTo() 方法來指定元素排序規(guī)則，或者初始化時通過構(gòu)造器參數(shù) Comparator 來指定排序規(guī)則。

PriorityBlockingQueue 并發(fā)控制采用的是 ReentrantLock，隊列為無界隊列（ArrayBlockingQueue 是有界隊列，LinkedBlockingQueue 也可以通過在構(gòu)造函數(shù)中傳入 capacity 指定隊列最大的容量，但是 PriorityBlockingQueue 只能指定初始的隊列大小，后面插入元素的時候，如果空間不夠的話會自動擴容）。

簡單地說，它就是 PriorityQueue 的線程安全版本。不可以插入 null 值，同時，插入隊列的對象必須是可比較大小的（comparable），否則報 ClassCastException 異常。它的插入操作 put 方法不會 block，因為它是無界隊列（take 方法在隊列為空的時候會阻塞）。

推薦文章：

《解讀 Java 并發(fā)隊列 BlockingQueue》

https://javadoop.com/post/java-concurrent-queue

下面這部分內(nèi)容參考了極客時間專欄《數(shù)據(jù)結(jié)構(gòu)與算法之美》以及《實戰(zhàn)Java高并發(fā)程序設(shè)計》。

為了引出ConcurrentSkipListMap，先帶著大家簡單理解一下跳表。

對于一個單鏈表，即使鏈表是有序的，如果我們想要在其中查找某個數(shù)據(jù)，也只能從頭到尾遍歷鏈表，這樣效率自然就會很低，跳表就不一樣了。跳表是一種可以用來快速查找的數(shù)據(jù)結(jié)構(gòu)，有點類似于平衡樹。它們都可以對元素進行快速的查找。但一個重要的區(qū)別是：對平衡樹的插入和刪除往往很可能導(dǎo)致平衡樹進行一次全局的調(diào)整。而對跳表的插入和刪除只需要對整個數(shù)據(jù)結(jié)構(gòu)的局部進行操作即可。這樣帶來的好處是：在高并發(fā)的情況下，你會需要一個全局鎖來保證整個平衡樹的線程安全。而對于跳表，你只需要部分鎖即可。這樣，在高并發(fā)環(huán)境下，你就可以擁有更好的性能。而就查詢的性能而言，跳表的時間復(fù)雜度也是 O(logn) 所以在并發(fā)數(shù)據(jù)結(jié)構(gòu)中，JDK 使用跳表來實現(xiàn)一個 Map。

跳表的本質(zhì)是同時維護了多個鏈表，并且鏈表是分層的，

最低層的鏈表維護了跳表內(nèi)所有的元素，每上面一層鏈表都是下面一層的了集。

跳表內(nèi)的所有鏈表的元素都是排序的。查找時，可以從頂級鏈表開始找。一旦發(fā)現(xiàn)被查找的元素大于當(dāng)前鏈表中的取值，就會轉(zhuǎn)入下一層鏈表繼續(xù)找。這也就是說在查找過程中，搜索是跳躍式的。如上圖所示，在跳表中查找元素18。

查找18 的時候原來需要遍歷 18 次，現(xiàn)在只需要 7 次即可。針對鏈表長度比較大的時候，構(gòu)建索引查找效率的提升就會非常明顯。

從上面很容易看出，跳表是一種利用空間換時間的算法。

使用跳表實現(xiàn)Map 和使用哈希算法實現(xiàn)Map的另外一個不同之處是：哈希并不會保存元素的順序，而跳表內(nèi)所有的元素都是排序的。因此在對跳表進行遍歷時，你會得到一個有序的結(jié)果。所以，如果你的應(yīng)用需要有序性，那么跳表就是你不二的選擇。JDK 中實現(xiàn)這一數(shù)據(jù)結(jié)構(gòu)的類是ConcurrentSkipListMap。

《實戰(zhàn)Java高并發(fā)程序設(shè)計》

https://javadoop.com/post/jav...

https://juejin.im/post/5aeebd...

ThoughtWorks準(zhǔn)入職Java工程師。專注Java知識分享！開源 Java 學(xué)習(xí)指南——JavaGuide（12k+ Star）的作者。公眾號多篇文章被各大技術(shù)社區(qū)轉(zhuǎn)載。公眾號后臺回復(fù)關(guān)鍵字“1”可以領(lǐng)取一份我精選的Java資源哦！