1、CopyOnWriteArrayList 有什么特點(diǎn)？

其實(shí)在 CopyOnWriteArrayList 出現(xiàn)之前，已經(jīng)有了 ArrayList 和 LinkedList 作為 List 的數(shù)組和鏈表的實(shí)現(xiàn)，而且也有了線(xiàn)程安全的 Vector 和 Collections.synchronizedList() 可以使用。

先來(lái)看下線(xiàn)程安全的 Vector 的 size 和 get 方法的代碼：

public synchronized int size() {
    return elementCount;
}
public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

可以看出，Vector 內(nèi)部是使用 synchronized 來(lái)保證線(xiàn)程安全的，并且鎖的粒度比較大，都是方法級(jí)別的鎖，在并發(fā)量高的時(shí)候，很容易發(fā)生競(jìng)爭(zhēng)，并發(fā)效率相對(duì)比較低。在這一點(diǎn)上，Vector 和 Hashtable 很類(lèi)似。

并且，前面這幾種 List 在迭代期間不允許編輯，如果在迭代期間進(jìn)行添加或刪除元素等操作，則會(huì)拋出 ConcurrentModificationException 異常，這樣的特點(diǎn)也在很多情況下給使用者帶來(lái)了麻煩。

所以從 JDK1.5 開(kāi)始，Java 并發(fā)包里提供了使用 CopyOnWrite 機(jī)制實(shí)現(xiàn)的并發(fā)容器 CopyOnWriteArrayList 作為主要的并發(fā) List，CopyOnWrite 的并發(fā)集合還包括 CopyOnWriteArraySet，其底層正是利用 CopyOnWriteArrayList 實(shí)現(xiàn)的。所以以 CopyOnWriteArrayList 為突破口，來(lái)看一下 CopyOnWrite 容器的特點(diǎn)。

適用場(chǎng)景

• 讀操作可以盡可能的快，而寫(xiě)即使慢一些也沒(méi)關(guān)系

在很多應(yīng)用場(chǎng)景中，讀操作可能會(huì)遠(yuǎn)遠(yuǎn)多于寫(xiě)操作。比如，有些系統(tǒng)級(jí)別的信息，往往只需要加載或者修改很少的次數(shù)，但是會(huì)被系統(tǒng)內(nèi)所有模塊頻繁的訪(fǎng)問(wèn)。對(duì)于這種場(chǎng)景，最希望看到的就是讀操作可以盡可能的快，而寫(xiě)即使慢一些也沒(méi)關(guān)系。

• 讀多寫(xiě)少

黑名單是最典型的場(chǎng)景，假如有一個(gè)搜索網(wǎng)站，用戶(hù)在這個(gè)網(wǎng)站的搜索框中，輸入關(guān)鍵字搜索內(nèi)容，但是某些關(guān)鍵字不允許被搜索。這些不能被搜索的關(guān)鍵字會(huì)被放在一個(gè)黑名單中，黑名單并不需要實(shí)時(shí)更新，可能每天晚上更新一次就可以了。當(dāng)用戶(hù)搜索時(shí)，會(huì)檢查當(dāng)前關(guān)鍵字在不在黑名單中，如果在，則提示不能搜索。這種讀多寫(xiě)少的場(chǎng)景也很適合使用 CopyOnWrite 集合。

讀寫(xiě)規(guī)則

• 讀寫(xiě)鎖的規(guī)則

讀寫(xiě)鎖的思想是：讀讀共享、其他都互斥（寫(xiě)寫(xiě)互斥、讀寫(xiě)互斥、寫(xiě)讀互斥），原因是由于讀操作不會(huì)修改原有的數(shù)據(jù)，因此并發(fā)讀并不會(huì)有安全問(wèn)題；而寫(xiě)操作是危險(xiǎn)的，所以當(dāng)寫(xiě)操作發(fā)生時(shí)，不允許有讀操作加入，也不允許第二個(gè)寫(xiě)線(xiàn)程加入。

• 對(duì)讀寫(xiě)鎖規(guī)則的升級(jí)

