深入Java集合学习系列：CopyOnWriteArrayList详解

http://my.oschina.net/jielucky/blog/167198

http://my.oschina.net/summerpxy/blog/405728

CopyOnWriteArrayList是ArrayList 的一个线程安全的变体，其中所有可变操作（add、set等等）都是通过对底层数组进行一次新的复制来实现的。

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

    内存一致性效果：当存在其他并发 collection 时，将对象放入CopyOnWriteArrayList之前的线程中的操作 happen-before 随后通过另一线程从CopyOnWriteArrayList中访问或移除该元素的操作。 

   这种情况一般在多线程操作时，一个线程对list进行修改。一个线程对list进行fore时会出现java.util.ConcurrentModificationException错误。

   下面来看一个列子：两个线程一个线程fore一个线程修改list的值。

package com.lucky.concurrent.list;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class CopyOnWriteArrayListDemo {
    /**
     * 读线程
     * @author wangjie
     *
     */
    private static class ReadTask implements Runnable {
        List<String> list;

        public ReadTask(List<String> list) {
            this .list = list;
        }

        public void run() {
            for (String str : list) {
                System.out.println(str);
            }
        }
    }
    /**
     * 写线程
     * @author wangjie
     *
     */
    private static class WriteTask implements Runnable {
        List<String> list;
        int index;

        public WriteTask(List<String> list, int index) {
            this .list = list;
            this .index = index;
        }

        public void run() {
            list.remove(index);
            list.add(index, "write_" + index);
        }
    }

    public void run() {
        final int NUM = 10 ;
        List<String> list = new ArrayList<String>();
        for ( int i = 0 ; i < NUM; i++) {
            list.add( "main_" + i);
        }
        ExecutorService executorService = Executors.newFixedThreadPool(NUM);
        for ( int i = 0 ; i < NUM; i++) {
            executorService.execute( new ReadTask(list));
            executorService.execute( new WriteTask(list, i));
        }
        executorService.shutdown();
    }

    public static void main(String[] args) {
        new CopyOnWriteArrayListDemo().run();
    }
}

运行结果： 

从结果中可以看出来。在多线程情况下报错。其原因就是多线程操作结果：那这个种方案不行我们就换个方案。用jdk自带的类CopyOnWriteArrayList来做容器。这个类和ArrayList最大的区别就是add(E) 的时候。容器会自动copy一份出来然后再尾部add(E)。看源码：

/**
    * Appends the specified element to the end of this list.
    *
    * @param e element to be appended to this list
    * @return <tt>true</tt> (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();
   }
   }

用到了Arrays.copyOf 方法。这样导致每次操作的都不是同一个引用。也就不会出现java.util.ConcurrentModificationException错误。
换了种方案看代码：

//      List<String> list = new ArrayList<String>();
        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();

也就把容器list换成了  CopyOnWriteArrayList，其他的没变。 线程里面的list不用改。因为  CopyOnWriteArrayList实现的也是list<E> 接口。看结果：

其结果没报错。
CopyOnWriteArrayList add(E) 和remove(int index)都是对新的数组进行修改和新增。所以在多线程操作时不会出现java.util.ConcurrentModificationException错误。
所以最后得出结论：CopyOnWriteArrayList适合使用在读操作远远大于写操作的场景里，比如缓存。发生修改时候做copy，新老版本分离，保证读的高性能，适用于以读为主的情况。

     CopyOnWriteArrayList类是高效的线程安全的类。线程安全是因为该类对于所有的修改方法都使用了加锁操作。高效是因为对于迭代操作是对原有集合的引用，避免了同步的开销。

     

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

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

   这两个成员变量是该类的核心，对集合所有的修改操作都需要使用lock加锁，array则是整个集合的数据储存部分，关键在于该array被声明为volatile，当一个线程对与线程中array副本的修改会立即同步到主内存中该变量中去。

  

 public  CopyOnWriteArrayList(Collection<?  extends  E> c) {
        Object[] elements = c.toArray();
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if  (elements.getClass() != Object[]. class )
            elements = Arrays.copyOf(elements, elements.length, Object[]. class );
        setArray(elements);
    }

再来看构造函数，构造函数会将传进来的集合通过Arrays.copyOf()方法转换成一个Object类型的数组，并用array成员变量存储起来。

再来说说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.lock()方法对代码块加锁，通过比较index和length之间的位置，判断出需要移位的数目，最后通过System.arraycopy()方法，重新生产一个新的newElements数组，然后将该数组传递给array成员变量保存。

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

而get方法则是取得该线程当前拥有的array数组，不需要额外的同步开销。

为什么get方法不需要同步呢？这正是CopyOnWriteArrayList的高效之处，在多线程环境下，每一个线程中都有一个主内存中变量的拷贝，该拷贝反映的是此时此刻主内存中该集合的情况。当线程开始运行时，一个线程会修改该集合，例如使用add方法，这个时候该线程内部的array变量就会修改，由于该变量是volatile的，所以此时该线程中修改的值会被立即同步到主内存中该变量中去。但是如果一个线程是在这个修改之前创建的，那么该线程内部所拥有的程序变量array还是改变之前的。所有对于CopyOnWriteArrayList类中的读取操作可能并不能真实的反映出此时此刻主内存块中的变量的情况，因此也不需要同步的开销。