5 Java并發(fā)集合

5.1 引言

在前幾章中，我們介紹了Java集合的內容币绩，具體包括ArrayList、HashSet缆镣、HashMap、ArrayQueue等實現(xiàn)類董瞻。

不知道各位有沒有發(fā)現(xiàn)田巴，上述集合都有一個共同的特點钠糊，那就是線程不安全性壹哺，在并發(fā)情況下都不能保證數(shù)據(jù)的一致性。（當然管宵，這個集合必須是共享了，所以才會有數(shù)據(jù)不一致）

所以箩朴，當我們在進行并發(fā)任務時候隧饼，共享了一個不適用于并發(fā)的數(shù)據(jù)結構，也就是將此數(shù)據(jù)結構變成了程序中的成員變量燕雁，那么我們將會遇到數(shù)據(jù)的不一致，進而影響到我們程序的運行僧免。

為了應對并發(fā)場景的出現(xiàn)，Java在后續(xù)迭代過程中（具體應該是JDK1.5版本）撞叨，推出了java.util.concurrent包浊洞。該包的出現(xiàn)，讓Java并發(fā)編程變得更加輕松枷餐，幫助開發(fā)者編寫更加高效苫亦、易維護、結構清晰的程序润匙。

在java.util.concurrent包中，不但包含了我們本篇要說的線程安全的集合孕讳，還涉及到了多線程肄鸽、CAS卫病、線程鎖等相關內容，可以說是完整覆蓋了Java并發(fā)的知識棧典徘。

對于Java開發(fā)人員來說蟀苛，學好java.util.concurrent包下的內容逮诲，是一個必備的功課帜平，也是逐漸提升自己的一個重要階段梅鹦。

5.2 并發(fā)集合實現(xiàn)1

JDK1.5的出現(xiàn)裆甩，對于集合并發(fā)編程來說，java developer有了更多的選擇齐唆。不過，在JDK1.5之前，Java也還是提供了一些解決方案茉帅。

（1）最為簡單直接的就是在程序中我們自己對共享變量進行加鎖叨叙。不過，缺點也顯而易見堪澎，手動實現(xiàn)線程安全間接增加了程序的復雜度擂错，以及代碼出錯的概率---例如：線程死鎖的產生樱蛤；

（2）我們還可以使用Java集合框架中的Vector钮呀、Hashtable實現(xiàn)類昨凡，這兩個類都是線程安全的。不過土匀，Java已不提倡使用就轧。

（3）此外妒御，我們還可以使用集合工具類--Collections，通過調用其中的靜態(tài)方法镇饺，來得到線程安全的集合奸笤。具體方法，包括：Collections.synchronizedCollection(Collection<T> c)监右、Collections.synchronizedSet(Set<T> s)边灭、Collections.synchronizedList(List<T>)、Collections.synchronizedMap(Map<K, V>)健盒。
究其原理绒瘦，他們都是通過在方法中加synchronized同步鎖來實現(xiàn)的。我們知道synchronized鎖的開銷較大扣癣，在程序中不建議使用惰帽。

雖然，這三種方式可以實現(xiàn)線程安全的集合父虑，但是都有顯而易見的缺點该酗，而且也不是我們今天所關注的重點。

接下來士嚎，就來具體看下java.util.concurrent包中的實現(xiàn)呜魄；

5.2 并發(fā)集合實現(xiàn)2

在java.util.concurrent包中烁焙，提供了兩種類型的并發(fā)集合：一種是阻塞式，另一種是非阻塞式耕赘。

阻塞式集合：當集合已滿或為空時骄蝇，被調用的添加（滿）、移除（空）方法就不能立即被執(zhí)行操骡，調用這個方法的線程將被阻塞九火，一直等到該方法可以被成功執(zhí)行。

非阻塞式集合：當集合已滿或為空時册招，被調用的添加（滿）岔激、移除（空）方法就不能立即被執(zhí)行，調用這個方法的線程不會被阻塞是掰，而是直接則返回null或拋出異常虑鼎。

下面，就來看下concurrent包下键痛，到底存在了哪些線程安全的集合：

Collection集合：

List：

CopyOnWriteArrayList

Set：

CopyOnWriteArraySet
ConcurrentSkipListSet

Queue：

BlockingQueue:
    LinkedBlockingQueue
    DelayQueue
    PriorityBlockingQueue
    ConcurrentLinkedQueue
    TransferQueue:
        LinkedTransferQueue
    BlockingDeque:
        LinkedBlockingDeque
        ConcurrentLinkedDeque

Map集合：

Map:

