第三章 CopyOnWriteArrayList源碼解析

註：在看這篇文章之前，如果對ArrayList底層不清楚的話，建議先去看看ArrayList源碼解析。http://www.cnblogs.com/java-zhao/p/5102342.html1、對於CopyOnWriteArrayList需要掌握以下幾點創建：CopyOnWriteArrayL...

註：在看這篇文章之前，如果對ArrayList底層不清楚的話，建議先去看看ArrayList源碼解析。

http://www.cnblogs.com/java-zhao/p/5102342.html

1、對於CopyOnWriteArrayList需要掌握以下幾點

創建：CopyOnWriteArrayList()
添加元素：即add(E)方法
獲取單個對象：即get(int)方法
刪除對象：即remove(E)方法
遍歷所有對象：即iterator()，在實際中更常用的是增強型的for迴圈去做遍歷

註：CopyOnWriteArrayList是一個線程安全，讀操作時無鎖的ArrayList。

2、創建

public CopyOnWriteArrayList()

使用方法：

List<String> list = new CopyOnWriteArrayList<String>();

相關源代碼：

    private volatile transient Object[] array;//底層數據結構

    /**
     * 獲取array
     */
    final Object[] getArray() {
        return array;
    }

    /**
     * 設置Object[]
     */
    final void setArray(Object[] a) {
        array = a;
    }

    /**
     * 創建一個CopyOnWriteArrayList
     * 註意：創建了一個0個元素的數組
     */
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }

View Code

註意點：

設置一個容量為0的Object[]；ArrayList會創造一個容量為10的Object[]

3、添加元素

public boolean add(E e)

使用方法：

list.add("hello");

源代碼：

    /**
     * 在數組末尾添加元素
     * 1）獲取鎖
     * 2）上鎖
     * 3）獲取舊數組及其長度
     * 4）創建新數組，容量為舊數組長度+1，將舊數組拷貝到新數組
     * 5）將要增加的元素加入到新數組的末尾，設置全局array為新數組
     */
    public boolean add(E e) {
        final ReentrantLock lock = this.lock;//這裡為什麼不直接用this.lock（即類中已經初始化好的鎖）去上鎖
        lock.lock();//上鎖
        try {
            Object[] elements = getArray();//獲取當前的數組
            int len = elements.length;//獲取當前數組元素
            /*
             * Arrays.copyOf(elements, len + 1)的大致執行流程：
             * 1）創建新數組，容量為len+1，
             * 2）將舊數組elements拷貝到新數組，
             * 3）返回新數組
             */
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;//新數組的末尾元素設成e
            setArray(newElements);//設置全局array為新數組
            return true;
        } finally {
            lock.unlock();//解鎖
        }
    }

View Code

註意點：

Arrays.copyOf(T[] original, int newLength)該方法在ArrayList中講解過

疑問：

在add(E)方法中，為什麼要重新定義一個ReentrantLock，而不直接使用那個定義的類變數鎖（全局鎖）
- 答：事實上，按照他那樣寫，即使是在add、remove、set中存在多個引用，最後也是一個實例this.lock，所以不管你在add、remove、set中怎樣去從新定義一個ReentrantLock，其實add、remove、set中最後使用的都是同一個鎖this.lock，也就是說，同一時刻，add/remove/set只能有一個在運行。這樣講，就是說，下邊這段代碼完全可以做一個修改。修改前的代碼：
```
    public boolean add(E e) {
        final ReentrantLock lock = this.lock;//這裡為什麼不直接用this.lock（即類中已經初始化好的鎖）去上鎖
        lock.lock();//上鎖
```
  View Code
  修改後的代碼：
```
    public boolean add(E e) {
        //final ReentrantLock lock = this.lock;//這裡為什麼不直接用this.lock（即類中已經初始化好的鎖）去上鎖
        this.lock.lock();//上鎖
```
  View Code
根據以上代碼可知，每增加一個新元素，都要進行一次數組的複製消耗，那為什麼每次不將數組的元素設大（比如說像ArrayList那樣，設置為原來的1.5倍+1），這樣就會大大減少因為數組元素複製所帶來的消耗？

4、獲取元素

public E get(int index)

使用方法：

list.get(0)

源代碼：

    /**
     * 根據下標獲取元素
     * 1）獲取數組array
     * 2）根據索引獲取元素
     */
    public E get(int index) {
        return (E) (getArray()[index]);
    }

View Code

註意點：

獲取不需要加鎖

疑問：在《分散式Java應用：基礎與實踐》一書中作者指出：讀操作會發生臟讀，為什麼？

