CopyOnWriteArrayList分析

ArrayList 是比较常用的一个可变大小的数组集合,但是是不能同步的。如果多个线程同时访问一个 ArrayList 实例,其中至少一个线程从结构上修改了列表,那么它必须保持外部同步。一般通过加锁对象进行同步操作来完成,如果不存在这样的对象,则应该使用 Collections.synchronizedList 方法将该列表“包装”起来:

List list = Collections.synchronizedList(new ArrayList(...));  

此类的 iteratorlistIterator 方法返回的迭代器是快速失败的:在创建迭代器之后,除非通过迭代器自身的 removeadd 方法从结构上对列表进行修改,否则在任何时间以任何方式对列表进行修改,迭代器都会抛出 ConcurrentModificationException。因此,面对并发的修改,迭代器会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。 CopyOnWriteArrayListArrayList 的一个线程安全的变体实现,即可在多线程并发环境中使用。而它的可变操作都是通过对 ArrayList 中存储的数组通过一次新的复制来实现的。 当对列表进行修改( add, remove 等)操作时,先 lock ,然后 copy 一份,也就是先复制一份当前的数据存储结构,然后进行相应的操作。这也就让 get 操作从同步中释放出来。因为对数据的改变会在副本中进行,所以不需要同步,只是有可能独到脏数据,但这对于某些应用来说,问题不大,适合于少量写大量读取的情况。

用法

CopyOnWriteArrayList 数据结构比较简单,举个例子介绍它的用法:

  List<String> list =new CopyOnWriteArrayList<String>();
  list.add("4");
  list.add("5");
  list.add("6");
  list.remove(2);
内部实现

CopyOnWriteArrayList 内部采用的存储结构是数组,且在操作时用 ReentrantLock 进行锁操作:

transient final ReentrantLock lock = new ReentrantLock();  
private volatile transient Object[] array;  

CopyOnWriteArrayList 提供了一些构造函数,下面是两个典型的函数

    public CopyOnWriteArrayList() {
        setArray(new Object[0]);//采用长度为0的数组
    }
    public CopyOnWriteArrayList(E[] toCopyIn) {
        setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
    }

Arrays.copyOf 内部使用 System.arraycopy 函数拷贝数据,因为 System.arraycopy 函数是 native 的,效率比自己写的数组拷贝效率高。

Get函数

比较简单,直接返回指定位置的元素。

    public E get(int index) {
        return (E)(getArray()[index]);
    }
add函数

add 函数添加之前,先加锁创建一个数组,数组长度在当前基础上加1,同时复制所有旧数组数据到新数组,然后在新数组的最后一个位置,添加新数据。然后将该新数组的引用赋予当前数组,最后解锁

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

remove 函数跟 add 函数过程相似:先创建一个新的数组(长度为 原来长度-1),然后复制元素两边的数据元素, 然后将该新数组的引用赋予当前数组,整个过程也是有锁的。

public E remove(int index) {

    final ReentrantLock lock = this.lock;

    lock.lock();

    try {

        Object[] elements = getArray();

        int len = elements.length;

        Object oldValue = 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 (E)oldValue;

    } finally {

        lock.unlock();

    }

}
比较ArrayList和CopyOnWriteArrayList

单线程:在元素较少的景象下,两个类的性能接近,当元素很多时,CopyOnWriteArrayList增长元素的操作会差一点。
多线程:跟着元素数量和线程数量的增长,CopyOnWriteArrayList在添加和删除元素的机能就会降落,并且比ArrayList机能低。但在查找元素时在元素数量和线程数量的增长的情况下性能比ArrayList好。

在读多写少的并发场景中,CopyOnWriteArrayList比ArrayList有着性能大的优势,是一个不错的选择。