Java的CopyOnWriteArrayList是什么

01、Vector

Vector 的源碼文檔上直截了當?shù)卣f了，“如果不需要線程安全，推薦使用 ArrayList 替代 Vector?！闭f實話，在我十多年的編程生涯中，的確很少使用 Vector，因為它的線程安全是建立在每個方法上都加了 synchronized 關(guān)鍵字的基礎(chǔ)上，鎖的粒度很高，意味著性能就不咋滴。

public synchronized boolean add(E e) {
    modCount++;
    add(e, elementData, elementCount);
    return true;
}

public synchronized E remove(int index) {
    modCount++;
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);

    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                numMoved);
    elementData[--elementCount] = null; // Let gc do its work

    return oldValue;
}

就連 size() 這樣的方法上都加了 synchronized，可想而知，Vector 有多鋪張浪費，有多錦衣玉食。

如果對 synchronized 關(guān)鍵字不太了解的話，可以點擊下面的鏈接查看我之前寫的一篇文章。

我去，你竟然還不會用 synchronized

高并發(fā)的情況下，一般都要求性能要給力，Vector 顯然不夠格，所以被遺忘在角落也是“罪有應(yīng)得”啊。 

02、SynchronizedList

那有些同學(xué)可能會說，可以使用 Collections.synchronizedList() 讓 ArrayList 變成線程安全啊。

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

無論是 SynchronizedRandomAccessList 還是 SynchronizedList，它們都沒有在方法級別上使用 synchronized 關(guān)鍵字，而是在方法體內(nèi)使用了 synchronized(this) 塊。

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

其中 mutex 為 this 關(guān)鍵字，也就是當前對象。

final Object mutex;     // Object on which to synchronize

SynchronizedCollection(Collection<E> c) {
    this.c = Objects.requireNonNull(c);
    mutex = this;
}  
  

03、ConcurrentModificationException

ConcurrentModificationException 這個異常不知道同學(xué)們有沒有遇到過？我先來敲段代碼讓它發(fā)生一次，讓同學(xué)們認識一下。

List<String> list = new ArrayList<>();
list.add("沉默王二");
list.add("沉默王三");
list.add("一個文章真特么有趣的程序員");

for (String str : list) {
    if ("沉默王二".equals(str)) {
        list.remove(str);
    }
}

System.out.println(list);

運行這段代碼就會拋出 ConcurrentModificationException：

Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1012)
    at java.base/java.util.ArrayList$Itr.next(ArrayList.java:966)

通過異常的堆棧信息可以查找到，異常發(fā)生在 ArrayList 的內(nèi)部類 Itr 的 checkForComodification() 方法中。

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

也就是說，在執(zhí)行 checkForComodification() 方法的時候，發(fā)現(xiàn) modCount 和 expectedModCount 不等，就拋出了 ConcurrentModificationException 異常。

為什么會這樣呢？之前的代碼也沒有調(diào)用 checkForComodification() 方法??！

那就只能來看一下反編譯后的字節(jié)碼了，原來 for-each 這個語法糖是通過 Iterator 實現(xiàn)的。

List<String> list = new ArrayList();
list.add("沉默王二");
list.add("沉默王三");
list.add("一個文章真特么有趣的程序員");
Iterator var3 = list.iterator();

while (var3.hasNext()) {
    String str = (String) var3.next();
    if ("沉默王二".equals(str)) {
        list.remove(str);
    }
}

System.out.println(list);

在執(zhí)行 list.iterator() 的時候，其實返回的就是 ArrayList 的內(nèi)部類 Itr。

public Iterator<E> iterator() {
    return new ArrayList.Itr();
}

迭代器 Iterator 是 fail-fast 的，如果以任何方式（包括 remove 和
add）對迭代器進行修改的話，就會拋出 ConcurrentModificationException。

迭代器在執(zhí)行 remove() 方法的時候，會對 modCount 加 1。remove() 方法內(nèi)部會調(diào)用 fastRemove() 方法。

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}

當在進行下一次 next() 會執(zhí)行 checkForComodification() 方法，結(jié)果發(fā)現(xiàn) modCount 為 4，而 expectedModCount 為 3，于是就拋出了異常。

 

之所以在單線程的情況下就拋出 ConcurrentModificationException，就是為了在多線程并發(fā)的情況下，不冒任何的危險，提前規(guī)避掉其他線程對 List 修改的可能性。

ArrayList 返回的迭代器是 fail-fast 的，Vector 的也是，SynchronizedList 的也是。這就意味著它們在多線程環(huán)境下通過 for-each 遍歷進行增刪操作的時候會出問題。 

