Java集合 | CopyOnWriteArrayList源碼分析(JDK 1.7)

一、基本結構

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

二、基本屬性

// 加鎖的方法，在增加、移除操作的時候都需要加鎖
transient final ReentrantLock lock = new ReentrantLock();

// 底層的數組
private volatile transient Object[] array;

三、構造方法

// 無參構造函數
public CopyOnWriteArrayList() {
    // 執行個體化一個 Object 類型的長度為 0 的數組，并指派給 array
    setArray(new Object[0]);
}

// 有參構造函數，參數是集合類型
public CopyOnWriteArrayList(Collection<? extends E> c) {
    // 将集合轉變成數組
    Object[] 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);
    // 将轉變之後的數組賦給 array
    setArray(elements);
}

// 有參構造函數，參數是數組
public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

通用方法

// 擷取 array 底層數組
final Object[] getArray() {
    return array;
}

// 更新底層數組 array
final void setArray(Object[] a) {
    array = a;
}

四、增加

CopyOnWriteArrayList 中的 add 方法

// 增加方法
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    // 擷取執行 add 方法的那個對象的對象鎖
    lock.lock();
    try {
        // 擷取底層數組，賦給 elements
        Object[] elements = getArray();
        int len = elements.length;
        // 将底層數組 array 複制到新的數組 newElements
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 在新數組 newElements 添加元素
        newElements[len] = e;
        // 将新數組 newElements 賦給底層數組 array
        setArray(newElements);
        return true;
    } finally {
        // 釋放目前對象的鎖
        lock.unlock();
    }
}

在 CopyOnWriteArrayList 中增加元素的時候，需要對目前對象加鎖，即在一個線程添加元素的時候，其他線程是不能同時進行增加操作的

在添加元素的時候，不是直接在底層數組 array 上添加的，而是先複制了一個新的數組，然後在這個新的數組上添加元素，最後在把新的數組指派給底層數組

增加一個元素的圖示如下

Java集合 | CopyOnWriteArrayList源碼分析(JDK 1.7)

五、删除

CopyOnWriteArrayList 中的 remove() 方法，分為兩種，一種是根據位置進行删除，還有一種是根據傳入的元素進行删除

根據通過傳入的位置進行删除