從類屬性部分，我們可以看到array數組是volatile修飾的，也就是當你對volatile進行寫操作後，會將寫過後的array數組強制刷新到主記憶體，在讀操作中，當你讀出數組（即getArray()）時，會強制從主記憶體將array讀到工作記憶體，所以應該不會發生臟讀才對呀！！！

補：volatile的介紹見《附2 volatile》，鏈接如下：

http://www.cnblogs.com/java-zhao/p/5125698.html

5、刪除元素

public boolean remove(Object o)

使用方法：

list.remove("hello")

源代碼：

    /**
     * 刪除list中的第一個o
     * 1）獲取鎖、上鎖
     * 2）獲取舊數組、舊數組的長度len
     * 3）如果舊數組長度為0，返回false
     * 4）如果舊數組有值，創建新數組，容量為len-1
     * 5）從0開始遍曆數組中除了最後一個元素的所有元素
     * 5.1）將舊數組中將被刪除元素之前的元素複製到新數組中，
     * 5.2）將舊數組中將被刪除元素之後的元素複製到新數組中
     * 5.3）將新數組賦給全局array
     * 6）如果是舊數組的最後一個元素要被刪除，則
     * 6.1）將舊數組中將被刪除元素之前的元素複製到新數組中
     * 6.2）將新數組賦給全局array
     */
    public boolean remove(Object o) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();//獲取原數組
            int len = elements.length;//獲取原數組長度
            if (len != 0) {//如果有數據
                // Copy while searching for element to remove
                // This wins in the normal case of element being present
                int newlen = len - 1;//新數組長度為原數組長度-1
                Object[] newElements = new Object[newlen];//創建新數組

                for (int i = 0; i < newlen; ++i) {//遍歷新數組（不包含最後一個元素）
                    if (eq(o, elements[i])) {
                        // 將舊數組中將被刪除元素之後的元素複製到新數組中
                        for (int k = i + 1; k < len; ++k)
                            newElements[k - 1] = elements[k];
                        setArray(newElements);//將新數組賦給全局array
                        return true;
                    } else
                        newElements[i] = elements[i];//將舊數組中將被刪除元素之前的元素複製到新數組中
                }

                if (eq(o, elements[newlen])) {//將要刪除的元素時舊數組中的最後一個元素
                    setArray(newElements);
                    return true;
                }
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

View Code

判斷兩個對象是否相等：

    /**
     * 判斷o1與o2是否相等
     */
    private static boolean eq(Object o1, Object o2) {
        return (o1 == null ? o2 == null : o1.equals(o2));
    }

View Code

註意點：

需要加鎖
ArrayList的remove使用了System.arraycopy（這是一個native方法），而這裡沒使用，所以理論上這裡的remove的性能要比ArrayList的remove要低

6、遍歷所有元素

iterator() hasNext() next()

使用方法：

講解用的：

        Iterator<String> itr = list.iterator();
        while(itr.hasNext()){
            System.out.println(itr.next());
        }

View Code

實際中使用的：

        for(String str : list){
            System.out.println(str);
        }

View Code

源代碼：

    public Iterator<E> iterator() {
        return new COWIterator<E>(getArray(), 0);
    }

View Code

    private static class COWIterator<E> implements ListIterator<E> {
        private final Object[] snapshot;//數組快照
        private int cursor;//可看做數組索引

        private COWIterator(Object[] elements, int initialCursor) {
            cursor = initialCursor;
            snapshot = elements;//將實際數組賦給數組快照
        }
        
        public boolean hasNext() {
            return cursor < snapshot.length;//0~snapshot.length-1
        }
        
        public E next() {
            if (!hasNext())
                throw new NoSuchElementException();
            return (E) snapshot[cursor++];
        }

View Code

說明：這一塊兒代碼非常簡單，看看代碼註釋就好。

註意：

由於遍歷的只是全局數組的一個副本，即使全局數組發生了增刪改變化，副本也不會變化，所以不會發生併發異常。但是，可能在遍歷的過程中讀到一些剛剛被刪除的對象。

註意點：

總結：

線程安全，讀操作時無鎖的ArrayList
底層數據結構是一個Object[]，初始容量為0，之後每增加一個元素，容量+1，數組複製一遍
增刪改上鎖、讀不上鎖
遍歷過程由於遍歷的只是全局數組的一個副本，即使全局數組發生了增刪改變化，副本也不會變化，所以不會發生併發異常
讀多寫少且臟數據影響不大的併發情況下，選擇CopyOnWriteArrayList

疑問：

每增加一個新元素，都要進行一次數組的複製消耗，那為什麼每次不將數組的元素設大（比如說像ArrayList那樣，設置為原來的1.5倍+1），這樣就會大大減少因為數組元素複製所帶來的消耗？
get(int)操作會發生臟讀，為什麼？