CopyOnWriteArrayList 的思想比讀寫(xiě)鎖的思想又更進(jìn)一步。為了將讀取的性能發(fā)揮到極致，CopyOnWriteArrayList 讀取是完全不用加鎖的，更厲害的是，寫(xiě)入也不會(huì)阻塞讀取操作，也就是說(shuō)可以在寫(xiě)入的同時(shí)進(jìn)行讀取，只有寫(xiě)入和寫(xiě)入之間需要進(jìn)行同步，也就是不允許多個(gè)寫(xiě)入同時(shí)發(fā)生，但是在寫(xiě)入發(fā)生時(shí)允許讀取同時(shí)發(fā)生。這樣一來(lái)，讀操作的性能就會(huì)大幅度提升。

特點(diǎn)

• CopyOnWrite的含義

從 CopyOnWriteArrayList 的名字就能看出它是滿(mǎn)足 CopyOnWrite 的 ArrayList，CopyOnWrite 的意思是說(shuō)，當(dāng)容器需要被修改的時(shí)候，不直接修改當(dāng)前容器，而是先將當(dāng)前容器進(jìn)行 Copy，復(fù)制出一個(gè)新的容器，然后修改新的容器，完成修改之后，再將原容器的引用指向新的容器。這樣就完成了整個(gè)修改過(guò)程。

這樣做的好處是，CopyOnWriteArrayList 利用了“不變性”原理，因?yàn)槿萜髅看涡薷亩际莿?chuàng)建新副本，所以對(duì)于舊容器來(lái)說(shuō)，其實(shí)是不可變的，也是線(xiàn)程安全的，無(wú)需進(jìn)一步的同步操作。可以對(duì) CopyOnWrite 容器進(jìn)行并發(fā)的讀，而不需要加鎖，因?yàn)楫?dāng)前容器不會(huì)添加任何元素，也不會(huì)有修改。

CopyOnWriteArrayList 的所有修改操作（add，set等）都是通過(guò)創(chuàng)建底層數(shù)組的新副本來(lái)實(shí)現(xiàn)的，所以 CopyOnWrite 容器也是一種讀寫(xiě)分離的思想體現(xiàn)，讀和寫(xiě)使用不同的容器。

• 迭代期間允許修改集合內(nèi)容

ArrayList 在迭代期間如果修改集合的內(nèi)容，會(huì)拋出 ConcurrentModificationException 異常。

在 ArrayList 源碼里的 ListItr 的 next 方法中有一個(gè) checkForComodification 方法，代碼如下：

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

這里會(huì)首先檢查 modCount 是否等于 expectedModCount。modCount 是保存修改次數(shù)，每次調(diào)用 add、remove 或 trimToSize 等方法時(shí)它會(huì)增加，expectedModCount 是迭代器的變量，當(dāng)創(chuàng)建迭代器時(shí)會(huì)初始化并記錄當(dāng)時(shí)的 modCount。后面迭代期間如果發(fā)現(xiàn) modCount 和 expectedModCount 不一致，就說(shuō)明有人修改了集合的內(nèi)容，就會(huì)拋出異常。

和 ArrayList 不同的是，CopyOnWriteArrayList 的迭代器在迭代的時(shí)候，如果數(shù)組內(nèi)容被修改了，CopyOnWriteArrayList 不會(huì)報(bào) ConcurrentModificationException 的異常，因?yàn)榈魇褂玫囊廊皇桥f數(shù)組，只不過(guò)迭代的內(nèi)容可能已經(jīng)過(guò)時(shí)了。演示代碼如下：

/**
* 描述： 演示CopyOnWriteArrayList迭代期間可以修改集合的內(nèi)容
*/
public class CopyOnWriteArrayListDemo {
 
    public static void main(String[] args) {
 
        CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>(new Integer[]{1, 2, 3});
 
        System.out.println(list); //[1, 2, 3]
 
        //Get iterator 1
        Iterator<Integer> itr1 = list.iterator();
 
        //Add one element and verify list is updated
        list.add(4);
 
        System.out.println(list); //[1, 2, 3, 4]
 
        //Get iterator 2
        Iterator<Integer> itr2 = list.iterator();
 
        System.out.println("====Verify Iterator 1 content====");
 
        itr1.forEachRemaining(System.out::println); //1,2,3
 
        System.out.println("====Verify Iterator 2 content====");
 
        itr2.forEachRemaining(System.out::println); //1,2,3,4
 
    }
 
}

