CopyOnWriteArrayList中的隱藏的知識(shí)點(diǎn)有哪些

本篇內(nèi)容主要講解“CopyOnWriteArrayList中的隱藏的知識(shí)點(diǎn)有哪些”，感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“CopyOnWriteArrayList中的隱藏的知識(shí)點(diǎn)有哪些”吧!

線程安全 List

在 Java 中，線程安全的 List 不止一個(gè)，除了今天的主角 CopyOnWriteArrayList 之外，還有 Vector 類和 SynchronizedList 類，它們都是線程安全的 List 集合。在介紹 CopyOnWriteArrayList 之前，先簡(jiǎn)單介紹下另外兩個(gè)。

如果你嘗試你查看它們的源碼，你會(huì)發(fā)現(xiàn)有點(diǎn)不對(duì)頭，并發(fā)集合不都是在 java.util.concurrent 包中嘛，為什么Vector 類和 SynchronizedList 類 這兩個(gè)是在 java.util 包里呢？

確實(shí)是這樣的，這兩個(gè)線程安全的 List 和線程安全的 HashTable 是一樣的，都是比較簡(jiǎn)單粗暴的實(shí)現(xiàn)方式，直接方法上增加 synchronized 關(guān)鍵字實(shí)現(xiàn)的，而且不管增刪改查，統(tǒng)統(tǒng)加上，即使是 get 方法也不例外，沒錯(cuò)，就是這么粗暴。

Vector 類的 get 方法：

// Vector 中的 get 操作添加了 synchronized
public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

SynchronizedList 類的 ge t 方法：

public E get(int index) {
    synchronized (mutex) {return list.get(index);}
}

同學(xué)不妨思考一下，其實(shí)在 get 方法上添加同步機(jī)制也是有原因的，雖然降低了效率，但是可以讓寫入的數(shù)據(jù)立即可以被查詢到，這也保證了數(shù)據(jù)的強(qiáng)一致性。另外上面關(guān)于 synchronized 簡(jiǎn)單粗暴的描述也是不夠準(zhǔn)確的，因?yàn)樵诟甙姹镜?JDK 中，synchronized 已經(jīng)可以根據(jù)運(yùn)行時(shí)情況，自動(dòng)調(diào)整鎖的粒度，后面介紹 CopyOnWriteArrayList 時(shí)會(huì)再次講到。

CopyOnWriteArrayList

在 JDK 并發(fā)包中，目前關(guān)于 List 的并發(fā)集合，只有 CopyOnWriteArrayList 一個(gè)。上面簡(jiǎn)單介紹了 Vector 和 SynchronizdList 的粗暴實(shí)現(xiàn)，既然還有 CopyOnWriteArrayList，那么它一定是和上面兩種是有區(qū)別的，作為唯一的并發(fā) List，它有什么不同呢？

在探究 CopyOnWriteArrayList 的實(shí)現(xiàn)之前，我們不妨先思考一下，如果是你，你會(huì)怎么來實(shí)現(xiàn)一個(gè)線程安全的 List。

1. 并發(fā)讀寫時(shí)該怎么保證線程安全呢？

2. 數(shù)據(jù)要保證強(qiáng)一致性嗎？數(shù)據(jù)讀寫更新后是否立刻體現(xiàn)？

3. 初始化和擴(kuò)容時(shí)容量給多少呢？

4. 遍歷時(shí)要不要保證數(shù)據(jù)的一致性呢？需要引入 Fail-Fast 機(jī)制嗎？

通過類名我們大致可以猜測(cè)到 CopyOnWriteArrayList 類的實(shí)現(xiàn)思路：Copy-On-Write, 也就是寫時(shí)復(fù)制策略；末尾的 ArrayList 表示數(shù)據(jù)存放在一個(gè)數(shù)組里。在對(duì)元素進(jìn)行增刪改時(shí)，先把現(xiàn)有的數(shù)據(jù)數(shù)組拷貝一份，然后增刪改都在這個(gè)拷貝數(shù)組上進(jìn)行，操作完成后再把原有的數(shù)據(jù)數(shù)組替換成新數(shù)組。這樣就完成了更新操作。

但是這種寫入時(shí)復(fù)制的方式必定會(huì)有一個(gè)問題，因?yàn)槊看胃露际怯靡粋€(gè)新數(shù)組替換掉老的數(shù)組，如果不巧在更新時(shí)有一個(gè)線程正在讀取數(shù)據(jù)，那么讀取到的就是老數(shù)組中的老數(shù)據(jù)。其實(shí)這也是讀寫分離的思想，放棄數(shù)據(jù)的強(qiáng)一致性來換取性能的提升。

