通俗易懂的 JUC 源碼剖析-Copy On Write Array List

作者：小強(qiáng)大人

來源：SegmentFault 思否社區(qū)

---

前言

眾所皆知，ArrayList是線程不安全的，它的所有方法都沒有加鎖，那么有沒有線程安全并且性能高的類呢？那就是CopyOnWriteArrayList

---

實(shí)現(xiàn)原理

首先來看它的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)：

/**?The?lock?protecting?all?mutators?*/
final?transient?ReentrantLock?lock?=?new?ReentrantLock();
/**?The?array,?accessed?only?via?getArray/setArray.?*/
private?transient?volatile?Object[]?array;

可以看到，底層和ArrayList一樣，用數(shù)組來保存元素，但它多了把獨(dú)占鎖lock，來保證線程安全。

下面直接進(jìn)入主題，看看它的add()方法如何實(shí)現(xiàn)的：

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();
????}
}

代碼邏輯很清晰明了：

第一步，獲取數(shù)組的排他鎖
第二步，獲取數(shù)組元素和長度n，拷貝一個(gè)n+1長度的新數(shù)組
第三步，把待添加的元素e放在最后一個(gè)位置
第四步，覆蓋舊的數(shù)組，返回true表示添加成功
第五步，釋放鎖

簡而言之，它的實(shí)現(xiàn)思路就跟它的命名一樣，CopyOnWrite，“寫時(shí)復(fù)制”，添加元素的時(shí)候，先復(fù)制數(shù)組，添加完成后覆蓋掉舊的數(shù)組，這些步驟是在加鎖的環(huán)境完成的，也就是說這個(gè)過程中不會(huì)有其他線程同時(shí)也在寫數(shù)組，這就保證了寫操作的線程安全。

再來看set()方法：

public?E?set(int?index,?E?element)?{
????final?ReentrantLock?lock?=?this.lock;
????lock.lock();
????try?{
????????Object[]?elements?=?getArray();
????????E?oldValue?=?get(elements,?index);
????????//?如果新值與舊值不同，則拷貝一個(gè)新數(shù)組，并在index處設(shè)置新值
????????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
????????????//?新值與舊值相同，為了保證volatile語義，也覆蓋下數(shù)組，即使內(nèi)容相同。
????????????setArray(elements);
????????}
????????return?oldValue;
????}?finally?{
????????lock.unlock();
????}
}

再來看remove()方法

public?E?remove(int?index)?{
????final?ReentrantLock?lock?=?this.lock;
????lock.lock();
????try?{
????????Object[]?elements?=?getArray();
????????int?len?=?elements.length;
????????E?oldValue?=?get(elements,?index);
????????int?numMoved?=?len?-?index?-?1;
????????//?如果刪除的是最后一個(gè)元素
????????if?(numMoved?==?0)
????????????setArray(Arrays.copyOf(elements,?len?-?1));
????????else?{
????????????Object[]?newElements?=?new?Object[len?-?1];
????????????//?分兩步復(fù)制
????????????System.arraycopy(elements,?0,?newElements,?0,?index);
????????????System.arraycopy(elements,?index?+?1,?newElements,?index,
????????????numMoved);
????????????setArray(newElements);
????????}
????????return?oldValue;
???}?finally?{
????????lock.unlock();
???}
}

再來看get()方法：

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];
}

可以看到，它的get方法分為2步，先獲取數(shù)組，再獲取index位置的元素，這2步都是沒有加鎖的？為什么不需要加鎖呢？

上面提到，add()是先拷貝原數(shù)組，然后在拷貝的數(shù)組上操作的，在setArray()之前對原數(shù)組并沒有影響，因此讀的時(shí)候不需要加鎖。雖然不需要加鎖，但會(huì)出現(xiàn)數(shù)據(jù)弱一致性問題,下圖說明

在A線程獲取了數(shù)組(a=array)后，還沒有來得及獲取index位置的元素a[index]，線程B刪除了index位置的元素，并將array引用指向新的數(shù)組(array=newArray)，但是由于線程A用的是棧區(qū)的數(shù)組引用a，它引用的還是刪除元素前的數(shù)組，因此它還是會(huì)訪問到index這個(gè)被刪除的元素，因此說會(huì)有數(shù)據(jù)的弱一致性問題，但不會(huì)拋ConcurrentModificationException異常。

它的迭代器iterator也是有這種弱一致性的特性，迭代對象是數(shù)組的快照，迭代過程中，如果其他線程修改了數(shù)組，對迭代器來說是不可見的。

代碼如下：

public?Iterator?iterator()?{
????return?new?COWIterator(getArray(),?0);
}

//?COW?=?Copy?On?Write
static?final?class?COWIterator?implements?ListIterator?{
????/**?Snapshot?of?the?array?*/
????//?數(shù)組元素的一份快照
????private?final?Object[]?snapshot;
????/**?Index?of?element?to?be?returned?by?subsequent?call?to?next.??*/
????//?當(dāng)前迭代的位置-光標(biāo)
????private?int?cursor;
????private?COWIterator(Object[]?elements,?int?initialCursor)?{
????????cursor?=?initialCursor;
????????snapshot?=?elements;
???}
????public?boolean?hasNext()?{
????????return?cursor?????}
????public?boolean?hasPrevious()?{
????????return?cursor?>?0;
????}
????@SuppressWarnings("unchecked")
????public?E?next()?{
????????if?(!?hasNext())
????????????throw?new?NoSuchElementException();
????????return?(E)?snapshot[cursor++];
????}
?}

由此可以看出，CopyOnWriteArrayList適合用在讀多寫少的場景，性能會(huì)比Vector快，因?yàn)閂ector的所有方法都加了鎖，包括讀。

最后提下，CopyOnWriteArraySet就是用CopyOnWriteArrayList實(shí)現(xiàn)的，所以原理大同小異，有興趣的同學(xué)自己去看下源碼吧。

---

點(diǎn)擊左下角閱讀原文，到?SegmentFault 思否社區(qū)?和文章作者展開更多互動(dòng)和交流，掃描下方”二維碼“或在“公眾號后臺“回復(fù)“?入群?”即可加入我們的技術(shù)交流群，收獲更多的技術(shù)文章~

-?END -