作者： 一字馬胡
轉(zhuǎn)載標志 【2017-11-03】

更新日志

CopyOnWriteArrayList

CopyOnWriteArrayList是ArrayList的線程安全版本，從他的名字可以推測，CopyOnWriteArrayList是在有寫操作的時候會copy一份數(shù)據(jù)，然后寫完再設(shè)置成新的數(shù)據(jù)。CopyOnWriteArrayList適用于讀多寫少的并發(fā)場景，CopyOnWriteArraySet是線程安全版本的Set實現(xiàn)，它的內(nèi)部通過一個CopyOnWriteArrayList來代理讀寫等操作，使得CopyOnWriteArraySet表現(xiàn)出了和CopyOnWriteArrayList一致的并發(fā)行為，他們的區(qū)別在于數(shù)據(jù)結(jié)構(gòu)模型的不同，set不允許多個相同的元素插入容器中，具體的細節(jié)將在下文中分析。

CopyOnWriteArrayList類圖

上面的圖片展示你了CopyOnWriteArrayList的類圖，可以看到它實現(xiàn)了List接口，如果去看ArrayList的類圖的話，可以發(fā)現(xiàn)也是實現(xiàn)了List接口，也就得出一句廢話，ArrayList提供的api，CopyOnWriteArrayList也提供，下文中來分析CopyOnWriteArrayList是如何來做到線程安全的實現(xiàn)讀寫數(shù)據(jù)的，而且也會順便對比ArrayList的等效實現(xiàn)為什么不支持線程安全的。下面首先展示了CopyOnWriteArrayList中比較重要的成員：

    /** The lock protecting all mutators */
    final transient ReentrantLock lock = new ReentrantLock();

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

可以看到，CopyOnWriteArrayList使用了ReentrantLock來支持并發(fā)操作，array就是實際存放數(shù)據(jù)的數(shù)組對象。ReentrantLock是一種支持重入的獨占鎖，任意時刻只允許一個線程獲得鎖，所以可以安全的并發(fā)去寫數(shù)組，關(guān)于java中鎖的細節(jié)，可以參考文章Java可重入鎖詳解。接下來看一下CopyOnWriteArrayList是如何使用這個lock來實現(xiàn)并發(fā)寫的，下面首先展示了add方法的代碼：

    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock(); //上鎖，只允許一個線程進入
        try {
            Object[] elements = getArray(); // 獲得當(dāng)前數(shù)組對象
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);//拷貝到一個新的數(shù)組中
            newElements[len] = e;//插入數(shù)據(jù)元素
            setArray(newElements);//將新的數(shù)組對象設(shè)置回去
            return true;
        } finally {
            lock.unlock();//釋放鎖
        }
    }

為了對比ArrayList，下面展示了ArrayList中的add方法的細節(jié)：

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }        

相比CopyOnWriteArrayList，ArrayList的add方法實現(xiàn)就顯得啰嗦的多，而且ArrayList并不支持線程安全，至于為什么不支持線程安全，看代碼就知道了，這幾個調(diào)用的方法中都沒有類似鎖（與鎖等效語義的組件）出現(xiàn)。下面再來看另一個版本的add方法：

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

在操作之前都是先lock住的，這里面有一個有意思的地方，因為該方法可以指定index來插入value，如果這個index位置上已經(jīng)有舊值，那么該方法的作用類似replace，如果該index為當(dāng)前數(shù)組的長度，那么該方法和上面分析的add方法等效，現(xiàn)在分析一下index位置上已經(jīng)有值的情況，會分為兩段copy，然后在中間設(shè)置新值?，F(xiàn)在來分析一下讀操作，下面是get方法的細節(jié)：

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

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

可以發(fā)現(xiàn)是非常簡單的，而且讀是允許多個線程進入的。下面來分析一下CopyOnWriteArrayList提高的迭代器。下面是兩個重要的變量：

        /** Snapshot of the array */
        private final Object[] snapshot;
        /** Index of element to be returned by subsequent call to next.  */
        private int cursor;

遍歷的時候首先會獲得當(dāng)前數(shù)組對象的一個拷貝，稱為快照，然后遍歷的操作會在該快照上進行，那如果獲取了迭代器之后再對CopyOnWriteArrayList進行寫操作會怎么樣？迭代器能感知到這種變化嗎？下面實際實驗一下：

        CopyOnWriteArrayList<String> copyOnWriteArrayList = new CopyOnWriteArrayList<>();

        copyOnWriteArrayList.add("first");
        copyOnWriteArrayList.add("second");

        Iterator<String> iterator = copyOnWriteArrayList.iterator();

        copyOnWriteArrayList.add("third");

        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        
        //output:
        
        first
        second

結(jié)果是不能感知，也就是說，這個快照并不會和外界有任何聯(lián)系，某個線程在獲取迭代器的時候就會拷貝一份，或者說，每一個線程都將獲得當(dāng)前時刻的一個快照，所以不需要加鎖就可以安全的實現(xiàn)遍歷，下面的代碼也證實了上面的說法：

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

CopyOnWriteArraySet

CopyOnWriteArraySet使用一個CopyOnWriteArrayList來做代理，它的所有api都是依賴于CopyOnWriteArrayList來實現(xiàn)的，下面的代碼也展示了這種代理的事實：

    private final CopyOnWriteArrayList<E> al;

    /**
     * Creates an empty set.
     */
    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }

下面來分析一下CopyOnWriteArraySet的寫操作實現(xiàn)，比如add方法：

    public boolean add(E e) {
        return al.addIfAbsent(e);
    }
    
    public boolean addIfAbsent(E e) {
        Object[] snapshot = getArray();
        return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
            addIfAbsent(e, snapshot);
    }
    
    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();
        }
    }    

set是一種不允許有重復(fù)元素的簡單數(shù)據(jù)結(jié)構(gòu)，所以和CopyOnWriteArrayList不同，CopyOnWriteArraySet需要add在插入新元素的時候多做一些判斷，而CopyOnWriteArraySet在實現(xiàn)上使用了CopyOnWriteArrayList的addIfAbsent方法，這個方法的意思就是如果存在就不再插入，如果不存在再進行插入。

本人分析了CopyOnWriteArrayList的實現(xiàn)細節(jié)，并且分析了基于CopyOnWriteArrayList實現(xiàn)的CopyOnWriteArraySet，介于CopyOnWriteArrayList的簡單性，本文沒有太多亮點，但是理解CopyOnWriteArrayList的實現(xiàn)細節(jié)是有必要的，在并發(fā)環(huán)境下，我們在選擇對象容器的時候需要考量是否需要選擇線程安全的容器，如果不需要，則優(yōu)先選擇ArrayList等沒有線程安全保障的容器，如果需要線程安全保障，那么必須選擇類似CopyOnWriteArrayList的線程安全的容器集合，否則會造成不可預(yù)料的錯誤。當(dāng)然，實現(xiàn)線程安全的代價是以損失部分性能為代價的，畢竟有l(wèi)ock-unlock的操作，但是這又是必須的。接下來的文章會分析一些java中實現(xiàn)的線程安全的容器，比如ConcurrentHashMap等，當(dāng)然，也會對類似HashMap之類的非線程安全的容器集合進行分析總結(jié)，畢竟類似HashMap這樣的容器集合是我們經(jīng)常使用的，理解他的具體實現(xiàn)有助于我們更好的使用它。