public E remove(int index) {
    final ReentrantLock lock = this.lock;
    // 擷取執行 remove 方法的那個對象的對象鎖
    lock.lock();
    try {
        // 擷取底層數組 array
        Object[] elements = getArray();
        int len = elements.length;
        // 從 elements 數組中擷取位置是 index 的值（即要被删除的元素）
        E oldValue = get(elements, index);
        // 獲得從被删元素所在位置到數組的最後一位之間的元素個數
        int numMoved = len - index - 1;
        // 如果個數是 0，說明此時被删元素是數組的最後一位，直接複制最後一位之前的所有元素，将指派的結果指派給底層數組 array
        if (numMoved == 0)
            setArray(Arrays.copyOf(elements, len - 1));
        // 如果被删元素不是數組的最後一位
        else {
            // 先執行個體化一個個數少 1 的新數組，用于存放删除指定元素之後的數組
            Object[] newElements = new Object[len - 1];
            // 首先将 elements 數組被删元素之前的所有元素複制到新數組(從新數組第0位開始接收)
            System.arraycopy(elements, 0, newElements, 0, index);
            // 然後将 elements 數組被删元素之後的所有元素複制到新數組(從新數組第index位開始接收)
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            // 将新數組 newElements 指派給底層數組 array
            setArray(newElements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

根據傳入的對象進行删除

public boolean remove(Object o) {
    final ReentrantLock lock = this.lock;
    // 擷取對象
    lock.lock();
    try {
        // 将底層數組 array 賦給 elements
        Object[] elements = getArray();
        int len = elements.length;
        // 如果數組長度大于 0
        if (len != 0) {
            // Copy while searching for element to remove
            // This wins in the normal case of element being present
            int newlen = len - 1;
            // 執行個體化一個長度比 array 數組長度小 1 的新數組
            Object[] newElements = new Object[newlen];

            // 周遊新數組
            for (int i = 0; i < newlen; ++i) {
  				// 如果傳入對象和底層數組中目前位置的值相同(底層通過equals)判斷
                if (eq(o, elements[i])) {
                    // found one;  copy remaining and exit
                    // 從被删元素的後一位開始周遊
                    for (int k = i + 1; k < len; ++k)
       					// 将被删除元素之後的所有元素賦給新數組
                        newElements[k-1] = elements[k];
                    // 将新數組賦給底層數組 array
                    setArray(newElements);
                    return true;
                } else
                 	// 如果傳入對象和底層數組中目前位置的值不同，則直接将底層數組目前位置的元素指派給新數組
                    newElements[i] = elements[i];
            }

            // special handling for last cell
            // 如果底層數組隻有1個元素
            if (eq(o, elements[newlen])) {
                // 直接将這一個元素指派給底層數組 array
                setArray(newElements);
                return true;
            }
        }
        return false;
    } finally {
        lock.unlock();
    }
}

通用方法

// 擷取數組中的某個位置的值
private E get(Object[] a, int index) {
    // 擷取數組中 index 位置的值
    return (E) a[index];
}

private static boolean eq(Object o1, Object o2) {
    // CopyOnWriteArrayList 中并沒有重寫 equals 方法
    return (o1 == null ? o2 == null : o1.equals(o2));
}

删除方法共有2種，一種是根據位置進行删除，另一種是根據元素進行删除

對于根據位置進行删除的情況，步驟如下：

将底層數組複制給新數組 elements
根據删除元素的位置進行區分

2.1 如果删除原數組中的最後一個元素，直接将最後一個元素之前的所有元素複制到一個臨時數組中，然後将這個臨時的數組賦給底層數組 array

2.2 如果不是删除原數組中的最後一個元素，先建立一個長度比原來小 1 的新數組 newElements。首先将原數組被删元素之前的所有元素複制到新數組 newElements，在将原數組被删元素之後的所有元素複制到新數組 newElements。最後再把新數組 newElements 賦給底層數組 array

對于根據元素進行删除的情況，步驟如下：

将底層數組複制給新數組 elements
執行個體化一個數組長度比原來小 1 的新數組 newElements
周遊 newElements 數組

3.1 如果要删除的值和 elements 數組目前位置的值相同，則循環周遊将 elements 數組中除了被删元素之外的所有元素按原來的次序放入 newElements 中。放完之後，将放完的 newElements 賦給底層數組 array，然後直接退出

3.2 如果要删除的值和 elements 數組目前位置的值不同，則直接将 elements 數組中目前位置的元素賦給 newElements 中的目前位置
如果原數組長度是 1，且要删除的元素和這唯一的一個元素相同，則直接将空的數組賦給底層數組 array（将唯一一個元素删除自然就變成空數組了）

和 add 方法一樣，執行 remove 方法之前也是需要擷取對象鎖的，也是先複制一份和底層數組 array 一樣的數組，然後對這個新的數組進行删除操作，最後在将新的數組指派給底層數組 array

六、其他方法

CopyOnWriteArrayList 的 get 方法

public E get(int index) {
    // 傳入底層的數組 array 和數組中的位置
    return get(getArray(), index);
}

private E get(Object[] a, int index) {
    return (E) a[index];
}

讀取的方法是不用加鎖的

七、周遊

// 集合周遊的方法
public Iterator<E> iterator() {
    // 傳入底層數組，和開始周遊的位置(從0開始)
    return new COWIterator<E>(getArray(), 0);
}

内部類 COWIterator

private static 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.  */
    // 目前周遊在 snapshot 數組中的位置
    private int cursor;
	
    // 執行個體化疊代器的時候調用該構造函數
    private COWIterator(Object[] elements, int initialCursor) {
        // 傳入初始周遊的位置，指派給 cursor
        cursor = initialCursor;
        // 将底層數組指派給新數組 snapshot
        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();
        // 從新的 snapshot 數組中擷取 cursor 位置的值
        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;
    }

    /**
      * Not supported. Always throws UnsupportedOperationException.
      * @throws UnsupportedOperationException always; <tt>remove</tt>
      *         is not supported by this iterator.
      */
    // 不支援直接在疊代器中使用 remove 方法
    public void remove() {
        throw new UnsupportedOperationException();
    }

    /**
      * Not supported. Always throws UnsupportedOperationException.
      * @throws UnsupportedOperationException always; <tt>set</tt>
      *         is not supported by this iterator.
      */
    public void set(E e) {
        throw new UnsupportedOperationException();
    }

    /**
      * Not supported. Always throws UnsupportedOperationException.
      * @throws UnsupportedOperationException always; <tt>add</tt>
      *         is not supported by this iterator.
      */
    public void add(E e) {
        throw new UnsupportedOperationException();
    }
}

可以看到，CopyOnWriteArrayList 下的 Iterator 方法，并不是對底層數組 array 進行直接周遊的，而是先将底層數組複制到新數組 snapshot，然後對這個新的數組周遊取值

此時如果在周遊的時候，執行 CopyOnWrieArrayList 的 add 或者 remove 方法，并不會影響周遊，在使用疊代器進行周遊的時候，都是對疊代器在的 snapshot 這個數組執行的，而執行集合的 add 或者 remove 方法，隻是對底層的數組 array 進行操作，發生改變的也隻是 array 這個數組，并沒有影響到 Iterator 中的 snapshot 這個數組

正因為這個機制，會出現這麼一種情況，一邊使用 Iterator 周遊 CopyOnWriteArrayList，一邊使用集合的 remove 方法删除周遊出來的元素，當周遊結束的時候，CopyOnWriteArrayList 中已經沒有元素了，而疊代器中仍然存有周遊之前底層數組中的所有元素

因為 CopyOnWriteArrayList 的疊代器不是對底層數組進行操作，所有也不會出現 ArrayList 和 HashMap 這種在使用疊代器的過程中如果集合中增加或者删除元素而發生的 ConcurrentModificationException 異常

同時要注意的是，CopyOnWriteArrayList 疊代器下的 remove、set 和 add 方法都是不能使用的，都會抛出 UnsupportedOperationException 異常

八、關于讀和寫

設想這麼一個場景，如果有兩個線程，一個線程執行讀，另一個線程執行寫，這裡需要分以下幾種情況：

1.使用Iterator進行讀

這種情況我們上面已經研究過了，如果一個線程在完成了 Iterator 的初始化之後，其他線程才開始對 CopyOnWriteArrayList 集合進行寫，即使寫操作已經完成了，但是執行讀操作的那個線程讀到的依然是舊的數組

2.使用get方式進行讀

使用 get 方法需要分這麼三種情況：

如果一個線程寫操作（在複制的數組中放了新的元素）未完成，另一個線程讀到的依然是舊的數組的元素
如果一個線程寫操作完成，但是沒有賦給底層數組，另一個線程讀到的依然是舊的數組的元素
如果一個線程寫操作完成，同時也賦給了底層數組，另一個線程讀到的則是新數組的元素

需要強調的是，讀操作是不加鎖的

九、缺點

這裡我直接引用别人寫的，寫的還是挺清楚的

https://blog.csdn.net/linsongbin1/article/details/54581787

十、參考

https://www.cnblogs.com/dolphin0520/p/3938914.html

https://blog.csdn.net/linsongbin1/article/details/54581787

https://mp.weixin.qq.com/s?__biz=MzIxNTQ3NDMzMw==&mid=2247483989&idx=1&sn=6610ee7d7938a620452284eec215d213&scene=19#wechat_redirect

Java集合 | CopyOnWriteArrayList源碼分析(JDK 1.7)

一、基本結構

二、基本屬性

三、構造方法

四、增加

五、删除

六、其他方法

七、周遊

八、關于讀和寫

1.使用Iterator進行讀

2.使用get方式進行讀

九、缺點

十、參考

繼續閱讀

Java集合在JDK1.7和JDK1.8中的不同——JDK1.7和JDK1.8中集合的對比研究——java集合深入了解1、ArrayList

java基礎-Java集合架構-Map接口-HashMap原理（jdk1.7和jdk1.8）Java集合架構-Map接口-HashMap原理和源碼

Java并發程式設計之原子性問題什麼是原子性問題簡單總結參考

Timer和TimerTask源碼解讀（面試題：雙重定時器）Timer和TimerTask源碼解讀

HashSet集合解讀

Python求兩個list的差集、交集與并集的方法（轉）一.兩個list差集二. 擷取兩個list 的并集三. 擷取兩個 list 的差集

Java多線程之synchronized進階篇

Python基礎：元組&集合&字典

jQuery callbacks函數

18_張孝祥_多線程_阻塞隊列的應用

15_張孝祥_多線程_Semaphere同步工具

Java1.8 對HashMap的resize()的了解

初探OpenStack Mitaka二．部署

# Linux常用指令 #

集合練習題1

基于jdk1.8的Vector源碼分析