ConcurrentMap:
    ConcurrentHashMap
    ConcurrentSkipListMap
    ConcurrentNavigableMap

通過以上可以看出炫彩，java.util.concurrent包為每一類集合都提供了線程安全的實現(xiàn)。

接下來絮短，我們做具體分析江兢！

5.3 List并發(fā)集合（CopyOnWrite機制）

1. CopyOnWrite機制

CopyOnWrite（簡稱COW），是計算機程序設計領域中的一種優(yōu)化策略丁频，也是一種思想--即寫入時復制思想杉允。

那么，什么是寫入時復制思想呢席里？就是當有多個調用者同時去請求一個資源時(可以是內存中的一個數(shù)據(jù))叔磷，當其中一個調用者要對資源進行修改，系統(tǒng)會copy一個副本給該調用者奖磁，讓其進行修改改基；而其他調用者所擁有資源并不會由于該調用者對資源的改動而發(fā)生改變。這就是寫入時復制思想署穗；

如果用代碼來描述的話寥裂，就是創(chuàng)建多個線程，在每個線程中如果修改共享變量案疲，那么就將此變量進行一次拷貝操作封恰，每次的修改都是對副本進行。

代碼如下：

public class CopyOnWriteThread implements Runnable {

    private List<String> list = new ArrayList<String>();

    public void run() {
        List<String> newList = new ArrayList<String>();
        newList.add("hello");
        Collections.copy(newList,list);
        
    }
   
    //創(chuàng)建線程：
    public static void main(String[] agrs){
        Thread thread1 = new Thread(new CopyOnWriteThread());
        thread1.start();

        Thread thread2 = new Thread(new CopyOnWriteThread());
        thread2.start();
    }
}

從JDK1.5開始褐啡，java.util.concurrent包中提供了兩個CopyOnWrite機制容器诺舔，分別為CopyOnWriteArrayList和CopyOnWriteArraySet。

CopyOnWriteArrayList，直白翻譯過來就是“當寫入時復制ArrayList集合”低飒。

簡單的理解许昨，就是當我們往CopyOnWrite容器中添加元素時，不直接操作當前容器褥赊，而是先將容器進行Copy糕档，然后對Copy出的新容器進行修改，修改后拌喉，再將原容器的引用指向新的容器速那，即完成了整個修改操作；

2. CopyOnWriteArrayList的實現(xiàn)原理

CopyOnWriteArrayList尿背，線程安全的集合端仰，這一點主要區(qū)別與ArrayList。

通常來說田藐，線程安全都是通過加鎖實現(xiàn)的荔烧，那么CopyOnWriteArrayList是如何實現(xiàn)？

CopyOnWriteArrayList通過使用ReentrantLock鎖來實現(xiàn)線程安全：

public class CopyOnWriteArrayList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;

    //ReentrantLock鎖汽久，沒有使用Synchronized
    transient final ReentrantLock lock = new ReentrantLock();

    //集合底層數(shù)據(jù)結構：數(shù)組（volatile修飾共享可見）
    private volatile transient Object[] array;
}

CopyOnWriteArrayList在添加鹤竭、獲取元素時，使用getArray（）獲取底層數(shù)組對象回窘，獲取此時集合中的數(shù)組對象诺擅；使用setArray（）設置底層數(shù)組，將原有數(shù)組對象指針指向新的數(shù)組對象----實以此來實現(xiàn)CopyOnWrite副本概念：

//CopyOnWrite容器中重要方法：獲取底層數(shù)組啡直。
final Object[] getArray() {
    return array;
}

//CopyOnWrite容器中重要方法：設置底層數(shù)組
final void setArray(Object[] a) {
    array = a;
}

CopyOnWriteArrayList添加元素：在添加元素之前進行加鎖操作，保證數(shù)據(jù)的原子性苍碟。在添加過程中酒觅，進行數(shù)組復制，修改操作微峰，再將新生成的數(shù)組復制給集合中的array屬性舷丹。最后，釋放鎖蜓肆；

由于array屬性被volatile修飾颜凯，所以當添加完成后，其他線程就可以立刻查看到被修改的內容仗扬。

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    //加鎖：
    lock.lock();
    try {
        //獲取集合中的數(shù)組：
        Object[] elements = getArray();
        int len = elements.length;
        
        //數(shù)組復制：將此線程與其他線程對集合的操作區(qū)分開來症概，無論底層結構如何改變，本線程中的數(shù)據(jù)不受影響
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        
        //對新的數(shù)組進行操作：
        newElements[len] = e;

        //將原有數(shù)組指針指向新的數(shù)組對象：
        setArray(newElements);
        return true;
    } finally {
        //釋放鎖：
        lock.unlock();
    }
}