這段代碼會(huì)首先創(chuàng)建一個(gè) CopyOnWriteArrayList，并且初始值被賦為 [1, 2, 3]，此時(shí)打印出來(lái)的結(jié)果很明顯就是 [1, 2, 3]。然后創(chuàng)建一個(gè)叫作 itr1 的迭代器，創(chuàng)建之后再添加一個(gè)新的元素，利用 list.add() 方法把元素 4 添加進(jìn)去，此時(shí)打印出 List 自然是 [1, 2, 3, 4]。再創(chuàng)建一個(gè)叫作 itr2 的迭代器，在下方把兩個(gè)迭代器迭代產(chǎn)生的內(nèi)容打印出來(lái)，這段代碼的運(yùn)行結(jié)果是：

[1, 2, 3]
[1, 2, 3, 4]
====Verify Iterator 1 content====
1
2
3
====Verify Iterator 2 content====
1
2
3
4

可以看出，這兩個(gè)迭代器打印出來(lái)的內(nèi)容是不一樣的。第一個(gè)迭代器打印出來(lái)的是 [1, 2, 3]，而第二個(gè)打印出來(lái)的是 [1, 2, 3, 4]。雖然它們的打印時(shí)機(jī)都發(fā)生在第四個(gè)元素被添加之后，但它們的創(chuàng)建時(shí)機(jī)是不同的。由于迭代器 1 被創(chuàng)建時(shí)的 List 里面只有三個(gè)元素，后續(xù)無(wú)論 List 有什么修改，對(duì)它來(lái)說(shuō)都是無(wú)感知的。

以上這個(gè)結(jié)果說(shuō)明了，CopyOnWriteArrayList 的迭代器一旦被建立之后，如果往之前的 CopyOnWriteArrayList 對(duì)象中去新增元素，在迭代器中既不會(huì)顯示出元素的變更情況，同時(shí)也不會(huì)報(bào)錯(cuò)，這一點(diǎn)和 ArrayList 是有很大區(qū)別的。

缺點(diǎn)

這些缺點(diǎn)不僅是針對(duì) CopyOnWriteArrayList，其實(shí)同樣也適用于其他的 CopyOnWrite 容器：

• 內(nèi)存占用問(wèn)題

因?yàn)?CopyOnWrite 的寫(xiě)時(shí)復(fù)制機(jī)制，所以在進(jìn)行寫(xiě)操作的時(shí)候，內(nèi)存里會(huì)同時(shí)駐扎兩個(gè)對(duì)象的內(nèi)存，這一點(diǎn)會(huì)占用額外的內(nèi)存空間。

• 在元素較多或者復(fù)雜的情況下，復(fù)制的開(kāi)銷(xiāo)很大

復(fù)制過(guò)程不僅會(huì)占用雙倍內(nèi)存，還要消耗 CPU 等資源，會(huì)降低整體性能。

• 數(shù)據(jù)一致性問(wèn)題

由于 CopyOnWrite 容器的修改是先修改副本，所以這次修改對(duì)于其他線(xiàn)程來(lái)說(shuō)，并不是實(shí)時(shí)能看到的，只有在修改完之后才能體現(xiàn)出來(lái)。如果希望寫(xiě)入的的數(shù)據(jù)馬上能被其他線(xiàn)程看到，CopyOnWrite 容器是不適用的。

源碼分析

• 數(shù)據(jù)結(jié)構(gòu)

/** 可重入鎖對(duì)象 */
final transient ReentrantLock lock = new ReentrantLock();
 
/** CopyOnWriteArrayList底層由數(shù)組實(shí)現(xiàn)，volatile修飾，保證數(shù)組的可見(jiàn)性 */
private transient volatile Object[] array;
 
/**
* 得到數(shù)組
*/
final Object[] getArray() {
    return array;
}
 
/**
* 設(shè)置數(shù)組
*/
final void setArray(Object[] a) {
    array = a;
}
 
/**
* 初始化CopyOnWriteArrayList相當(dāng)于初始化數(shù)組
*/
public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}

