《Java源码分析》：CopyOnWriteArrayList/CopyOnWriteArraySet

CopyOnWriteArrayList/CopyOnWriteArraySet的基本思想是一旦对容器有修改，那么就“复制”一份新的集合，在新的集合上修改，然后将新集合复制给旧的引用。当然了这部分少不了要加锁。显然对于CopyOnWriteArrayList/CopyOnWriteArraySet来说最大的好处就是“读”操作不需要锁了。

CopyOnWriteArrayList是ArrayList 的一个线程安全的变体，其中所有可变操作（add、set 等等）都是通过对底层数组进行一次新的复制来实现的。这一般需要很大的开销，但是当遍历操作的数量大大超过可变操作的数量时，这种方法可能比其他替代方法更有效。在不能或不想进行同步遍历，但又需要从并发线程中排除冲突时，它也很有用。“快照”风格的迭代器方法在创建迭代器时使用了对数组状态的引用。此数组在迭代器的生存期内不会更改，因此不可能发生冲突，并且迭代器保证不会抛出 ConcurrentModificationException。创建迭代器以后，迭代器就不会反映列表的添加、移除或者更改。在迭代器上进行的元素更改操作（remove、set 和 add）不受支持。这些方法将抛出 UnsupportedOperationException。

这个类确实比较简单，在一些可变操作下通过加锁并对底层数组进行一次复制来实现。下面我们就简单的看下源码。

CopyOnWriteArrayList构造函数

CopyOnWriteArrayList的底层还是基于数组来实现的，只是此时的数组采用volatile来修饰，来保证内存的一致性，即一个线程对array的修改对另一个线程可见，但不是立即可见。

private transient volatile Object[] array;

构造函数如下：

    public CopyOnWriteArrayList() {setArray(new Object[0]);}/*** Sets the array.*/final void setArray(Object[] a) {array = a;}

即初始对象构造了一个长度为零的List。

get方法

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

利用的数组的不可变性，get方法的操作数组都是某一时刻array的镜像。这样在高并发的情况下get方法和其它线程对该List的访问(无论是读操作还是写操作)都不会产生冲突。

另一些不加锁的方法contains/indexOf

    public int indexOf(Object o) {Object[] elements = getArray();//得到此时数组的一份镜像return indexOf(o, elements, 0, elements.length);}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;}//同indexOf一直public boolean contains(Object o) {Object[] elements = getArray();return indexOf(o, elements, 0, elements.length) >= 0;}

可变操作(add/set/remove)

下面为CopyOnWriteArrayList的一些可变操作的内部实现，可变操作都是采用的如下的思想：

1、加锁

2、将原来的数组copy一份到新数组中，然后修改

3、将旧的引用array指向新数组。

4、释放锁

由于源码都比较简单好懂，这里就不解释了。

    /*** Appends the specified element to the end of this list.** @param e element to be appended to this list* @return {@code true} (as specified by {@link Collection#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();}}/*** Inserts the specified element at the specified position in this* list. Shifts the element currently at that position (if any) and* any subsequent elements to the right (adds one to their indices).** @throws IndexOutOfBoundsException {@inheritDoc}*/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();}}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();}}/*** Replaces the element at the specified position in this list with the* specified element.** @throws IndexOutOfBoundsException {@inheritDoc}*/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 {// Not quite a no-op; ensures volatile write semantics 确保语义/*为了保持“volatile”的语义，任何一个读操作都应该是一个写操作的结果，也就是读操作看到的数据一定是某个写操作的结果（尽管写操作没有改变数据本身）。所以这里即使不设置也没有问题，仅仅是为了一个语义上的补充（就如源码中的注释所言）。*/setArray(elements);//写回，什么都没有改变，为什么还要写回了？这是因为}return oldValue;} finally {lock.unlock();}}

CopyOnWriteArraySet类分析

上面介绍了CopyOnWriteArrayList类的常见方法，比较简单。而CopyOnWriteArraySet就更简单了，因为，CopyOnWriteArraySet里面有一个CopyOnWriteArrayList的引用，即CopyOnWriteArraySet类里面的内部实现全部是委托给CopyOnWriteArrayList来实现的，只是额外的封装了下。

看如下的代码你就明白了。

    public class CopyOnWriteArraySet<E> extends AbstractSet<E>implements java.io.Serializable {
    private static final long serialVersionUID = 5457747651344034263L;private final CopyOnWriteArrayList<E> al;/*** Creates an empty set.*/public CopyOnWriteArraySet() {al = new CopyOnWriteArrayList<E>();}

小结

关于CopyOnWriteArrayList、CopyOnWriteArraySet，我们需要记住以下几点就好了

1、CopyOnWriteArrayList是ArrayList的线程安全的实现。

2、如何来实现线程安全的呢？底层的数组采用Volatile来声明的，对于可变操作采用加锁并对底层的数组进行拷贝一份，在新数组上进行修改，最后将旧引用指向这个新数组即可，对于不可变的操作，利用的数组的不可变性来完成的。