CopyOnWriteArrayList介紹
它相當于線程安全的ArrayList。和ArrayList一樣，它是個可變數組；但是和ArrayList不同的時，它具有以下特性：
1. 它最適合于具有以下特征的應用程序：List 大小通常保持很小，只讀操作遠多于可變操作，需要在遍歷期間防止線程間的沖突。
2. 它是線程安全的。
3. 因為通常需要復制整個基礎數組，所以可變操作（add()、set() 和 remove() 等等）的開銷很大。
4. 迭代器支持hasNext(), next()等不可變操作，但不支持可變 remove()等操作。
5. 使用迭代器進行遍歷的速度很快，并且不會與其他線程發生沖突。在構造迭代器時，迭代器依賴于不變的數組快照。
CopyOnWriteArrayList原理和數據結構
CopyOnWriteArrayList的數據結構，如下圖所示：
說明：
1. CopyOnWriteArrayList實現了List接口，因此它是一個隊列。
2. CopyOnWriteArrayList包含了成員lock。每一個CopyOnWriteArrayList都和一個互斥鎖lock綁定，通過lock，實現了對CopyOnWriteArrayList的互斥訪問。
3. CopyOnWriteArrayList包含了成員array數組，這說明CopyOnWriteArrayList本質上通過數組實現的。
下面從“動態數組”和“線程安全”兩個方面進一步對CopyOnWriteArrayList的原理進行說明。
1. CopyOnWriteArrayList的“動態數組”機制 -- 它內部有個“volatile數組”(array)來保持數據。在“添加/修改/刪除”數據時，都會新建一個數組，并將更新后的數據拷貝到新建的數組中，最后再將該數組賦值給“volatile數組”。這就是它叫做CopyOnWriteArrayList的原因！CopyOnWriteArrayList就是通過這種方式實現的動態數組；不過正由于它在“添加/修改/刪除”數據時，都會新建數組，所以涉及到修改數據的操作，CopyOnWriteArrayList效率很
低；但是單單只是進行遍歷查找的話，效率比較高。
2. CopyOnWriteArrayList的“線程安全”機制 -- 是通過volatile和互斥鎖來實現的。(01) CopyOnWriteArrayList是通過“volatile數組”來保存數據的。一個線程讀取volatile數組時，總能看到其它線程對該volatile變量最后的寫入；就這樣，通過volatile提供了“讀取到的數據總是最新的”這個機制的
保證。(02) CopyOnWriteArrayList通過互斥鎖來保護數據。在“添加/修改/刪除”數據時，會先“獲取互斥鎖”，再修改完畢之后，先將數據更新到“volatile數組”中，然后再“釋放互斥鎖”；這樣，就達到了保護數據的目的。
CopyOnWriteArrayList函數列表
|
1
2
3
4
5
|
// 創建一個空列表。CopyOnWriteArrayList()// 創建一個按 collection 的迭代器返回元素的順序包含指定 collection 元素的列表。CopyOnWriteArrayList(Collection<? extends E> c)// CopyOnWriteArrayList(E[] toCopyIn) |
創建一個保存給定數組的副本的列表。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
// 將指定元素添加到此列表的尾部。boolean add(E e)// 在此列表的指定位置上插入指定元素。void add(int index, E element)// 按照指定 collection 的迭代器返回元素的順序，將指定 collection 中的所有元素添加此列表的尾部。boolean addAll(Collection<? extends E> c)// 從指定位置開始，將指定 collection 的所有元素插入此列表。boolean addAll(int index, Collection<? extends E> c)// 按照指定 collection 的迭代器返回元素的順序，將指定 collection 中尚未包含在此列表中的所有元素添加列表的尾部。int addAllAbsent(Collection<? extends E> c)// 添加元素（如果不存在）。boolean addIfAbsent(E e)// 從此列表移除所有元素。void clear()// 返回此列表的淺表副本。Object clone()// 如果此列表包含指定的元素，則返回 true。boolean contains(Object o)// 如果此列表包含指定 collection 的所有元素，則返回 true。boolean containsAll(Collection<?> c)// 比較指定對象與此列表的相等性。boolean equals(Object o)// 返回列表中指定位置的元素。E get(int index)// 返回此列表的哈希碼值。int hashCode()// 返回第一次出現的指定元素在此列表中的索引，從 index 開始向前搜索，如果沒有找到該元素，則返回 -1。int indexOf(E e, int index)// 返回此列表中第一次出現的指定元素的索引；如果此列表不包含該元素，則返回 -1。int indexOf(Object o)// 如果此列表不包含任何元素，則返回 true。boolean isEmpty()// 返回以恰當順序在此列表元素上進行迭代的迭代器。Iterator<E> iterator()// 返回最后一次出現的指定元素在此列表中的索引，從 index 開始向后搜索，如果沒有找到該元素，則返回 -1。int lastIndexOf(E e, int index)// 返回此列表中最后出現的指定元素的索引；如果列表不包含此元素，則返回 -1。int lastIndexOf(Object o)// 返回此列表元素的列表迭代器（按適當順序）。ListIterator<E> listIterator()// 返回列表中元素的列表迭代器（按適當順序），從列表的指定位置開始。ListIterator<E> listIterator(int index)// 移除此列表指定位置上的元素。E remove(int index)// 從此列表移除第一次出現的指定元素（如果存在）。boolean remove(Object o)// 從此列表移除所有包含在指定 collection 中的元素。boolean removeAll(Collection<?> c)// 只保留此列表中包含在指定 collection 中的元素。boolean retainAll(Collection<?> c)// 用指定的元素替代此列表指定位置上的元素。E set(int index, E element)// 返回此列表中的元素數。int size()// 返回此列表中 fromIndex（包括）和 toIndex（不包括）之間部分的視圖。List<E> subList(int fromIndex, int toIndex)// 返回一個按恰當順序（從第一個元素到最后一個元素）包含此列表中所有元素的數組。Object[] toArray()// 返回以恰當順序（從第一個元素到最后一個元素）包含列表所有元素的數組；返回數組的運行時類型是指定數組的運行時類型。<T> T[] toArray(T[] a)// 返回此列表的字符串表示形式。String toString() |
下面我們從“創建，添加，刪除，獲取，遍歷”這5個方面去分析CopyOnWriteArrayList的原理。
1. 創建
CopyOnWriteArrayList共3個構造函數。它們的源碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public CopyOnWriteArrayList() { setArray(new Object[0]);}public CopyOnWriteArrayList(Collection<? extends E> c) { Object[] elements = c.toArray(); if (elements.getClass() != Object[].class) elements = Arrays.copyOf(elements, elements.length, Object[].class); setArray(elements);}public CopyOnWriteArrayList(E[] toCopyIn) { setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));}說明：這3個構造函數都調用了setArray()，setArray()的源碼如下：private volatile transient Object[] array;final Object[] getArray() { return array;}final void setArray(Object[] a) { array = a;} |
說明：setArray()的作用是給array賦值；其中，array是volatile transient Object[]類型，即array是“volatile數組”。
關于volatile關鍵字，我們知道“volatile能讓變量變得可見”，即對一個volatile變量的讀，總是能看到（任意線程）對這個volatile變量最后的寫入。正在由于這種特性，每次更新了“volatile數組”之后，其它線程都能看到對它所做的更新。
關于transient關鍵字，它是在序列化中才起作用，transient變量不會被自動序列化。transient不是本文關注的重點，了解即可。
2. 添加
以add(E e)為例，來對“CopyOnWriteArrayList的添加操作”進行說明。下面是add(E e)的代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
public boolean add(E e) { final ReentrantLock lock = this.lock; // 獲取“鎖” lock.lock(); try { // 獲取原始”volatile數組“中的數據和數據長度。 Object[] elements = getArray(); int len = elements.length; // 新建一個數組newElements，并將原始數據拷貝到newElements中； // newElements數組的長度=“原始數組的長度”+1 Object[] newElements = Arrays.copyOf(elements, len + 1); // 將“新增加的元素”保存到newElements中。 newElements[len] = e; // 將newElements賦值給”volatile數組“。 setArray(newElements); return true; } finally { // 釋放“鎖” lock.unlock(); }} |
說明：add(E e)的作用就是將數據e添加到”volatile數組“中。它的實現方式是，新建一個數組，接著將原始的”volatile數組“的數據拷貝到新數組中，然后將新增數據也添加到新數組中；最后，將新數組賦值給”volatile數組“。
在add(E e)中有兩點需要關注。
第一，在”添加操作“開始前，獲取獨占鎖(lock)，若此時有需要線程要獲取鎖，則必須等待；在操作完畢后，釋放獨占鎖(lock)，此時其它線程才能獲取鎖。通過獨占鎖，來防止多線程同時修改數據！lock的定義如下：
transient final ReentrantLock lock = new ReentrantLock();
第二，操作完畢時，會通過setArray()來更新”volatile數組“。而且，前面我們提過”即對一個volatile變量的讀，總是能看到（任意線程）對這個volatile變量最后的寫入“；這樣，每次添加元素之后，其它線程都能看到新添加的元素。
3. 獲取
以get(int index)為例，來對“CopyOnWriteArrayList的刪除操作”進行說明。下面是get(int index)的代碼：
|
1
2
3
4
5
6
|
public E get(int index) { return get(getArray(), index);}private E get(Object[] a, int index) { return (E) a[index];} |
說明：get(int index)的實現很簡單，就是返回”volatile數組“中的第index個元素。
4. 刪除
以remove(int index)為例，來對“CopyOnWriteArrayList的刪除操作”進行說明。下面是remove(int index)的代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
public E remove(int index) { final ReentrantLock lock = this.lock; // 獲取“鎖” lock.lock(); try { // 獲取原始”volatile數組“中的數據和數據長度。 Object[] elements = getArray(); int len = elements.length; // 獲取elements數組中的第index個數據。 E oldValue = get(elements, index); int numMoved = len - index - 1; // 如果被刪除的是最后一個元素，則直接通過Arrays.copyOf()進行處理，而不需要新建數組。 // 否則，新建數組，然后將”volatile數組中被刪除元素之外的其它元素“拷貝到新數組中；最后，將新數組賦值給”volatile數組“。 if (numMoved == 0) setArray(Arrays.copyOf(elements, len - 1)); else { Object[] newElements = new Object[len - 1]; System.arraycopy(elements, 0, newElements, 0, index); System.arraycopy(elements, index + 1, newElements, index, numMoved); setArray(newElements); } return oldValue; } finally { // 釋放“鎖” lock.unlock(); }} |
說明：remove(int index)的作用就是將”volatile數組“中第index個元素刪除。它的實現方式是，如果被刪除的是最后一個元素，則直接通過Arrays.copyOf()進行處理，而不需要新建數組。否則，新建數組，然后將”volatile數組中被刪除元素之外的其它元素“拷貝到新數組中；最后，將新數組賦值給”volatile數組“。
和add(E e)一樣，remove(int index)也是”在操作之前，獲取獨占鎖；操作完成之后，釋放獨占是“；并且”在操作完成時，會通過將數據更新到volatile數組中“。
5. 遍歷
以iterator()為例，來對“CopyOnWriteArrayList的遍歷操作”進行說明。下面是iterator()的代碼：
|
1
2
3
|
public Iterator<E> iterator() { return new COWIterator<E>(getArray(), 0);} |
說明：iterator()會返回COWIterator對象。
COWIterator實現額ListIterator接口，它的源碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
private static class COWIterator<E> implements ListIterator<E> { private final Object[] snapshot; private int cursor; private COWIterator(Object[] elements, int initialCursor) { cursor = initialCursor; snapshot = elements; } public boolean hasNext() { return cursor < snapshot.length; } public boolean hasPrevious() { return cursor > 0; } // 獲取下一個元素 @SuppressWarnings("unchecked") public E next() { if (! hasNext()) throw new NoSuchElementException(); return (E) snapshot[cursor++]; } // 獲取上一個元素 @SuppressWarnings("unchecked") public E previous() { if (! hasPrevious()) throw new NoSuchElementException(); return (E) snapshot[--cursor]; } public int nextIndex() { return cursor; } public int previousIndex() { return cursor-1; } public void remove() { throw new UnsupportedOperationException(); } public void set(E e) { throw new UnsupportedOperationException(); } public void add(E e) { throw new UnsupportedOperationException(); }} |
說明：COWIterator不支持修改元素的操作。例如，對于remove(),set(),add()等操作，COWIterator都會拋出異常！
另外，需要提到的一點是，CopyOnWriteArrayList返回迭代器不會拋出ConcurrentModificationException異常，即它不是fail-fast機制的！
CopyOnWriteArrayList示例
下面，我們通過一個例子去對比ArrayList和CopyOnWriteArrayList。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
import java.util.*; import java.util.concurrent.*; /* * CopyOnWriteArrayList是“線程安全”的動態數組，而ArrayList是非線程安全的。 * * 下面是“多個線程同時操作并且遍歷list”的示例 * (01) 當list是CopyOnWriteArrayList對象時，程序能正常運行。 * (02) 當list是ArrayList對象時，程序會產生ConcurrentModificationException異常。 * * */ public class CopyOnWriteArrayListTest1 { // TODO: list是ArrayList對象時，程序會出錯。 //private static List<String> list = new ArrayList<String>(); private static List<String> list = new CopyOnWriteArrayList<String>(); public static void main(String[] args) { // 同時啟動兩個線程對list進行操作！ new MyThread("ta").start(); new MyThread("tb").start(); } private static void printAll() { String value = null; Iterator iter = list.iterator(); while(iter.hasNext()) { value = (String)iter.next(); System.out.print(value+", "); } System.out.println(); } private static class MyThread extends Thread { MyThread(String name) { super(name); } @Override public void run() { int i = 0; while (i++ < 6) { // “線程名” + "-" + "序號" String val = Thread.currentThread().getName()+"-"+i; list.add(val); // 通過“Iterator”遍歷List。 printAll(); } } } } |
(某一次)運行結果：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
ta-1, tb-1, ta-1, tb-1, ta-1, ta-1, tb-1, tb-1, tb-2, tb-2, ta-1, ta-2, tb-1, ta-1, tb-2, tb-1, ta-2, tb-2, tb-3, ta-2, ta-1, tb-3, tb-1, ta-3, tb-2, ta-1, ta-2, tb-1, tb-3, tb-2, ta-3, ta-2, tb-4, tb-3, ta-1, ta-3, tb-1, tb-4, tb-2, ta-4, ta-2, ta-1, tb-3, tb-1, ta-3, tb-2, tb-4, ta-2, ta-4, tb-3, tb-5, ta-3, ta-1, tb-4, tb-1, ta-4, tb-2, tb-5, ta-2, ta-5, tb-3, ta-1, ta-3, tb-1, tb-4, tb-2, ta-4, ta-2, tb-5, tb-3, ta-5, ta-3, tb-6, tb-4, ta-4, tb-5, ta-5, tb-6, ta-6, |
結果說明：如果將源碼中的list改成ArrayList對象時，程序會產生ConcurrentModificationException異常。
