并发容器分析（一）--CopyOnWriteArrayList

一、简介

    JDK5中添加了新的concurrent包，其中包含了很多并发容器，这些容器针对多线程环境进行了优化，大大提高了容器类在并发环境下的执行效率。

    CopyOnWriteArrayList类是一个线程安全的List接口的实现，在该类的内部进行元素的写操作时，底层的数组将被完整的复制，这对于读操作远远多于写操作的应用非常适合。在CopyOnWriteArrayList上进行操作时，读操作不需要加锁，而写操作类实现中对其进行了加锁。

二、具体实现

    CopyOnWriteArrayList底层的定义如下：

public class CopyOnWriteArrayList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    private volatile transient E[] array;

    private E[] array() { return array; }

    // 该操作是加锁的，防止array在copy的时候被替换 
    private synchronized void copyIn(E[] toCopyIn, int first, int n) {
        array  = (E[]) new Object[n];
        System.arraycopy(toCopyIn, first, array, 0, n);
    }

  ...
}

    读写操作：

public class CopyOnWriteArrayList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    public E get(int index) {
     // 由于包括rangeCheck和index两个操作，并不是直接在array上执行
   // 而是使用本地变量elementData引用array数组，防止两个操作之间
   // array被替换
     E[] elementData = array();
        rangeCheck(index, elementData.length);
        return elementData[index];
    }
    
    public synchronized E set(int index, E element) { // 是同步的
        int len = array.length;
        rangeCheck(index, len);
        E oldValue = array[index];

        // 判断该写的元素与原数据是否相同
        boolean same = (oldValue == element ||
        (element != null && element.equals(oldValue)));
        
        if (!same) {
            // [1] 创建一个新数组，将原array的值拷贝至新数组
        E[] newArray = (E[]) new Object[len];
            System.arraycopy(array, 0, newArray, 0, len);
            // [2] set的元素
        newArray[index] = element;
            // [3] 替换底层array数组
        array = newArray;
        }
        return oldValue;
    }

  ...
}

    add和remove也采用相同的技术：

public class CopyOnWriteArrayList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    public synchronized boolean add(E element) {
        // [1] new and copy
        int len = array.length;
        E[] newArray = (E[]) new Object[len+1];
        System.arraycopy(array, 0, newArray, 0, len);
        // [2] add element
        newArray[len] = element;
        // [3] change base array
        array = newArray;
        return true;
    }

    public synchronized E remove(int index) {
        int len = array.length;
        rangeCheck(index, len);
        E oldValue = array[index];
        // new一个新的数组
      E[] newArray = (E[]) new Object[len-1];
        // copy index之前的元素
      System.arraycopy(array, 0, newArray, 0, index);
        // copy余下的元素
      int numMoved = len - index - 1;
        if (numMoved > 0)
            System.arraycopy(array, index+1, newArray, index, numMoved);
        // 替换array引用    
     array = newArray;
        return oldValue;
    }

  ...
}

   特别注意：在CopyOnWriteArrayList上获得的Iterator是不能进行set和remove操作的，否则会抛出异常。