JDK12源碼分析_05 CopyOnWriteArrayList、CopyOnWriteArraySet 源碼分析

• CopyOnWriteArrayList
• CopyOnWriteArraySet

CopyOnWriteArrayList

CopyOnWriteArrayList 是并發版的ArrayList。

它的本質是修改操作時，在底層複制一個資料庫快照上進行，然後再把新的數組指針指派給該集合。

是以原來已經開始周遊的還是用的舊的引用。即為寫時複制政策。

接下來我們看一個英文的描述。

A thread-safe variant of java.util.ArrayList in which all mutative operations add, set, and so on are implemented by making a fresh copy of the underlying array. This is ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations, and is useful when you cannot or don’t want to synchronize traversals, yet need to preclude interference among concurrent threads. The “snapshot” style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException. The iterator will not reflect additions, removals, or changes to the list since the iterator was created. Element-changing operations on iterators themselves (remove, set, and add) are not supported. These methods throw UnsupportedOperationException. All elements are permitted, including null. Memory consistency effects: As with other concurrent collections, actions in a thread prior to placing an object into a CopyOnWriteArrayList.

我的翻譯：

java.util.ArrayList的線程安全變體。其中所有的更改操作add、set等都是通過建立底層數組的新副本來實作的。這通常開銷太大，但是當周遊操作的數量遠遠超過更改時，它可能比替代方法更有效；當您不能或不想同步周遊，但又需要排除并發線程之間的幹擾時，它很有用。“快照”樣式疊代器方法使用對建立疊代器時數組狀态的引用。該數組在疊代器的生命周期内從未更改，是以不可能發生幹擾，并且保證疊代器不會抛出ConcurrentModificationException。自建立疊代器以來，疊代器不會反映清單的添加、删除或更改。不支援對疊代器本身(删除、設定和添加)進行元素更改操作。這些方法抛出 UnsupportedOperationException。所有元素都是允許的，包括null。記憶體一緻性效果:與其他并發集合一樣，在将對象放入 CopyOnWriteArrayList之前，線程中的操作。

final transient Object lock = new Object();

private transient volatile Object[] array;
           

volatile Object[] array 這個數組用來存儲資料。

這裡我們可以看到JDK12已經放棄ReentrantLock了，而采用了 Object lock。

我們看一下官方解釋為什麼要換成這樣？

The lock protecting all mutators. (We have a mild preference for builtin monitors over ReentrantLock when either will do.)

這裡可以看出本質上螢幕鎖和ReentrantLock 可重入鎖效果是一樣的。這裡使用螢幕鎖可以獲得更好的性能。那我們不妨來看看它是怎樣add操作的。

public boolean add(E e) {
        synchronized (lock) {
            Object[] es = getArray();
            int len = es.length;
            es = Arrays.copyOf(es, len + 1);
            es[len] = e;
            setArray(es);
            return true;
        }
    }
           

整個add的操作需要獲得 Object lock 的螢幕鎖，被synchronized 包裹住了，是以同一時間隻有一個線程能夠執行add代碼塊裡面的内容。

這在曾經的JDK版本裡面，都是ReentrantLock 擷取鎖，然後再執行，最後釋放鎖的流程，現在修改成了synchronized 為了取得更好的性能，更簡單的代碼結構，不用再考慮finally釋放鎖的問題。

我們這裡看到 Object[] es = getArray();是擷取數組，Arrays.copyOf把數組進行了複制，并添加新元素，最後再把這個新數組的指針給這個集合setArray。add操作并沒有在原數組上進行。

也就是說如果已經有循環在變老的數組，這裡的setArray本質是指針操作，原數組引用依舊還在，依舊可以繼續循環周遊。是以說他是add時複制政策。

這裡我們也能看出add的操作的開銷非常大，每一次的新增操作必然要複制Arrays.copyOf 老的數組。如果寫入操作非常頻繁的話，應該是不能使用這個集合的。CopyOnWriteArrayList 适合讀多寫少的場景。

接下來我們來看如何擷取指定位置的元素

public E get(int index) {
        return elementAt(getArray(), index);
}
final Object[] getArray() {
        return array;
}    
static <E> E elementAt(Object[] a, int index) {
        return (E) a[index];
}
           

根據下标擷取元素總共有三個方法，而這三個方法執行起來是沒有加鎖的，是以說如果元素不存在，還是會抛下标越界的異常 IndexOutOfBoundsException。