在這個(gè)類(lèi)中首先會(huì)有一個(gè) ReentrantLock 鎖，用來(lái)保證修改操作的線(xiàn)程安全。下面被命名為 array 的 Object[] 數(shù)組是被 volatile 修飾的，可以保證數(shù)組的可見(jiàn)性，這正是存儲(chǔ)元素的數(shù)組，同樣，可以從 getArray()、setArray 以及它的構(gòu)造方法看出，CopyOnWriteArrayList 的底層正是利用數(shù)組實(shí)現(xiàn)的，這也符合它的名字。

• add 方法

public boolean add(E e) {
 
    // 加鎖
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
 
        // 得到原數(shù)組的長(zhǎng)度和元素
        Object[] elements = getArray();
        int len = elements.length;
 
        // 復(fù)制出一個(gè)新數(shù)組
        Object[] newElements = Arrays.copyOf(elements, len + 1);
 
        // 添加時(shí)，將新元素添加到新數(shù)組中
        newElements[len] = e;
 
        // 將volatile Object[] array 的指向替換成新數(shù)組
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

add 方法的作用是往 CopyOnWriteArrayList 中添加元素，是一種修改操作。首先需要利用 ReentrantLock 的 lock 方法進(jìn)行加鎖，獲取鎖之后，得到原數(shù)組的長(zhǎng)度和元素，也就是利用 getArray 方法得到 elements 并且保存 length。之后利用 Arrays.copyOf 方法復(fù)制出一個(gè)新的數(shù)組，得到一個(gè)和原數(shù)組內(nèi)容相同的新數(shù)組，并且把新元素添加到新數(shù)組中。完成添加動(dòng)作后，需要轉(zhuǎn)換引用所指向的對(duì)象，利用 setArray(newElements) 操作就可以把 volatile Object[] array 的指向替換成新數(shù)組，最后在 finally 中把鎖解除。

總結(jié)流程：在添加的時(shí)候首先上鎖，并復(fù)制一個(gè)新數(shù)組，增加操作在新數(shù)組上完成，然后將 array 指向到新數(shù)組，最后解鎖。

上面的步驟實(shí)現(xiàn)了 CopyOnWrite 的思想：寫(xiě)操作是在原來(lái)容器的拷貝上進(jìn)行的，并且在讀取數(shù)據(jù)的時(shí)候不會(huì)鎖住 list。而且可以看到，如果對(duì)容器拷貝操作的過(guò)程中有新的讀線(xiàn)程進(jìn)來(lái)，那么讀到的還是舊的數(shù)據(jù)，因?yàn)樵谀莻€(gè)時(shí)候?qū)ο蟮囊眠€沒(méi)有被更改。

下面來(lái)分析一下讀操作的代碼，也就是和 get 相關(guān)的三個(gè)方法，分別是 get 方法的兩個(gè)重載和 getArray 方法，代碼如下：

public E get(int index) {
    return get(getArray(), index);
}
final Object[] getArray() {
    return array;
}
private E get(Object[] a, int index) {
    return (E) a[index];
}

可以看出，get 相關(guān)的操作沒(méi)有加鎖，保證了讀取操作的高速。

• 迭代器 COWIterator 類(lèi)

這個(gè)迭代器有兩個(gè)重要的屬性，分別是 Object[] snapshot 和 int cursor。其中 snapshot 代表數(shù)組的快照，也就是創(chuàng)建迭代器那個(gè)時(shí)刻的數(shù)組情況，而 cursor 則是迭代器的游標(biāo)。迭代器的構(gòu)造方法如下：

private COWIterator(Object[] elements, int initialCursor) {
    cursor = initialCursor;
    snapshot = elements;
}

可以看出，迭代器在被構(gòu)建的時(shí)候，會(huì)把當(dāng)時(shí)的 elements 賦值給 snapshot，而之后的迭代器所有的操作都基于 snapshot 數(shù)組進(jìn)行的，比如：

public E next() {
    if (! hasNext())
        throw new NoSuchElementException();
    return (E) snapshot[cursor++];
}

在 next 方法中可以看到，返回的內(nèi)容是 snapshot 對(duì)象，所以，后續(xù)就算原數(shù)組被修改，這個(gè) snapshot 既不會(huì)感知到，也不會(huì)受影響，執(zhí)行迭代操作不需要加鎖，也不會(huì)因此拋出異常。迭代器返回的結(jié)果，和創(chuàng)建迭代器的時(shí)候的內(nèi)容一致。