在單線程開發環境中，我們經常使用ArrayList作容器來存儲我們的數據，但它不是線程安全的，在多線程環境中使用它可能會出現意想不到的結果。

多線程中的ArrayList：

我們可以從一段代碼了解并發環境下使用ArrayList的情況：

public class ConcurrentArrayList {
    public static void main(String[] args) throws InterruptedException {
        List<Integer> list = new ArrayList<>();

        Runnable runnable = () -> {
            for (int i = 0; i < 10000; i++) {
                list.add(i);
            }
        };
        
        for (int i = 0; i < 2; i++) {
            new Thread(runnable).start();
        }
        
        Thread.sleep(500);
        System.out.println(list.size());
    }
}
123456789101112131415161718

代碼中循環創建了兩個線程，這兩個線程都執行10000次數組的添加操作，理論上最后輸出的結果應該為20000，但經過多次嘗試，最后只出現了兩種結果：

1. 數組索引越界異常

Exception in thread "Thread-0" java.lang.ArrayIndexOutOfBoundsException: 10
	at java.util.ArrayList.add(ArrayList.java:463)
	at ConcurrentArrayList.lambda$main$0(ConcurrentArrayList.java:14)
	at java.lang.Thread.run(Thread.java:748)
10007
12345

2. 輸出結果小于20000

16093
1

雖然仍有可能得到20000的結果，但概率非常低。我們要從ArrayList的源碼中去分析為什么會出現這種結果。
ArrayList數組默認初始化大小：

// 默認初始大小
private static final int DEFAULT_CAPACITY = 10;
...
// 數組size
private int size;
12345

ArrayList的add方法：

public boolean add(E e) {
    //確定集合的大小是否足夠，如果不夠則會進行擴容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
1234567

以上面錯誤1：ArrayIndexOutOfBoundsException: 10為例，出現錯誤的步驟如下：

1. 假設某時刻Thread-0和Thread-1都執行到了elementData[size++] = e; 這步，獲取的size大小都為9，此時輪到Thread-1執行
2. Thread-1執行elementData[9] = e，空間剛剛好夠用，賦值完后size變為10。接著輪到Thread-0執行
3. 因為Thread-0已經跳過了ensureCapacityInternal(size + 1); 這步判斷容量的檢查步驟，因此它執行elementData[10] = e，而數組容量剛好為10！此時就出現了數組越界的錯誤。

另外，size++本身就是非原子性的，多個線程之間訪問沖突，這時兩個線程可能對同一個位置賦值，這就出現了出現size小于期望值的錯誤2結果。

線程安全的List

目前比較常用的構建線程安全的List有三種方法：

1. 使用Vector容器
2. 使用Collections的靜態方法synchronizedList(List< T> list)
3. 采用CopyOnWriteArrayList容器

1.使用Vector容器

Vector類實現了可擴展的對象數組，并且它是線程安全的。它和ArrayList在常用方法的實現上很相似，不同的只是它采用了同步關鍵詞synchronized修飾方法。
ArrayList中的add方法：

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
123456789

Vector中的add方法：

public void add(int index, E element) {
    insertElementAt(element, index);
}
...
// 使用了synchronized關鍵詞修飾
public synchronized void insertElementAt(E obj, int index) {
        modCount++;
        if (index > elementCount) {
            throw new ArrayIndexOutOfBoundsException(index
                                                     + " > " + elementCount);
        }
        ensureCapacityHelper(elementCount + 1);
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        elementData[index] = obj;
        elementCount++;
    }
12345678910111213141516

可以看出，Vector在通用方法的實現上ArrayList并沒有什么區別（這里不比較擴容方式等細節）

2. Collections.synchronizedList(List< T> list)

使用這種方法我們可以獲得線程安全的List容器，它和Vector的區別在于它采用了同步代碼塊實現線程間的同步。通過分析源碼，它的底層使用了新的容器包裝原始的List。
下圖是新容器的繼承關系圖：

synchronizedList方法：

public static <T> List<T> synchronizedList(List<T> list) {
        return (list instanceof RandomAccess ?
                new SynchronizedRandomAccessList<>(list) :
                new SynchronizedList<>(list));
    }
12345

因為ArrayList實現了RandomAccess接口，因此該方法返回一個SynchronizedRandomAccessList實例。
該類的add實現：

public void add(int index, E element) {
    synchronized (mutex) {list.add(index, element);}
}
123

其中，mutex是final修飾的一個對象：

final Object mutex;
1

我們可以看到，這種線程安全容器是通過同步代碼塊來實現的，基礎的add方法任然是由ArrayList實現。

我們再來看看它的讀方法：

public E get(int index) {
    synchronized (mutex) {return list.get(index);}
}
123

和寫方法沒什么區別，同樣是使用了同步代碼塊。線程同步的實現原理非常簡單！

通過上面的分析可以看出，無論是讀操作還是寫操作，它都會進行加鎖，當線程的并發級別非常高時就會浪費掉大量的資源，因此某些情況下它并不是一個好的選擇。針對這個問題，我們引出第三種線程安全容器的實現。

3. CopyOnWriteArrayList

顧名思義，它的意思就是在寫操作的時候復制數組。為了將讀取的性能發揮到極致，在該類的使用過程中，讀讀操作和讀寫操作都不互斥，這是一個很神奇的操作，接下來我們看看它如何實現。

    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);
            // 賦值
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }
12345678910111213141516