04、CopyOnWriteArrayList

瞧，為了引出 CopyOnWriteArrayList，我花了多少心思。

List<String> list = new CopyOnWriteArrayList();
list.add("沉默王二");
list.add("沉默王三");
list.add("一個文章真特么有趣的程序員");

for (String str : list) {
    if ("沉默王二".equals(str)) {
        list.remove(str);
    }
}

System.out.println(list);

把 ArrayList 換成 CopyOnWriteArrayList，程序就能夠正常執(zhí)行了，輸出結(jié)果如下所示。

[沉默王三, 一個文章真特么有趣的程序員]

之所以不拋出 ConcurrentModificationException 異常，是因為 CopyOnWriteArrayList 是 fail-safe 的，迭代器遍歷的是原有的數(shù)組，remove 的時候 remove 的是復(fù)制后的新數(shù)組，然后再將新數(shù)組賦值給原有的數(shù)組。

不過，任何在獲取迭代器之后對 CopyOnWriteArrayList 的修改將不會及時反映迭代器里。

CopyOnWriteArrayList<String> list1 =
        new CopyOnWriteArrayList<>(new String[] {"沉默王二", "沉默王三"});
Iterator itr = list1.iterator();
list1.add("沉默王四");
while(itr.hasNext()) {
    System.out.print(itr.next() + " ");
}

沉默王四并不會出現(xiàn)在輸出結(jié)果中。

沉默王二 沉默王三 

ArrayList 的迭代器 Itr 是支持 remove 的。

List<String> list = new ArrayList();
list.add("沉默王二");
list.add("沉默王三");
list.add("一個文章真特么有趣的程序員");
Iterator var3 = list.iterator();

while (var3.hasNext()) {
    String str = (String) var3.next();
    if ("沉默王二".equals(str)) {
        var3.remove();
    }
}

System.out.println(list);

程序輸出的結(jié)果如下所示：

[沉默王三, 一個文章真特么有趣的程序員]

而 CopyOnWriteArrayList 的迭代器 COWIterator 是不支持 remove 的。

public void remove() {
            throw new UnsupportedOperationException();
        }

 

CopyOnWriteArrayList 實現(xiàn)了 List 接口，不過，它不在 java.util 包下，而在 java.util.concurrent 包下，算作是 ArrayList 的增強版，線程安全的。

顧名思義，CopyOnWriteArrayList 在進行寫操作（add、set、remove）的時候會先進行拷貝，底層是通過數(shù)組復(fù)制來實現(xiàn)的。

Java 8 的時候，CopyOnWriteArrayList 的增刪改操作方法使用的是  ReentrantLock（可重入鎖，一個線程獲得了鎖之后仍然可以反復(fù)的加鎖，不會出現(xiàn)自己阻塞自己的情況）。

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();
    }
}

Java 14 的時候，已經(jīng)改成 synchronized 塊了。

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;
    }
}

其中的 lock 是一個 Object 對象（注釋上說和 ReentrantLock 有一點關(guān)系）。

/**
 * The lock protecting all mutators.  (We have a mild preference
 * for builtin monitors over ReentrantLock when either will do.)
 */
final transient Object lock = new Object();

使用 ReentrantLock 性能更好，還是 synchronized 塊性能更好，同學(xué)們可以試驗一下。不過，從另外一些細節(jié)上看，Java 14 的寫法比 Java 8 更簡潔一些，其中就少了一個 newElements 變量的創(chuàng)建。

再來看 set() 方法：

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;
        }
        // Ensure volatile write semantics even when oldvalue == element
        setArray(es);
        return oldValue;
    }
}

同樣使用了 synchronized 塊，并且調(diào)用了封裝好的 clone() 方法進行了復(fù)制。

然后來看 remove() 方法：

public E remove(int index) {
    synchronized (lock) {
        Object[] es = getArray();
        int len = es.length;
        E oldValue = elementAt(es, index);
        int numMoved = len - index - 1;
        Object[] newElements;
        if (numMoved == 0)
            newElements = Arrays.copyOf(es, len - 1);
        else {
            newElements = new Object[len - 1];
            System.arraycopy(es, 0, newElements, 0, index);
            System.arraycopy(es, index + 1, newElements, index,
                    numMoved);
        }
        setArray(newElements);
        return oldValue;
    }
} 

synchronized 塊是必須的，數(shù)組復(fù)制（System.arraycopy()）也是必須的。

和 Vector 不同的是，CopyOnWriteArrayList 的 get()、size() 方法不再加鎖。

public int size() {
    return getArray().length;
}

public E get(int index) {
    return elementAt(getArray(), index);
}