CopyOnWriteArrayList與CopyOnWriteArraySet詳解

什麼是CopyOnWrite容器

　　【1】CopyOnWrite容器是基於併發模式Copy-on-Write模式（最簡單的併發解決方案）實現的用於避免共用的數據集合。

　　【2】CopyOnWrite容器又被成為寫時複製的容器，即當我們往一個容器添加元素的時候，不直接往當前容器添加，而是先將當前容器進行Copy，複製出一個新的容器，然後新的容器里添加元素，添加完元素之後，再將原容器的引用指向新的容器。這樣做的好處是我們可以對CopyOnWrite容器進行併發的讀，而不需要加鎖，因為當前容器不會添加任何元素。所以CopyOnWrite容器也是一種讀寫分離的思想，讀和寫不同的容器。

　　【3】適用場景：讀多寫少的場景。

源碼分析CopyOnWriteArrayList的實現

　　【1】屬性說明

//用於鎖住所有變化情況
final transient ReentrantLock lock = new ReentrantLock();

//存儲數據的數組只能通過getArray/setArray進行改變
private transient volatile Object[] array;

　　【2】方法解析（僅展示部分方法）

　　　　1）添加方法

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

public void add(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+len);
        Object[] newElements;
        int numMoved = len - index;
        if (numMoved == 0)
            newElements = Arrays.copyOf(elements, len + 1);
        else {
            newElements = new Object[len + 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index, newElements, index + 1, numMoved);
        }
        newElements[index] = element;
        setArray(newElements);
    } finally {
        lock.unlock();
    }
}

　　　　2）設置方法

public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        E oldValue = get(elements, index);

        if (oldValue != element) {
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len);
            newElements[index] = element;
            setArray(newElements);
        } else {
            // 這裡其實是將副本，重新放回去
            setArray(elements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

　　　　3）刪除方法

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

　　　　4）獲取方法

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

public E get(int index) {
    return get(getArray(), index);
}

//final修飾方法之後該方法無法被子類覆蓋
final Object[] getArray() {
    return array;
}

　　【3】彙總說明

　　　　1.CopyOnWriteArrayList之所以選擇數組而不是鏈表作為變數的存儲空間的原因：

　　　　　　1）提高處理速度，因為數組存儲在記憶體中一塊連續的空間，而鏈表則是分散的，採用Arrays.copyOf 本質上底層還是使用 System.arraycopy 將那塊連續的記憶體空間的數據一次性拷貝，減少操作次數。

　　　　2.由源碼可以看到，每次進行修改的時候都會加鎖僅限於一個線程進行變更操作，避免了共用變數併發寫的問題。所以是線程安全的。

　　　　3.但是其占用記憶體空間容易出現問題，如：在進行寫操作的時候，記憶體里會同時駐扎兩個對象的記憶體，舊的對象和新寫入的對象（註意:在複製的時候只是複製容器里的引用，只是在寫的時候會創建新對象添加到新容器里，而舊容器的對象還在使用，所以有兩份對象記憶體）。如果這些對象占用的記憶體比較大，比如說200M左右，那麼再寫入100M數據進去，記憶體就會占用300M，那麼這個時候很有可能造成頻繁的Yong GC和Full GC。而Full GC過長則應用響應時間也隨之變長。

　　　　4.數據一致性問題，我們可以看出數據並不是實時一致性的，而是最終一致性。因為會先將數據拷貝到newElements 中，再設置到array的指針指向。要知道操作系統是基於時間片輪轉機制分配運行時間（如：時間耗盡沒有新的時間片給予，會導致線程上下文切換），所以中間的間隔時間可以假設很長，那麼修改是寫入了，但是變更還沒進行。其次，在加鎖的時間內，其他線程讀取的其實都是沒有修改的數據。

源碼分析CopyOnWriteArraySet的實現

　　【1】屬性說明

private final CopyOnWriteArrayList<E> al;

　　【2】方法說明

public boolean add(E e) {
    return al.addIfAbsent(e);
}

//CopyOnWriteArrayList類的方法
public boolean addIfAbsent(E e) {
    Object[] snapshot = getArray();
    return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false : addIfAbsent(e, snapshot);
}

private static int indexOf(Object o, Object[] elements, int index, int fence) {
    if (o == null) {
        for (int i = index; i < fence; i++)
            if (elements[i] == null)
                return i;
    } else {
        for (int i = index; i < fence; i++)
            if (o.equals(elements[i]))
                return i;
    }
    return -1;
}

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;
        }
        Object[] newElements = Arrays.copyOf(current, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

　　【3】彙總說明

　　　　1.CopyOnWriteArraySet的實現嚴格來說是基於CopyOnWriteArrayList進行實現的，去重邏輯在add中體現。

　　　　2.其次是效率問題：每次插入都需要去遍歷CopyOnWriteArrayList數組一次。

　　　　3.雖然也是線程安全的，但是CopyOnWriteArrayList的缺點全部都會繼承。