阿里Java面試官：CopyOnWriteArrayList底層是怎么保證線程安全的？
歡迎學(xué)習(xí)解讀Java源碼專欄，在這個系列中，我將手把手帶著大家剖析Java核心組件的源碼，內(nèi)容包含集合、線程、線程池、并發(fā)、隊(duì)列等，深入了解其背后的設(shè)計(jì)思想和實(shí)現(xiàn)細(xì)節(jié)，輕松應(yīng)對工作面試。
引言
上篇文章提到ArrayList不是線程安全的，而CopyOnWriteArrayList是線程安全的。此刻我就會產(chǎn)生幾個問題：
- CopyOnWriteArrayList初始容量是多少？
- CopyOnWriteArrayList是怎么進(jìn)行擴(kuò)容的？
- CopyOnWriteArrayList是怎么保證線程安全的？
帶著這幾個問題，一起分析一下CopyOnWriteArrayList的源碼。
簡介
CopyOnWriteArrayList是一種線程安全的ArrayList，底層是基于數(shù)組實(shí)現(xiàn)，不過該數(shù)組使用了volatile關(guān)鍵字修飾。 實(shí)現(xiàn)線程安全的原理是，“人如其名”，就是 Copy On Write（寫時復(fù)制），意思就是在對其進(jìn)行修改操作的時候，復(fù)制一個新的ArrayList，在新的ArrayList上進(jìn)行修改操作，從而不影響舊的ArrayList的讀操作。 看一下源碼中CopyOnWriteArrayList內(nèi)部有哪些數(shù)據(jù)結(jié)構(gòu)組成：
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
// 加鎖，用來保證線程安全
final transient ReentrantLock lock = new ReentrantLock();
// 存儲元素的數(shù)組，使用了volatile修飾
private transient volatile Object[] array;
// 數(shù)組的get/set方法
final Object[] getArray() {
return array;
}
final void setArray(Object[] a) {
array = a;
}
}CopyOnWriteArrayList的內(nèi)部結(jié)構(gòu)非常簡單，使用ReentrantLock加鎖，用來保證線程安全。使用數(shù)組存儲元素，數(shù)組使用volatile修飾，用來保證內(nèi)存可見性。當(dāng)其他線程重新對數(shù)組對象進(jìn)行賦值的時候，當(dāng)前線程可以及時感知到。
初始化
當(dāng)我們調(diào)用CopyOnWriteArrayList的構(gòu)造方法的時候，底層邏輯是怎么實(shí)現(xiàn)的？
List<Integer> list = new CopyOnWriteArrayList<>();CopyOnWriteArrayList初始化的時候，不支持指定數(shù)組長度，接著往下看，就能明白CopyOnWriteArrayList為什么不支持指定數(shù)組長度。
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}初始化過程非常簡單，就是創(chuàng)建了一個長度為0的數(shù)組。
添加元素
再看一下往CopyOnWriteArrayList添加元素時，調(diào)用的 add() 方法源碼實(shí)現(xiàn)：
// 添加元素
public boolean add(E e) {
// 加鎖，保證線程安全
final ReentrantLock lock = this.lock;
lock.lock();
try {
// 獲取原數(shù)組
Object[] elements = getArray();
int len = elements.length;
// 創(chuàng)建一個新數(shù)組，長度原數(shù)組長度+1，并把原數(shù)組元素拷貝到新數(shù)組里面
Object[] newElements = Arrays.copyOf(elements, len + 1);
// 直接賦值給新數(shù)組末尾位置
newElements[len] = e;
// 替換原數(shù)組
setArray(newElements);
return true;
} finally {
// 釋放鎖
lock.unlock();
}
}添加元素的流程：
- 先使用ReentrantLock加鎖，保證線程安全。
- 再創(chuàng)建一個新數(shù)組，長度是原數(shù)組長度+1，并把原數(shù)組元素拷貝到新數(shù)組里面。
- 然后在新數(shù)組末尾位置賦值
- 使用新數(shù)組替換掉原數(shù)組
- 最后釋放鎖
add() 方法添加元素的時候，并沒有在原數(shù)組上進(jìn)行賦值，而是創(chuàng)建一個新數(shù)組，在新數(shù)組上賦值后，再用新數(shù)組替換原數(shù)組。這是為了利用volatile關(guān)鍵字的特性，如果直接在原數(shù)組上進(jìn)行修改，其他線程是感知不到的。只有重新對原數(shù)組對象進(jìn)行賦值，其他線程才能感知到。 還有一個需要注意的點(diǎn)是，每次添加元素的時候都會創(chuàng)建一個新數(shù)組，并涉及數(shù)組拷貝，相當(dāng)于每次都進(jìn)行擴(kuò)容操作。當(dāng)數(shù)組較大，性能消耗較為明顯。所以CopyOnWriteArrayList適用于讀多寫少的場景，如果存在較多的寫操作場景，性能也是一個需要考慮的因素。
刪除元素
再看一下刪除元素的方法 remove() 的源碼：
// 按照下標(biāo)刪除元素
public E remove(int index) {
// 加鎖，保證線程安全
final ReentrantLock lock = this.lock;
lock.lock();
try {
// 獲取原數(shù)組
Object[] elements = getArray();
int len = elements.length;
E oldValue = get(elements, index);
// 計(jì)算需要移動的元素個數(shù)
int numMoved = len - index - 1;
if (numMoved == 0) {
// 0表示刪除的是數(shù)組末尾的元素
setArray(Arrays.copyOf(elements, len - 1));
} else {
// 創(chuàng)建一個新數(shù)組，長度是原數(shù)組長度-1
Object[] newElements = new Object[len - 1];
// 把原數(shù)組下標(biāo)前后兩段的元素都拷貝到新數(shù)組里面
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
// 替換原數(shù)組
setArray(newElements);
}
return oldValue;
} finally {
// 釋放鎖
lock.unlock();
}
}刪除元素的流程：
- 先使用ReentrantLock加鎖，保證線程安全。
- 再創(chuàng)建一個新數(shù)組，長度是原數(shù)組長度-1，并把原數(shù)組中剩余元素（不包含需要刪除的元素）拷貝到新數(shù)組里面。
- 使用新數(shù)組替換掉原數(shù)組
- 最后釋放鎖
可以看到，刪除元素的流程與添加元素的流程類似，都是需要創(chuàng)建一個新數(shù)組，再把舊數(shù)組元素拷貝到新數(shù)組，最后替換舊數(shù)組。區(qū)別就是新數(shù)組的長度不一樣，刪除元素流程中的新數(shù)組長度是舊數(shù)組長度-1，添加元素流程中的新數(shù)組長度是舊數(shù)組長度+1。 根據(jù)對象刪除元素的方法源碼與之類似，也是轉(zhuǎn)換成下標(biāo)刪除，讀者可自行查看。
批量刪除
再看一下批量刪除元素方法 removeAll() 的源碼：
// 批量刪除元素
public boolean removeAll(Collection<?> c) {
// 參數(shù)判空
if (c == null) {
throw new NullPointerException();
}
// 加鎖，保證線程安全
final ReentrantLock lock = this.lock;
lock.lock();
try {
// 獲取原數(shù)組
Object[] elements = getArray();
int len = elements.length;
if (len != 0) {
// 創(chuàng)建一個新數(shù)組，長度暫時使用原數(shù)組的長度，因?yàn)椴恢酪獎h除多少個元素。
Object[] temp = new Object[len];
// newlen表示新數(shù)組中元素個數(shù)
int newlen = 0;
// 遍歷原數(shù)組，把需要保留的元素放到新數(shù)組中
for (int i = 0; i < len; ++i) {
Object element = elements[i];
if (!c.contains(element)) {
temp[newlen++] = element;
}
}
// 如果新數(shù)組沒有滿，就釋放空白位置，并覆蓋原數(shù)組
if (newlen != len) {
setArray(Arrays.copyOf(temp, newlen));
return true;
}
}
return false;
} finally {
// 釋放鎖
lock.unlock();
}
}批量刪除元素的流程，與上面類似：
- 先使用ReentrantLock加鎖，保證線程安全。
- 再創(chuàng)建一個新數(shù)組，長度暫時使用原數(shù)組的長度，因?yàn)椴恢酪獎h除多少個元素。
- 然后遍歷原數(shù)組，把需要保留的元素放到新數(shù)組中。
- 釋放掉新數(shù)組中空白位置，再使用新數(shù)組替換掉原數(shù)組。
- 最后釋放鎖
如果遇到需要一次刪除多個元素的場景，盡量使用 removeAll() 方法，因?yàn)?nbsp;removeAll() 方法只涉及一次數(shù)組拷貝，性能比單個刪除元素更好。
并發(fā)修改問題
當(dāng)遍歷CopyOnWriteArrayList的過程中，同時增刪CopyOnWriteArrayList中的元素，會發(fā)生什么情況？測試一下：
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
public class Test {
public static void main(String[] args) {
List<Integer> list = new CopyOnWriteArrayList<>();
list.add(1);
list.add(2);
list.add(2);
list.add(3);
// 遍歷ArrayList
for (Integer key : list) {
// 判斷如果元素等于2，則刪除
if (key.equals(2)) {
list.remove(key);
}
}
System.out.println(list);
}
}輸出結(jié)果：
[1, 3]不但沒有拋出異常，還把CopyOnWriteArrayList中重復(fù)的元素也都刪除了。 原因是CopyOnWriteArrayList重新實(shí)現(xiàn)迭代器，拷貝了一份原數(shù)組的快照，在快照數(shù)組上進(jìn)行遍歷。這樣做的優(yōu)點(diǎn)是其他線程對數(shù)組的并發(fā)修改，不影響對快照數(shù)組的遍歷，但是遍歷過程中無法感知其他線程對數(shù)組修改，有得必有失。 下面是迭代器的源碼實(shí)現(xiàn)：
static final class COWIterator<E> implements ListIterator<E> {
/**
* 原數(shù)組的快照
*/
private final Object[] snapshot;
/**
* 迭代游標(biāo)
*/
private int cursor;
private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
snapshot = elements;
}
public boolean hasNext() {
return cursor < snapshot.length;
}
// 迭代下個元素
public E next() {
if (!hasNext())
throw new NoSuchElementException();
return (E)snapshot[cursor++];
}
}總結(jié)
現(xiàn)在可以回答文章開頭提出的問題了吧：
- CopyOnWriteArrayList初始容量是多少？
答案：是0
- CopyOnWriteArrayList是怎么進(jìn)行擴(kuò)容的？
答案：
- 加鎖
- 創(chuàng)建一個新數(shù)組，長度原數(shù)組長度+1，并把原數(shù)組元素拷貝到新數(shù)組里面。
- 釋放鎖
- CopyOnWriteArrayList是怎么保證線程安全的？
答案：
- 使用ReentrantLock加鎖，保證操作過程中線程安全。
- 使用volatile關(guān)鍵字修飾數(shù)組，保證當(dāng)前線程對數(shù)組對象重新賦值后，其他線程可以及時感知到。
