因為不知道Java的CopyOnWriteArrayList，面試官讓我回去等通知

hello，同學們，大家好，我是沉默王二，在我為數不多的面試經歷中，有一位姓馬的面試官令我印象深刻，九年過去了，我還能記得他為數不多的發(fā)量。

老馬：“兄弟，ArrayList 是線程安全的嗎？”
王二：“不是啊。”
老馬：“那有沒有線程安全的 List？”
王二：“有啊，Vector。”
老馬：“還有別的嗎？”
王二：“Vector 不就夠用了嗎？”
老馬看了一下左手腕上的表，說道：“今天差不多就到這里吧，你回去等通知。”

（不是，我特么不是剛進來，就回答了三個問題而已，就到這了？）

現在回想起來當時一臉懵逼的樣子，臉上情不自禁地泛起了紅暈，老馬的意思是讓我說說 Java 的 CopyOnWriteArrayList，可惜我當時幾乎沒怎么用過這個類，也不知道它就是個線程安全的 List，慚愧啊慚愧。

（地上有坑嗎？我想跳進去。）

真正的勇士敢于直面過去的慘淡，經過這么多年的努力，我的技術功底已經大有長進了，是時候輸出一波傷害了。希望這篇文章能夠給不太了解 CopyOnWriteArrayList 的同學一點點幫助，到時候給面試官一個好看。

注：我用的是 OpenJDK 14。

01、Vector

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

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 關鍵字不太了解的話，可以點擊下面的鏈接查看我之前寫的一篇文章。

我去，你竟然還不會用 synchronized

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

02、SynchronizedList

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

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

無論是 SynchronizedRandomAccessList 還是 SynchronizedList，它們都沒有在方法級別上使用 synchronized 關鍵字，而是在方法體內使用了 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 關鍵字，也就是當前對象。

final?Object?mutex;?????//?Object?on?which?to?synchronize

SynchronizedCollection(Collection?c)?{
????this.c?=?Objects.requireNonNull(c);
????mutex?=?this;
}

03、ConcurrentModificationException

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

List?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 的內部類 Itr 的 checkForComodification() 方法中。

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

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

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

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

List?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 的內部類 Itr。

public?Iterator?iterator()?{
????return?new?ArrayList.Itr();
}

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

迭代器在執(zhí)行 remove() 方法的時候，會對 modCount 加 1。remove() 方法內部會調用 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() 方法，結果發(fā)現 modCount 為 4，而 expectedModCount 為 3，于是就拋出了異常。

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

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

04、CopyOnWriteArrayList

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

List?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í)行了，輸出結果如下所示。

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

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

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

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

沉默王四并不會出現在輸出結果中。

沉默王二?沉默王三?

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

List?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);

程序輸出的結果如下所示：

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

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

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

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

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

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

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 的時候，已經改成 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 有一點關系）。

/**
?*?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 塊性能更好，同學們可以試驗一下。不過，從另外一些細節(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 塊，并且調用了封裝好的 clone() 方法進行了復制。

然后來看 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 塊是必須的，數組復制（System.arraycopy()）也是必須的。

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

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

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

簡單總結一下就是：第一，CopyOnWriteArrayList 在修改時，復制出一個新數組，修改的操作在新數組中完成，最后將新數組賦值給原有的數組引用。第二，CopyOnWriteArrayList 的寫加鎖，讀不加鎖。

CopyOnWriteArrayList 有很多優(yōu)勢，但數組復制是沉重的，如果寫的操作比較多，而讀的操作比較少，內存就會被占用得比較多；另外，CopyOnWriteArrayList 無法保證數據是實時同步的，因為讀寫操作是分離的，寫的操作都建立在復制的新數組上，而讀的是原有的數組。

05、最后

如果九年前，我就看到了這樣一篇文章，一定就不會被老馬刁難呢，保不準還能再拖延半個小時，讓他多問二十個問題。但我想同學們一定是比我幸運的，至少現在看到了，不晚，對不對？

公眾號：沉默王二（ID：cmower）
CSDN：沉默王二
這是一個有顏值卻靠才華吃飯的程序員，你知道，他的文章風趣幽默，讀起來就好像花錢一樣爽快。

長按下圖二維碼關注，你將感受到一個有趣的靈魂，且每篇文章都有干貨。

原創(chuàng)不易，莫要白票，如果覺得有點用的話，請毫不留情地素質三連吧，分享、點贊、在看，我不挑，因為這將是我寫作更多優(yōu)質文章的最強動力。