CopyOnWriteArrayList 原始碼解析

語言: CN / TW / HK

highlight: atom-one-dark theme: vuepress


小知識,大挑戰!本文正在參與“程式設計師必備小知識”創作活動 CopyOnWriteArrayList為執行緒安全的ArrayList,這節分析下CopyOnWriteArrayList的原始碼,基於JDK1.8。

類結構

CopyOnWriteArrayList類關係圖:

col01.png CopyOnWriteArrayList實現了List介面的所有方法,主要包含如下兩個成員變數:

```java // 可重入鎖,用於對寫操作加鎖 final transient ReentrantLock lock = new ReentrantLock();

// Object型別陣列,存放資料,volatile修飾,目的是一個執行緒對這個欄位的修改另外一個執行緒立即可見 private transient volatile Object[] array; ```

CopyOnWriteArrayList中並沒有和容量有關的屬性或者常量,下面通過對一些常用方法的原始碼解析,就可以知道原因。

方法解析

建構函式

CopyOnWriteArrayList()空參建構函式:

```java public CopyOnWriteArrayList() { setArray(new Object[0]); }

final void setArray(Object[] a) { array = a; } ```

無參建構函式直接建立了一個長度為0的Object陣列。

CopyOnWriteArrayList(Collection<? extends E> c)

