CopyOnWriteArrayList源碼閱讀筆記

​

簡介

ArrayList是開發中使用比較多的集合，它不是線程安全的，CopyOnWriteArrayList就是線程安全版本的ArrayList。CopyOnWriteArrayList同樣是通過數組實作，這個類的名字叫“CopyOnWrite ”，它是在寫入的時候拷貝數組，對副本進行操作。

原理

CopyOnWriteArrayList采用了一種讀寫分離的并發政策。CopyOnWriteArrayList容器允許并發讀，讀操作是無鎖的，性能較高。至于寫操作，比如向容器中添加一個元素，則首先将目前容器複制一份，然後在新副本上執行寫操作，結束之後再将原容器的引用指向新容器。示意圖如下：

繼承體系

通過類圖，可以看到CopyOnWriteArrayList的繼承體系·：

• 實作了List, RandomAccess, Cloneable, java.io.Serializable等接口。
• 實作了List，提供了基礎的添加、删除、周遊等操作。
• 實作了RandomAccess，提供了随機通路的能力。
• 實作了Cloneable，可以被克隆。
• 實作了Serializable，可以被序列化。

源碼分析

屬性

//可重入鎖，保證線程安全
    final transient ReentrantLock lock = new ReentrantLock();
    
    //存放資料元素的數組，隻能通過get/set方法通路
    private transient volatile Object[] array;

    final Object[] getArray() {
        return array;
    }
    
    final void setArray(Object[] a) {
        array = a;
    }      

• lock：用于修改時加鎖，使用transient修飾表示不自動序列化。
• array:被使用volatile修飾表示一個線程對這個字段的修改另外一個線程立即可見。

構造方法

• 無參構造方法：建立一個空數組

public CopyOnWriteArrayList() {
        setArray(new Object[0]);
 }      

• 有參構造方法，參數為集合

public CopyOnWriteArrayList(Collection<? extends E> c) {
        Object[] elements;
         // 如果c也是CopyOnWriteArrayList類型
        // 那麼直接把它的數組拿過來使用
        if (c.getClass() == CopyOnWriteArrayList.class)
            elements = ((CopyOnWriteArrayList<?>)c).getArray();
        else {
           //否則，先轉換為數組
            elements = c.toArray();
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
           //  檢查c.toArray()傳回的是不是Object[]類型，如果不是，重新拷貝成Object[].class類型
            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));
    }      

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(int index, E element)

在指定位置插入數組

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)
            // 如果插入的位置是最後一位
            // 那麼拷貝一個n+1的數組, 其前n個元素與舊數組一緻
                newElements = Arrays.copyOf(elements, len + 1);
            else {
                // 如果插入的位置不是最後一位
               // 那麼建立一個n+1的數組
                newElements = new Object[len + 1];
                //拷貝舊數組[0,……index-1]下标的元素
                System.arraycopy(elements, 0, newElements, 0, index);
                //拷貝舊數組的其餘元素到新數組[index+1，……length+1]，剛好空出了index下标位置
                System.arraycopy(elements, index, newElements, index + 1,
                                 numMoved);
            }
            //将插入的元素放到index下标位置
            newElements[index] = element;
            //給array指派
            setArray(newElements);
        } finally {
           //釋放鎖
            lock.unlock();
        }
    }      

寫入操作:

• 在上面添加元素的操作中，都進行了加鎖的操作
• 拷貝一個新數組，長度等于原數組長度加1，并把原數組元素拷貝到新數組中
• 把新數組指派給目前對象的array屬性，覆寫原數組

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 = get(elements, index);
            int numMoved = len - index - 1;
            if (numMoved == 0)
            // 如果移除的是最後一位
            // 那麼直接拷貝一份n-1的新數組, 最後一位就自動删除了
                setArray(Arrays.copyOf(elements, len - 1));
            else {
              // 如果移除的不是最後一位
             // 那麼建立一個n-1的新數組
                Object[] newElements = new Object[len - 1];
                // 将前index個元素拷貝到新數組中
                System.arraycopy(elements, 0, newElements, 0, index);
                // 将index後面(不包含)的元素往前挪一位
               // 這樣正好把index位置覆寫掉了, 相當于删除了
                System.arraycopy(elements, index + 1, newElements, index,
                                 numMoved);
                setArray(newElements);
            }
            return oldValue;
        } finally {
            //釋放鎖
            lock.unlock();
        }
    }      

删除操作：删除操作同理，将除要删除元素之外的其他元素拷貝到新副本中，然後切換引用，将原容器引用指向新副本。同屬寫操作，需要加鎖。

get(int index)

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

擷取操作:擷取操作屬于讀操作，直接通過數組下标擷取資料元素，沒有加鎖，是以保證了性能。

size()

public int size() {
       //傳回數組長度
        return getArray().length;
    }      

和ArrayList不同，檢視

ArrayList源碼閱讀筆記

，可以發現ArrayList中是有size屬性的，這是因為ArrayList數組的長度實際是要大于集合的大小的。CopyOnWriteArrayList每次修改都是拷貝一份正好可以存儲目标個數元素的數組，是以不需要size屬性，直接傳回數組長度即可。

總結

• CopyOnWriteArrayList使用ReentrantLock重入鎖加鎖，保證線程安全；
• CopyOnWriteArrayList的寫操作都要先拷貝一份新數組，在新數組中做修改，修改完了再用新數組替換老數組，是以空間複雜度是O(n)，性能相對低下；
• CopyOnWriteArrayList的讀操作支援随機通路，時間複雜度為O(1)；
• CopyOnWriteArrayList采用讀寫分離的思想，讀操作不加鎖，寫操作加鎖，且寫操作占用較大記憶體空間，是以适用于讀多寫少的場合；
• CopyOnWriteArrayList隻保證最終一緻性，不保證明時一緻性；