原文鏈接：https://www.changxuan.top/?p=1252
CopyOnWriteArrayList 是 JUC 中唯一一個支持并發的 List，
CopyOnWriteArrayList 的修改操作都是在底層的一個復制的陣列上進行，即寫時復制策略，從而實作了執行緒安全，其實原理和資料庫的讀寫分離十分相似，
基本構成
底層使用陣列 private transient volatile Object[] array; 來存盤元素，使用 ReentrantLock 獨占鎖保證相關操作的安全性，
建構式
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
// 將集合 c 內的元素復制到 list 中
public CopyOnWriteArrayList(Collection<? extends E> c) {
Object[] elements;
if (c.getClass() == CopyOnWriteArrayList.class)
elements = ((CopyOnWriteArrayList<?>)c).getArray();
else {
elements = c.toArray();
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elements.getClass() != Object[].class)
elements = Arrays.copyOf(elements, elements.length, Object[].class);
}
setArray(elements);
}
// 創建一個內部元素是 toCopyIn 副本的 list
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
添加元素
CopyOnWriteArrayList 中與添加元素相關的方法有以下幾種：
- add(E e)
- add(int index, E element)
- addAll(Collection<? extends E> c)
- addAll(int index, Collection<? extends E> c)
- addIfAbsent(E e)
- addAllAbsent(Collection<? extends E> c)
鑒于原理基本相似，下面只分析 add(E e) 和 addIfAbsent(E e) 方法做為例子，
add(E e)
原始碼
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();
}
}
進入 add 方法的執行緒首先會去嘗試獲取獨占鎖，成功獲取的執行緒會繼續執行后續添加元素邏輯，而未獲取獨占鎖的執行緒在沒有例外的情況下則會阻塞掛起，等待獨占鎖被釋放后，再次嘗試獲取，（ps. 在 CopyOnWriteArrayList 中使用的是 ReentrantLock 的非公平鎖模式）
這樣就能保證，同一時間只有一個執行緒進行添加元素，
addIfAbsent(E e)
原始碼
public boolean addIfAbsent(E e) {
// 獲取當前陣列
Object[] snapshot = getArray();
// 呼叫 indexOf 判斷元素是否已存在 （遍歷）
return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
addIfAbsent(e, snapshot);
}
private boolean addIfAbsent(E e, Object[] snapshot) {
// 獲取獨占鎖
final ReentrantLock lock = this.lock;
lock.lock();
try {
// 再次獲取當前陣列
Object[] current = getArray();
int len = current.length;
// 此處判斷是檢查在當前執行緒判斷元素不存在和獲取獨占鎖之間的這段時間內是否有其它執行緒對陣列進行了更改操作
if (snapshot != current) {
// Optimize for lost race to another addXXX operation
int common = Math.min(snapshot.length, len);
for (int i = 0; i < common; i++)
if (current[i] != snapshot[i] && eq(e, current[i]))
return false;
if (indexOf(e, current, common, len) >= 0)
return false;
}
// 與 add 方法的邏輯相同
Object[] newElements = Arrays.copyOf(current, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
如果當前陣列中不存在元素 e，addIfAbsent 則會將 e 添加至陣列中回傳 true；如果當前陣列中存在待添加元素，則會回傳 false，
在 addIfAbsent 方法中為了提高性能，設計者把判斷“當前陣列是否存在待添加元素”和“添加元素”的操作分開了，由于前一個操作不必要獲取獨占鎖，在遇到每次待添加的元素都已經存在于陣列的情況時可以高效的回傳 false ，
因為上面提到的兩步操作是非原子性的，所以再第二步操作中還需要再次進行確認之前用來判斷不存在元素 e 的陣列是否被“掉包”了，如果被“掉包”，那么也不要“嫌棄”，就需要再判斷一下“掉包”后的陣列還能不能接著用，如果不能用直接回傳 false，如果發現能用就繼續向下執行，成功后回傳 true ，
這種設計思路，在自己的業務系統中還是比較值的借鑒的，當然上述場景下“壞”的設計，就是會先嘗試獲取獨占鎖，在獲取獨占鎖后再進行“判斷元素是否存在和決定是否添加元素的操作”，這樣則會導致大大增加執行緒阻塞掛起幾率，相信大多數同學還是能寫出漂亮的代碼的，不至于犯這種小錯誤，
獲取元素
獲取元素一共涉及到三個方法，原始碼如下：
public E get(int index) {
return get(getArray(), index);
}
// 步驟一
final Object[] getArray() {
return array;
}
// 步驟二
private E get(Object[] a, int index) {
return (E) a[index];
}
我們看到獲取元素的操作，全程沒有加鎖，并且獲取元素是由兩步操作組合而成的，一獲取當前陣列，二從當前資料中取出所指定的下標位置的元素，一旦在這兩步操作之間，有其它執行緒更改了 index 下標位置的元素，此時，獲取元素的執行緒所使用的陣列則是被廢棄掉的，它接收到的值也不是最新的值，這是寫時復制策略產生的弱一致性問題，
修改元素
可以使用 set(int index, E element) 方法修改指定位置的元素，
原始碼
public E set(int index, E element) {
// 獲取獨占鎖
final ReentrantLock lock = this.lock;
lock.lock();
try {
// 獲取當前陣列
Object[] elements = getArray();
// 獲取要修改位置的元素
E oldValue = https://www.cnblogs.com/chxuan/p/get(elements, index);
// 新值與老值是否一樣
if (oldValue != element) {
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len);
newElements[index] = element;
setArray(newElements);
} else {
// Not quite a no-op; ensures volatile write semantics
setArray(elements);
}
return oldValue;
} finally {
lock.unlock();
}
}
可以看到，在代碼中并沒有顯示的判斷 index 是否合法，如果不合法則會拋出 IndexOutOfBoundsException 例外，
主要邏輯也是先嘗試獲取獨占鎖，符合條件則進行修改，需要注意的一點是，如果指定索引處的元素值與新值相等，也會呼叫 setArray(Object[] a) 一次方法，這主要是為了保證 volatile 語意，（執行緒在寫入 volatile 變數時，不會把值快取在暫存器或者其它地方，而是會把值刷回到主記憶體，確保記憶體可見性）
洗掉元素
洗掉元素的方法包括：
- E remove(int index)
- boolean remove(Object o)
- boolean removeAll(Collection<?> c)
我們來看下 remove(int index) 的實作，
原始碼
public E remove(int index) {
// 獲取獨占鎖
final ReentrantLock lock = this.lock;
lock.lock();
try {
// 獲取當前資料
Object[] elements = getArray();
int len = elements.length;
// 獲取要被洗掉的元素
E oldValue = https://www.cnblogs.com/chxuan/p/get(elements, index);
// 計算要移動的位置
int numMoved = len - index - 1;
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();
}
}
其實代碼邏輯很清楚，獲取鎖后根據情況復制老陣列中的未洗掉資料到新陣列即可，
迭代器
不知道大家有沒有在遍歷 ArrayList 變數的程序中想沒想過洗掉其中的某個元素？反正我曾經這么寫過，然后就出現了問題 ... 后來使用了 ArrayList 的迭代器之后就沒有錯誤了，
在 CopyOnWriteArrayList 中也有迭代器，但是也存在著弱一致性問題
原始碼
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
static final class COWIterator<E> implements ListIterator<E> {
/** 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;
}
public boolean hasPrevious() {
return cursor > 0;
}
// 獲取元素
public E next() {
if (! hasNext())
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();
}
... ...
}
可以看到，CopyOnWriteArrayList 的迭代器并不支持 remove 操作，在呼叫 iterator() 方法時獲取了一份當前陣列的快照，如果在遍歷期間并沒有其它執行緒對資料做更改操作就不會出現一致性的問題，一旦有其它執行緒對資料更改后，將 CopyOnWriteArrayList 中的陣列更改為了新陣列，此時迭代器所持有的資料就相當于快照了，同時也出現了弱一致性問題，
拓展延申
還記得剛剛提到的 addIfAbsent 方法嗎？看到它你有沒有聯想到什么東西呢？集合 set?
對的，通過 addIfAbsent 方法也能實作集合的功能，CopyOnWriteArraySet 的底層就是使用 CopyOnWriteArrayList 實作的，(PS. HasSet 的底層依賴 HashMap ，)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/255459.html
標籤：Java
上一篇：Mybatis01