分析源碼 ( JDK8 )

上面已經(jīng)說了，CopyOnWriteArrayList 的思想是寫時(shí)復(fù)制，讀寫分離，它的內(nèi)部維護(hù)著一個(gè)使用 volatile 修飾的數(shù)組，用來存放元素?cái)?shù)據(jù)。

/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;

CopyOnWriteArrayList 類中方法很多，這里不會(huì)一一介紹，下面會(huì)分析其中的幾個(gè)常用的方法，這幾個(gè)方法理解后基本就可以掌握 CopyOnWriteArrayList 的實(shí)現(xiàn)原理。

構(gòu)造函數(shù)

CopyOnWriteArrayList 的構(gòu)造函數(shù)一共有三個(gè)，一個(gè)是無參構(gòu)造，直接初始化數(shù)組長度為0；另外兩個(gè)傳入一個(gè)集合或者數(shù)組作為參數(shù)，然后會(huì)把集合或者數(shù)組中的元素直接提取出來賦值給 CopyOnWriteArrayList 內(nèi)部維護(hù)的數(shù)組。

// 直接初始化一個(gè)長度為 0 的數(shù)組
public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}
// 傳入一個(gè)集合，提取集合中的元素賦值到 CopyOnWriteArrayList 數(shù)組
public CopyOnWriteArrayList(Collection<!--? extends E--> c) {
    Object[] es;
    if (c.getClass() == CopyOnWriteArrayList.class)
        es = ((CopyOnWriteArrayList<!--?-->)c).getArray();
    else {
        es = c.toArray();
        if (c.getClass() != java.util.ArrayList.class)
            es = Arrays.copyOf(es, es.length, Object[].class);
    }
    setArray(es);
}
// 傳入一個(gè)數(shù)組，數(shù)組元素提取后賦值到 CopyOnWriteArrayList 數(shù)組
public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

構(gòu)造函數(shù)是實(shí)例創(chuàng)建時(shí)調(diào)用的，沒有線程安全問題，所以構(gòu)造方法都是簡(jiǎn)單的賦值操作，沒有特殊的邏輯處理。

新增元素

元素新增根據(jù)入?yún)⒌牟煌泻脦讉€(gè)，但是原理都是一樣的，所以下面只貼出了 add(E e ) 的實(shí)現(xiàn)方式，是通過一個(gè) ReentrantLock 鎖保證線程安全的。

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock(); // 加鎖
    try {
        Object[] elements = getArray(); // 獲取數(shù)據(jù)數(shù)組
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1); // 拷貝一個(gè)數(shù)據(jù)數(shù)組，長度+1
        newElements[len] = e; // 加入新元素
        setArray(newElements); // 用新數(shù)組替換掉老數(shù)組
        return true;
    } finally {
        lock.unlock();
    }
}

具體步驟：

1. 加鎖，獲取目前的數(shù)據(jù)數(shù)組開始操作（加鎖保證了同一時(shí)刻只有一個(gè)線程進(jìn)行增加/刪除/修改操作）。

2. 拷貝目前的數(shù)據(jù)數(shù)組，且長度增加一。

3. 新數(shù)組中放入新的元素。

4. 用新數(shù)組替換掉老的數(shù)組。

5. finally 釋放鎖。

由于每次 add 時(shí)容量只增加了1，所以每次增加時(shí)都要?jiǎng)?chuàng)建新的數(shù)組進(jìn)行數(shù)據(jù)復(fù)制，操作完成后再替換掉老的數(shù)據(jù)，這必然會(huì)降低數(shù)據(jù)新增時(shí)候的性能。下面通過一個(gè)簡(jiǎn)單的例子測(cè)試 CopyOnWriteArrayList 、Vector、ArrayList 的新增和查詢性能。

public static void main(String[] args) {
    CopyOnWriteArrayList<object> copyOnWriteArrayList = new CopyOnWriteArrayList&lt;&gt;();
    Vector vector = new Vector&lt;&gt;();
    ArrayList arrayList = new ArrayList();

    add(copyOnWriteArrayList);
    add(vector);
    add(arrayList);

    get(copyOnWriteArrayList);
    get(vector);
    get(arrayList);
}
public static void add(List list) {
    long start = System.currentTimeMillis();
    for (int i = 0; i &lt; 100000; i++) {
        list.add(i);
    }
    long end = System.currentTimeMillis();
    System.out.println(list.getClass().getName() + ".size=" + list.size() + ",add耗時(shí):" + (end - start) + "ms");
}
public static void get(List list) {
    long start = System.currentTimeMillis();
    for (int i = 0; i &lt; list.size(); i++) {
        Object object = list.get(i);
    }
    long end = System.currentTimeMillis();
    System.out.println(list.getClass().getName() + ".size=" + list.size() + ",get耗時(shí):" + (end - start) + "ms");
}

