作者： 一字马胡
转载标志 【2017-11-03】

更新日志

日期	更新内容	备注
2017-11-03	添加转载标志	持续更新

CopyOnWriteArrayList

CopyOnWriteArrayList是ArrayList的线程安全版本，从他的名字可以推测，CopyOnWriteArrayList是在有写操作的时候会copy一份数据，然后写完再设置成新的数据。CopyOnWriteArrayList适用于读多写少的并发场景，CopyOnWriteArraySet是线程安全版本的Set实现，它的内部通过一个CopyOnWriteArrayList来代理读写等操作，使得CopyOnWriteArraySet表现出了和CopyOnWriteArrayList一致的并发行为，他们的区别在于数据结构模型的不同，set不允许多个相同的元素插入容器中，具体的细节将在下文中分析。

CopyOnWriteArrayList类图

上面的图片展示你了CopyOnWriteArrayList的类图，可以看到它实现了List接口，如果去看ArrayList的类图的话，可以发现也是实现了List接口，也就得出一句废话，ArrayList提供的api，CopyOnWriteArrayList也提供，下文中来分析CopyOnWriteArrayList是如何来做到线程安全的实现读写数据的，而且也会顺便对比ArrayList的等效实现为什么不支持线程安全的。下面首先展示了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来支持并发操作，array就是实际存放数据的数组对象。ReentrantLock是一种支持重入的独占锁，任意时刻只允许一个线程获得锁，所以可以安全的并发去写数组，关于java中锁的细节，可以参考文章Java可重入锁详解。接下来看一下CopyOnWriteArrayList是如何使用这个lock来实现并发写的，下面首先展示了add方法的代码：

    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();//释放锁
        }
    }

为了对比ArrayList，下面展示了ArrayList中的add方法的细节：

    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方法实现就显得啰嗦的多，而且ArrayList并不支持线程安全，至于为什么不支持线程安全，看代码就知道了，这几个调用的方法中都没有类似锁（与锁等效语义的组件）出现。下面再来看另一个版本的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位置上已经有旧值，那么该方法的作用类似replace，如果该index为当前数组的长度，那么该方法和上面分析的add方法等效，现在分析一下index位置上已经有值的情况，会分为两段copy，然后在中间设置新值。现在来分析一下读操作，下面是get方法的细节：

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

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

可以发现是非常简单的，而且读是允许多个线程进入的。下面来分析一下CopyOnWriteArrayList提高的迭代器。下面是两个重要的变量：

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

遍历的时候首先会获得当前数组对象的一个拷贝，称为快照，然后遍历的操作会在该快照上进行，那如果获取了迭代器之后再对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

结果是不能感知，也就是说，这个快照并不会和外界有任何联系，某个线程在获取迭代器的时候就会拷贝一份，或者说，每一个线程都将获得当前时刻的一个快照，所以不需要加锁就可以安全的实现遍历，下面的代码也证实了上面的说法：

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

CopyOnWriteArraySet

CopyOnWriteArraySet使用一个CopyOnWriteArrayList来做代理，它的所有api都是依赖于CopyOnWriteArrayList来实现的，下面的代码也展示了这种代理的事实：

    private final CopyOnWriteArrayList<E> al;

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

下面来分析一下CopyOnWriteArraySet的写操作实现，比如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是一种不允许有重复元素的简单数据结构，所以和CopyOnWriteArrayList不同，CopyOnWriteArraySet需要add在插入新元素的时候多做一些判断，而CopyOnWriteArraySet在实现上使用了CopyOnWriteArrayList的addIfAbsent方法，这个方法的意思就是如果存在就不再插入，如果不存在再进行插入。

本人分析了CopyOnWriteArrayList的实现细节，并且分析了基于CopyOnWriteArrayList实现的CopyOnWriteArraySet，介于CopyOnWriteArrayList的简单性，本文没有太多亮点，但是理解CopyOnWriteArrayList的实现细节是有必要的，在并发环境下，我们在选择对象容器的时候需要考量是否需要选择线程安全的容器，如果不需要，则优先选择ArrayList等没有线程安全保障的容器，如果需要线程安全保障，那么必须选择类似CopyOnWriteArrayList的线程安全的容器集合，否则会造成不可预料的错误。当然，实现线程安全的代价是以损失部分性能为代价的，毕竟有lock-unlock的操作，但是这又是必须的。接下来的文章会分析一些java中实现的线程安全的容器，比如ConcurrentHashMap等，当然，也会对类似HashMap之类的非线程安全的容器集合进行分析总结，毕竟类似HashMap这样的容器集合是我们经常使用的，理解他的具体实现有助于我们更好的使用它。