java public CopyOnWriteArrayList(Collection<? extends E> c) { Object[] elements; if (c.getClass() == CopyOnWriteArrayList.class) // 如果集合型別就是CopyOnWriteArrayList,則直接將其array賦值給當前CopyOnWriteArrayList elements = ((CopyOnWriteArrayList<?>)c).getArray(); else { // 如果不是CopyOnWriteArrayList型別,則將集合轉換為陣列 elements = c.toArray(); // 就如ArrayList原始碼分析所述那樣,c.toArray()返回型別不一定是Object[].class,所以需要轉換 if (elements.getClass() != Object[].class) elements = Arrays.copyOf(elements, elements.length, Object[].class); } // 設定array值 setArray(elements); }

CopyOnWriteArrayList(E[] toCopyIn)

java public CopyOnWriteArrayList(E[] toCopyIn) { // 入參為陣列,拷貝一份賦值給array setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class)); }

add(E e)

add(E e)往CopyOnWriteArrayList末尾新增元素:

```java public boolean add(E e) { // 獲取可重入鎖 final ReentrantLock lock = this.lock; // 上鎖,同一時間內只能有一個執行緒進入 lock.lock(); try { // 獲取當前array屬性值 Object[] elements = getArray(); // 獲取當前array陣列長度 int len = elements.length; // 複製一份新陣列,新陣列長度為當前array陣列長度+1 Object[] newElements = Arrays.copyOf(elements, len + 1); // 在新陣列末尾新增元素 newElements[len] = e; // 新陣列賦值給array屬性 setArray(newElements); return true; } finally { // 鎖釋放 lock.unlock(); } }

final Object[] getArray() { return array; } ```

可以看到,add操作通過ReentrantLock來確保執行緒安全。通過add方法,我們也可以看出CopyOnWriteArrayList修改操作的基本思想為:複製一份新的陣列,新陣列長度剛好能夠容納下需要新增的元素;在新數組裡進行操作;最後將新陣列賦值給array屬性,替換舊陣列。這種思想也稱為“寫時複製”,所以稱為CopyOnWriteArrayList。

此外,我們可以看到CopyOnWriteArrayList中並沒有類似於ArrayList的grow方法擴容的操作。

add(int index, E element)

add(int index, E element)指定下標新增指定元素:

java public void add(int index, E element) { // 獲取可重入鎖 final ReentrantLock lock = this.lock; // 上鎖,同一時間內只能有一個執行緒進入 lock.lock(); try { // 獲取當前array屬性值 Object[] elements = getArray(); // 獲取當前array陣列長度 int len = elements.length; // 下標檢查 if (index > len || index < 0) throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len); Object[] newElements; int numMoved = len - index; if (numMoved == 0) // numMoved為0,說明是在末尾新增,過程和add(E e)方法一致 newElements = Arrays.copyOf(elements, len + 1); else { // 否則建立一個新陣列,陣列長度為舊陣列長度值+1 newElements = new Object[len + 1]; // 分兩次複製,分別將index之前和index+1之後的元素複製到新陣列中 System.arraycopy(elements, 0, newElements, 0, index); System.arraycopy(elements, index, newElements, index + 1, numMoved); } // 在新陣列的index位置新增指定元素 newElements[index] = element; // 新陣列賦值給array屬性,替換舊陣列 setArray(newElements); } finally { // 鎖釋放 lock.unlock(); } }

set(int index, E element)

set(int index, E element)設定指定位置的值:

```java public E set(int index, E element) { // 獲取可重入鎖 final ReentrantLock lock = this.lock; // 上鎖,同一時間內只能有一個執行緒進入 lock.lock(); try { // 獲取當前array屬性值 Object[] elements = getArray(); // 獲取當前array指定index下標值 E oldValue = get(elements, index); if (oldValue != element) { // 如果新值和舊值不相等 int len = elements.length; // 複製一份新陣列,長度和舊陣列一致 Object[] newElements = Arrays.copyOf(elements, len); // 修改新陣列index下標值 newElements[index] = element; // 新陣列賦值給array屬性,替換舊陣列 setArray(newElements); } else { // 即使新值和舊值一致,為了確保volatile語義,需要重新設定array setArray(elements); } return oldValue; } finally { // 釋放鎖 lock.unlock(); } }

private E get(Object[] a, int index) { return (E) a[index]; } ```

remove(int index)

remove(int index)刪除指定下標元素:

java public E remove(int index) { // 獲取可重入鎖 final ReentrantLock lock = this.lock; // 上鎖,同一時間內只能有一個執行緒進入 try { // 獲取當前array屬性值 Object[] elements = getArray(); // 獲取當前array長度 int len = elements.length; // 獲取舊值 E oldValue = get(elements, index); int numMoved = len - index - 1; if (numMoved == 0) // 如果刪除的是最後一個元素,則將當前array設定為新陣列 // 新陣列長度為舊陣列長度-1,這樣剛好截去了最後一個元素 setArray(Arrays.copyOf(elements, len - 1)); else { // 分段複製,將index前的元素和index+1後的元素複製到新陣列 // 新陣列長度為舊陣列長度-1 Object[] newElements = new Object[len - 1]; System.arraycopy(elements, 0, newElements, 0, index); System.arraycopy(elements, index + 1, newElements, index, numMoved); // 設定array setArray(newElements); } return oldValue; } finally { // 鎖釋放 lock.unlock(); } }

可以看到,CopyOnWriteArrayList中的增刪改操作都是在新陣列中進行的,並且通過加鎖的方式確保同一時刻只能有一個執行緒進行操作,操作完後賦值給array屬性,替換舊陣列,舊陣列失去了引用,最終由GC回收。

get(int index)

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

可以看到,get(int index)操作是分兩步進行的:

  1. 通過getArray()獲取array屬性值;
  2. 獲取array陣列index下標值。

這個過程並沒有加鎖,所以在併發環境下可能出現如下情況:

  1. 執行緒1呼叫get(int index)方法獲取值,內部通過getArray()方法獲取到了array屬性值;
  2. 執行緒2呼叫CopyOnWriteArrayList的增刪改方法,內部通過setArray方法修改了array屬性的值;
  3. 執行緒1還是從舊的array陣列中取值。

所以get方法是弱一致性的

size()

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

size()方法返回當前array屬性長度,因為CopyOnWriteArrayList中的array陣列每次複製都剛好能夠容納下所有元素,並不像ArrayList那樣會預留一定的空間。所以CopyOnWriteArrayList中並沒有size屬性,元素的個數和陣列的長度是相等的。

迭代器

```java public Iterator iterator() { return new COWIterator(getArray(), 0); } static final class COWIterator implements ListIterator { / Snapshot of the array */ private final Object[] snapshot; / Index of element to be returned by subsequent call to next. */ private int cursor;

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

public boolean hasNext() {
    return cursor < snapshot.length;
}
......

} ```

可以看到,迭代器也是弱一致性的,並沒有在鎖中進行。如果其他執行緒沒有對CopyOnWriteArrayList進行增刪改的操作,那麼snapshot還是建立迭代器時獲取的array,但是如果其他執行緒對CopyOnWriteArrayList進行了增刪改的操作,舊的陣列會被新的陣列給替換掉,但是snapshot還是原來舊的陣列的引用:

java CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>(); list.add("hello"); Iterator<String> iterator = list.iterator(); list.add("world"); while (iterator.hasNext()){ System.out.println(iterator.next()); }

輸出結果僅為hello。

總結

  1. CopyOnWriteArrayList體現了寫時複製的思想,增刪改操作都是在複製的新陣列中進行的;
  2. CopyOnWriteArrayList的取值方法是弱一致性的,無法確保實時取到最新的資料;
  3. CopyOnWriteArrayList的增刪改方法通過可重入鎖確保執行緒安全;
  4. CopyOnWriteArrayList執行緒安全體現在多執行緒增刪改不會丟擲java.util.ConcurrentModificationException異常,並不能確保資料的強一致性;
  5. 同一時刻只能有一個執行緒對CopyOnWriteArrayList進行增刪改操作,而讀操作沒有限制,並且 CopyOnWriteArrayList增刪改操作都需要複製一份新陣列,增加了記憶體消耗,所以CopyOnWriteArrayList適合讀多寫少的情況。