這裡CopyOnWriteArrayList 展現了寫時複制政策的弱一緻性問題。getArray的過程中存在其他線程删除或修改資料。并且弱一緻性問題也會影響set(int index, E element)修改指定位置元素的方法，同樣會抛IndexOutOfBoundsException。

public E set(int index, E element) {
        synchronized (lock) {
            Object[] es = getArray();
            E oldValue = elementAt(es, index);

            if (oldValue != element) {
                es = es.clone();
                es[index] = element;
                setArray(es);
            }
            return oldValue;
        }
}
           

這裡我們看set方法，依舊是被包在synchronized 螢幕鎖裡面的，如果新對象和老對象不一緻，隻會建立新的數組并複制元素，再把新數組要修改的修改好了，設定setArray到集合array上面。

老版本的JDK不管新對象和老對象是否一緻，都會重新修改array得指針，現在JDK12不會有這個沒有意義的操作了。是否可以考慮成synchronized 螢幕鎖裡面不需要考慮volatile 的 array 語義一緻性問題。

删除操作也是一樣，如果是删除末尾的元素，直接複制之前的元素。

如果是删除中間的元素，那麼會進行兩次複制，把一頭一尾兩段數組拼接起來組成新的數組，替代老的數組。

接下來我們舉個例子。

// 陳濤版權所有，禁止轉載，QQ郵箱：[email protected]
    public static void main(String[] args) {
        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
        list.add("chentao1");
        list.add("chentao2");

        Iterator<String> iterator = list.iterator();
        list.add("chentao3");

        System.out.println("Iterator疊代器輸出：");
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

        System.out.println("Consumer消費者模式輸出：");
        list.forEach(new Consumer<String>() {
            public void accept(String s) {
                System.out.println(s);
            }
        });

        List<String> arrayList = new ArrayList<String>(list);
        Iterator<String> iteratorArrayList = arrayList.iterator();
        arrayList.add("chentao4");
        // 抛出異常 java.util.ConcurrentModificationException
        while (iteratorArrayList.hasNext()) {
            System.out.println(iteratorArrayList.next());
        }
    }
           

輸出：

Iterator疊代器輸出：

chentao1

chentao2

Consumer消費者模式輸出：

chentao1

chentao2

chentao3

Exception in thread “main” java.util.ConcurrentModificationException

這裡可以看出執行了list.iterator();以後再對CopyOnWriteArrayList集合進行新增操作不會影響Iterator疊代器輸出。

list.forEach(new Consumer() {…}）是JDK8以後新增的消費者forEach模式，需要自己實作accept方法，也可以傳入Lambda 表達式（Lambda允許把函數作為一個方法的參數）。

ArrayList如果使用Iterator之後再修改集合，就會抛出ConcurrentModificationException異常。原因是checkForComodification的判斷 modCount != expectedModCount

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

CopyOnWriteArraySet

CopyOnWriteArraySet的原理和CopyOnWriteArrayList非常相似，接下來我們看一下構造函數就明白了。

private final CopyOnWriteArrayList<E> al;

public CopyOnWriteArraySet() {
    al = new CopyOnWriteArrayList<E>();
}
           

CopyOnWriteArraySet底層就是CopyOnWriteArrayList al 來儲存資料的，所有操作當然也是依賴List的，接下來我們介紹不一樣的地方。

Set最重要的功能是去除重複，我們來看是怎樣實作的。

public boolean add(E e) {
        return al.addIfAbsent(e);
    }
           

這裡我們看到 add的方法的本質是 CopyOnWriteArrayList的addIfAbsent，我們去看一下CopyOnWriteArrayList的源碼。

public boolean addIfAbsent(E e) {
        Object[] snapshot = getArray();
        return indexOfRange(e, snapshot, 0, snapshot.length) < 0
            && addIfAbsent(e, snapshot);
    }
           

這裡依舊是在snapshot 鏡像上面操作的。

indexOfRange本質是for循環進行equals比較，他有從前往後循環和從後往前循環兩種模式。

如果indexOfRange沒有找到這個元素，會執行addIfAbsent(e, snapshot)，裡面的代碼是包含在synchronized裡面的，最終還是Arrays.copyOf複制數組增加元素，并設定新數組給集合。

是以這裡的CopyOnWriteArraySet和Map結構完全沒有關系，本質是一個數組！