從測(cè)得的結(jié)果中可以看到 CopyOnWriteArrayList 的新增耗時(shí)最久，其次是加鎖的 Vector（Vector 的擴(kuò)容默認(rèn)是兩倍）。而在獲取時(shí)最快的是線程不安全的 ArrayList，其次是 CopyOnWriteArrayList，而 Vector 因?yàn)?Get 時(shí)加鎖，性能最低。

java.util.concurrent.CopyOnWriteArrayList.size=100000,add耗時(shí):2756ms
java.util.Vector.size=100000,add耗時(shí):4ms
java.util.ArrayList.size=100000,add耗時(shí):3ms
java.util.concurrent.CopyOnWriteArrayList.size=100000,get耗時(shí):4ms
java.util.Vector.size=100000,get耗時(shí):5ms
java.util.ArrayList.size=100000,get耗時(shí):2ms

修改元素

修改元素和新增元素的思想是一致的，通過 ReentrantLock 鎖保證線程安全性，實(shí)現(xiàn)代碼也比較簡(jiǎn)單，本來不準(zhǔn)備寫進(jìn)來的，但是在看源碼時(shí)發(fā)現(xiàn)一個(gè)非常有意思的地方，看下面的代碼。

public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock(); //加鎖
    try {
        Object[] elements = getArray(); // 獲取老數(shù)組
        E oldValue = get(elements, index); // 獲取指定位置元素

        if (oldValue != element) { // 新老元素是否相等，不相等
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len); // 復(fù)制老數(shù)組
            newElements[index] = element; // 指定位置賦新值
            setArray(newElements); // 替換掉老數(shù)組
        } else {
            // Not quite a no-op; ensures volatile write semantics
            setArray(elements);  // 有意思的地方來了
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

通過源碼可以看到在修改元素前會(huì)先比較修改前后的值是否相等，而在相等的情況下，依舊 setArray(elements); 這就很奇妙了，到底是為什么呢？想了解其中的原因需要了解下 volatile 的特殊作用，通過下面這個(gè)代碼例子說明。

// initial conditions
int nonVolatileField = 0;
CopyOnWriteArrayList<string> list = /* a single String */

// Thread 1
nonVolatileField = 1;                 // (1)
list.set(0, "x");                     // (2)

// Thread 2
String s = list.get(0);               // (3)
if (s == "x") {
    int localVar = nonVolatileField;  // (4)
}
// 例子來自：https://stackoverflow.com/questions/28772539/why-setarray-method-call-required-in-copyonwritearraylist

要想理解例子中的特殊之處，首先你要知道 volatile 可以防止指令重排，其次要了解 happens-before 機(jī)制。說簡(jiǎn)單點(diǎn)就是它們可以保證代碼的執(zhí)行前后順序。

比如上面例子中的代碼，1 會(huì)在 2 之前執(zhí)行，3 會(huì)在 4 之前執(zhí)行，這都沒有疑問。還有一條是 volatile 修飾的屬性寫會(huì)在讀之前執(zhí)行，所以 2會(huì)在 3 之前執(zhí)行。而執(zhí)行順序還存在傳遞性。所以最終 1 會(huì)在 4 之前執(zhí)行。這樣 4 獲取到的值就是步驟 1 為 nonVolatileField 賦的值。如果 CopyOnWriteArrayList 中的 set 方法內(nèi)沒有為相同的值進(jìn)行 setArray，那么上面說的這些就都不存在了。

刪除元素

remove 刪除元素方法一共有三個(gè)，這里只看public E remove(int index) 方法，原理都是類似的。

public E remove(int index) {
    final ReentrantLock lock = this.lock;
    lock.lock(); // 加鎖
    try {
        Object[] elements = getArray(); // 獲取數(shù)據(jù)數(shù)組
        int len = elements.length;
        E oldValue = get(elements, index); // 獲取要?jiǎng)h除的元素
        int numMoved = len - index - 1;
        if (numMoved == 0) // 是否末尾
            setArray(Arrays.copyOf(elements, len - 1)); // 數(shù)據(jù)數(shù)組減去末尾元素
        else {
            Object[] newElements = new Object[len - 1]; // 把要?jiǎng)h除的數(shù)據(jù)的前后元素分別拷貝到新數(shù)組
            System.arraycopy(elements, 0, newElements, 0, index); 
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements); // 使用新數(shù)組替換老數(shù)組
        }
        return oldValue;
    } finally {
        lock.unlock(); // 解鎖
    }
}