從CopyOnWriteArrayList的add實現方式可以看出它是通過lock來實現線程間的同步的，這是一個標準的lock寫法。那么它是怎么做到讀寫互斥的呢？

// 復制數組
Object[] newElements = Arrays.copyOf(elements, len + 1);
// 賦值
newElements[len] = e;
1234

真實實現讀寫互斥的細節就在這兩行代碼上。在面臨寫操作的時候，CopyOnWriteArrayList會先復制原來的數組并且在新數組上進行修改，最后再將原數組覆蓋。如果寫操作的過程中發生了線程切換，并且切換到讀線程，因為此時數組并未發生覆蓋，讀操作讀取的還是原數組。

換句話說，就是讀操作和寫操作位于不同的數組上，因此它們不會發生安全問題。

另外，數組定義private transient volatile Object[] array，其中采用volatile修飾，保證內存可見性，讀取線程可以馬上知道這個修改。

private transient volatile Object[] array;
1

三種方式的性能比較

1. 首先我們來看看三種方式在寫操作的情況：

public class ConcurrentList {
    public static void main(String[] args) {
        testVector();
        testSynchronizedList();
        testCopyOnWriteArrayList();
    }

    public static void testVector(){
        Vector vector = new Vector();
        long time1 = System.currentTimeMillis();
        for (int i = 0; i < 10000000; i++) {
            vector.add(i);
        }
        long time2 = System.currentTimeMillis();
        System.out.println("vector: "+(time2-time1));
    }

    public static void testSynchronizedList(){
        List<Integer> list = Collections.synchronizedList(new ArrayList<Integer>());
        long time1 = System.currentTimeMillis();
        for (int i = 0; i < 10000000; i++) {
            list.add(i);
        }
        long time2 = System.currentTimeMillis();
        System.out.println("synchronizedList: "+(time2-time1));
    }

    public static void testCopyOnWriteArrayList(){
        CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
        long time1 = System.currentTimeMillis();
        for (int i = 0; i < 100000; i++) {
            list.add(i);
        }
        long time2 = System.currentTimeMillis();
        System.out.println("copyOnWriteArrayList: "+(time2-time1));
    }
}
12345678910111213141516171819202122232425262728293031323334353637

在代碼中我讓Vector和SynchronizedList兩種實現方式進行寫操作10000000次，而CopyOnWriteArrayList僅僅只有100000次，與前兩種方式少了100倍！
而結果卻出乎意料：

vector: 3202
synchronizedList: 1795
copyOnWriteArrayList: 8159
123

第三種方式使用的時間遠大于前兩種，寫操作越多，時間差就越明顯。

看似出乎意料，實則意料之中，copyOnWriteArrayList每進行一次寫操作都會復制一次數組，這是非常耗時的操作，因此在面臨巨大的寫操作量時才會差異這么大。

不過前兩種方式之間為什么差異也很明顯？可能因為同步代碼塊比同步方法效率更高？但是同步代碼塊是直接包含ArrayList的add方法，理論上兩種同步方式應該差異不大，歡迎大佬指點。

我們再來看看三種方式在讀操作的情況：

2. 我們再來看看三種方式在讀操作的情況：

public class ConcurrentList {
    public static void main(String[] args) {
        testVector();
        testSynchronizedList();
        testCopyOnWriteArrayList();
    }

    public static void testVector(){
        Vector<Integer> vector = new Vector<>();
        vector.add(0);
        long time1 = System.currentTimeMillis();
        for (int i = 0; i < 10000000; i++) {
            vector.get(0);
        }
        long time2 = System.currentTimeMillis();
        System.out.println("vector: "+(time2-time1));
    }

    public static void testSynchronizedList(){
        List<Integer> list = Collections.synchronizedList(new ArrayList<Integer>());
        list.add(0);
        long time1 = System.currentTimeMillis();
        for (int i = 0; i < 10000000; i++) {
            list.get(0);
        }
        long time2 = System.currentTimeMillis();
        System.out.println("synchronizedList: "+(time2-time1));
    }

    public static void testCopyOnWriteArrayList(){
        CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
        list.add(0);
        long time1 = System.currentTimeMillis();
        for (int i = 0; i < 10000000; i++) {
            list.get(0);
        }
        long time2 = System.currentTimeMillis();
        System.out.println("copyOnWriteArrayList: "+(time2-time1));
    }
}
12345678910111213141516171819202122232425262728293031323334353637383940

這一次三種方式都進行了10000000次讀操作，結果如下：

vector: 217
synchronizedList: 224
copyOnWriteArrayList: 12
123

這次copyOnWriteArrayList的優勢就顯示出來了，它的讀操作沒有實現同步，因此加快了多線程的讀操作。其他兩種方式的差別不大。

總結

1. 獲取線程安全的List我們可以通過Vector、Collections.synchronizedList()方法和CopyOnWriteArrayList三種方式
2. 讀多寫少的情況下，推薦使用CopyOnWriteArrayList方式
3. 讀少寫多的情況下，推薦使用Collections.synchronizedList()的方式

參考：

1. 并發容器(二)—線程安全的List
2. SynchronizedList和Vector的區別