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適合讀多寫少的情況。