CopyOnWriteArrayList獲取元素：在獲取元素時早芭，由于array屬性被volatile修飾彼城，所以每當獲取線程執(zhí)行時，都會拿到最新的數(shù)據(jù)。此外募壕，添加線程在進行添加元素時调炬，會將新的數(shù)組賦值給array屬性，所以在獲取線程中并不會因為元素的添加而導致本線程的執(zhí)行異常舱馅。因為獲取線程中的array和被添加后的array指向了不同的內存區(qū)域缰泡。

//根據(jù)角標，獲取對應的數(shù)組元素:
public E get(int index) {
    return get(getArray(), index);
}
@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
    return (E) a[index];
}

看到這代嗤，不知道你是不是跟我一樣棘钞，突然有個疑惑，在add（）方法時已經(jīng)加了鎖资溃，為什么還要進行數(shù)組復制呢武翎，難道不是多此一舉嗎？

其實不然溶锭，為了能讓get（）方法得到最大的性能宝恶，CopyOnWriteArrayList并沒有進行加鎖處理，而且也不需要加鎖處理趴捅。

因為垫毙，在add（）時候加了鎖，首先不會有多個線程同時進到add中去拱绑，這一點保證了數(shù)組的安全综芥。當在一個線程執(zhí)行add時，又進行了數(shù)組的復制操作猎拨，生成了一個新的數(shù)組對象膀藐，在add后又將新數(shù)組對象的指針指向了舊的數(shù)組對象指針，注意此時是指針的替換红省，原來舊的數(shù)組對象還存在额各。這樣就實現(xiàn)了，添加方法無論如何操作數(shù)組對象吧恃，獲取方法在獲取到集合后虾啦，都不會受到其他線程添加元素的影響。

這也就是在執(zhí)行add()時痕寓，為什么還要在加鎖的同時又copy了一分新的數(shù)組對象０磷怼！呻率！

模擬CopyOnWriteArrayList：

public class CopyOnWriteThread{

    private static CopyOnWriteTestList copyOnWriteTestList = new CopyOnWriteTestList();

    static class CopyOnWriteTestList{
        private Object[] array;

        public CopyOnWriteTestList(){
            this.array=new Object[0];
        }
        //獲取底層數(shù)組：
        public Object[] getArray(){
            return array;
        }
        //設置底層數(shù)組：
        public void setArray(Object[] array) {
            this.array = array;
        }

        //添加元素：
        public void add(String element){
            int len = array.length;
            Object[] newElements = Arrays.copyOf(array, len + 1);
            newElements[len] = element;
            setArray(newElements);
        }

        public void get(int index){
            Object[] array = getArray();
            get(array,index);
        }
        //此步驟硬毕，就是為了驗證在獲取元素時，array是否會隨著元素的添加而改變筷凤；
        public void get(Object[] array,int index){
            for(;;){
                System.out.println("獲取方法："+array.length);
            }
        }
    }
    //創(chuàng)建線程：
    public static void main(String[] agrs) throws InterruptedException {
        //啟動異步線程昭殉，一直添加元素
        new ThreadPoolExecutor(10,10,10, TimeUnit.MINUTES,
                new ArrayBlockingQueue(11),
                new ThreadPoolExecutor.AbortPolicy()).execute(new Runnable() {
            public void run() {
                for(;;){
                    int x=0;;
                    copyOnWriteTestList.add("jiaboyan"+x);
                    ++x;
                }
            }
        });
        Thread.sleep(1000);
        System.out.println(copyOnWriteTestList.getArray().length);
        //啟動線程：獲取元素
        new Runnable() {
            public void run() {
                copyOnWriteTestList.get(0);
            }
        }.run();
    }
}

3. CopyOnWrite機制的優(yōu)缺點

CopyOnWriteArrayList保證了數(shù)據(jù)在多線程操作時的最終一致性苞七。

缺點也同樣顯著，那就是內存空間的浪費：因為在寫操作時挪丢，進行數(shù)組復制蹂风，在內存中產生了兩份相同的數(shù)組。如果數(shù)組對象比較大乾蓬，那么就會造成頻繁的GC操作惠啄，進而影響到系統(tǒng)的性能；

剛才說了任内，CopyOnWriteArrayList只能保證最終的數(shù)據(jù)一致性撵渡，而不能保證實時的數(shù)據(jù)一致性。這一點也是我們在使用的過程中死嗦，必須要考慮到的因素趋距。

仔細思考下，其實CopyOnWrite容器也是一種讀寫分離越除，讀和寫是不同的容器节腐。