代碼還是很簡(jiǎn)單的，使用 ReentrantLock 獨(dú)占鎖保證操作的線程安全性，然后使用刪除元素后的剩余數(shù)組元素拷貝到新數(shù)組，使用新數(shù)組替換老數(shù)組完成元素刪除，最后釋放鎖返回。

獲取元素

獲取下標(biāo)為 index 的元素，如果元素不存在，會(huì)拋出IndexOutOfBoundsException 異常。

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

首先看到這里是沒有任何的加鎖操作的，而獲取指定位置的元素又分為了兩個(gè)步驟：

1. getArray() 獲取數(shù)據(jù)數(shù)組。

2. get(Object[] a, int index) 返回指定位置的元素。

很有可能在第一步執(zhí)行完成之后，步驟二執(zhí)行之前，有線程對(duì)數(shù)組進(jìn)行了更新操作。通過上面的分析我們知道更新會(huì)生成一個(gè)新的數(shù)組，而我們第一步已經(jīng)獲取了老數(shù)組，所以我們?cè)谶M(jìn)行 get 時(shí)依舊在老數(shù)組上進(jìn)行，也就是說另一個(gè)線程的更新結(jié)果沒有對(duì)我們的本次 get 生效。這也是上面提到的弱一致性問題。

迭代器的弱一致性

List<string> list = new CopyOnWriteArrayList&lt;&gt;();
list.add("www.wdbyte.com");
list.add("未讀代碼");

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

現(xiàn)在 List 中添加了元素 www.wdbyte.com 和 未讀代碼，在拿到迭代器對(duì)象后，又添加了新元素 java ,可以看到遍歷的結(jié)果沒有報(bào)錯(cuò)也沒有輸出 java 。也就是說拿到迭代器對(duì)象后，元素的更新不可見。

www.wdbyte.com
未讀代碼

這是為什么呢？要先從CopyOnWriteArrayList 的 iterator() 方法的實(shí)現(xiàn)看起。

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

可以看到在獲取迭代器時(shí)，先 getArray() 拿到了數(shù)據(jù)數(shù)組 然后傳入到 COWIterator 構(gòu)造器中，接著賦值給了COWIterator 中的 snapshot 屬性，結(jié)合上面的分析結(jié)果，可以知道每次更新都會(huì)產(chǎn)生新的數(shù)組，而這里使用的依舊是老數(shù)組，所以更新操作不可見，也就是上面多次提到的弱一致性。

新版變化

上面的源碼分析都是基于 JDK 8 進(jìn)行的。寫文章時(shí)順便看了下新版的實(shí)現(xiàn)方式有沒有變化，還真的有挺大的改變，主要體現(xiàn)在加鎖的方式上，或許是因?yàn)?JVM 后來引入了 synchronized 鎖升級(jí)策略，讓 synchronized 性能有了不少提升，所以用了 synchronized 鎖替換了老的 ReentrantLock 鎖。

新增：

public boolean add(E e) {
    synchronized (lock) {
        Object[] es = getArray();
        int len = es.length;
        es = Arrays.copyOf(es, len + 1);
        es[len] = e;
        setArray(es);
        return true;
    }
}

修改：

public E set(int index, E element) {
    synchronized (lock) {
        Object[] es = getArray();
        E oldValue = elementAt(es, index);

        if (oldValue != element) {
            es = es.clone();
            es[index] = element;
        }
        // Ensure volatile write semantics even when oldvalue == element
        setArray(es);
        return oldValue;
    }
}

總結(jié)

通過上面的分析，得到下面幾點(diǎn)關(guān)于 CopyOnWriteArrayList 的總結(jié)。

1. CopyOnWriteArrayList 采用讀寫分離，寫時(shí)復(fù)制方式實(shí)現(xiàn)線程安全，具有弱一致性。

2. CopyOnWriteArrayList 因?yàn)槊看螌懭霑r(shí)都要擴(kuò)容復(fù)制數(shù)組，寫入性能不佳。

3. CopyOnWriteArrayList 在修改元素時(shí)，為了保證 volatile 語義，即使元素沒有任何變化也會(huì)重新賦值，

4. 在高版 JDK 中，得益于 synchronized 鎖升級(jí)策略， CopyOnWriteArrayList 的加鎖方式采用了 synchronized。

到此，相信大家對(duì)“CopyOnWriteArrayList中的隱藏的知識(shí)點(diǎn)有哪些”有了更深的了解，不妨來實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！