您现在的位置是：首页 > 文章详情

Java并发编程笔记之CopyOnWriteArrayList源码分析

日期：2018-06-08点击：263收藏

并发包中并发List只有CopyOnWriteArrayList这一个，CopyOnWriteArrayList是一个线程安全的ArrayList,对其进行修改操作和元素迭代操作都是在底层创建一个拷贝数组（快照）上进行的，也就是写时拷贝策略。

我们首先看一下CopyOnWriteArrayList的类图有哪些属性和方法，如下图所示：

如上，CopyOnWriteArrayList的类图，每个CopyOnWriteArrayList对象里面有一个array数组对象用来存放具体元素，ReentrantLock独占锁对象用来保证同时只有一个线程对array进行修改，这里只要记得ReentrantLock是独占锁，同时只有一个线程可以获取就可以了。

那么问题来了，如果让我们自己去做一个写时拷贝的线程安全的List，我们会怎么做，要考虑哪些要点？

1.list何时初始化，初始化list元素个数为多少，list是有限大小？

2.如何保证线程安全，比如多个线程进行读写时候，如果保证是线程安全的？

3.如何使用迭代器遍历list时候的数据一致性？

那么我们就进入CopyOnWriteArrayList源码去看，看看设计者是如何处理的。

CopyOnWriteArrayList源码分离如下：

1.初始化，首先看一下CopyOnWriteArrayList的无参构造函数，如下代码内部创建了一个大小为0的Object数据作为array的初始值。源码如下：

 public CopyOnWriteArrayList() { setArray(new Object[0]); }

接下来再看看CopyOnWriteArrayList的有参构造函数，源码如下：

 //创建一个list，其内部元素是入参toCopyIn的拷贝 public CopyOnWriteArrayList(E[] toCopyIn) { setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class)); }
 //入参为集合，拷贝集合里面元素到本list public CopyOnWriteArrayList(Collection<? extends E> c) { Object[] elements; if (c.getClass() == CopyOnWriteArrayList.class) elements = ((CopyOnWriteArrayList<?>)c).getArray(); else { 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); }

2.添加元素，CopyOnWriteArrayList中添加元素函数有add(E e) ， add(int index , E element) ，addIfAbsent(E e) ， addAllAbsent(Collection<? extends E> c) 等操作，原理一致，

接下来就以add(E e)进行讲解。源码如下：

public boolean add(E e) { //加独占锁（1） final ReentrantLock lock = this.lock; lock.lock(); try { //获取array(2) Object[] elements = getArray(); //拷贝array到新数组，添加元素到新数组(3) int len = elements.length; Object[] newElements = Arrays.copyOf(elements, len + 1); newElements[len] = e; //使用新数组替换添加前的数组(4)  setArray(newElements); return true; } finally { //释放独占锁(5) lock.unlock(); } }

如上代码，调用add方法的线程会首先执行代码（1）去获取独占锁，如果多个线程都调用add则只有一个线程会获取该锁，其他线程会被阻塞挂起知道锁被释放。所以一个线程获取到锁后，就保证了在该线程添加元素过程中，其他线程不会对array进行修改。

线程获取锁后执行代码（2）获取array，然后执行代码（3）拷贝array到一个新数组（从这里可以知道新数组的大小是原来数组大小加增加1，所以CopyOnWriteArrayList是无界List），并把要新增的元素添加到新数组。

然后执行到代码（4）把新数组替换原数组，然后返回前要释放锁，由于加了锁，所以整个add过程是个原子操作，需要注意的是添加元素时候首先是拷贝了一个快照，然后在快照上进行的添加，而不是直接在源来的数组上进行。

3.获取指定位置元素，E get(int index)获取下标为index的元素，如果元素不存在会抛出IndexOutOfBoundsException 异常，源码如下：

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

如上代码，获取指定位置的元素分为两步，首先获取到当前list里面的array数组，这里称为步骤1，然后通过随机访问的下标方式访问指定位置的元素，这里称为步骤2。

从代码中可以看到整个过程并没有加锁，这就可能会导致当执行完步骤1后执行步骤2前，另外一个线程C进行了修改操作，比如remove操作，就会进行写时拷贝删除当前get方法要访问的元素，并且修改当前list的array为新数组。

而这之后步骤2 可能才开始执行，步骤2操作的是线程C删除元素前的一个快照数组（因为步骤1让array指向的是原来的数组），所以虽然线程C已经删除了index处的元素，但是步骤2还是返回index处的元素，这其实就是写时拷贝策略带来弱一致性。

4.修改指定元素，修改 list 中指定元素的值，如果指定位置的元素不存在则抛出 IndexOutOfBoundsException 异常，源码码如下：

 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  setArray(elements); } return oldValue; } finally { lock.unlock(); } }

如上代码，首先获取了独占锁控制了其他线程对array数组的修改，然后获取当前数组，并调用get方法获取指定位置元素。

如果指定的位置元素与新值不一致则创建新数组并拷贝元素，在新数组上修改指定位置元素值并设置新数组到array。

如果指定位置元素与新值一样，则为了保障volatile语义，还是需要重新设置下array，虽然array内容并没有改变(为了保证 volatile 语义是考虑到 set 方法本身应该提供 volatile 的语义）.

5.删除元素，删除list里面指定的元素，主要的方法有如下方法：

E remove(int index)

boolean remove(Object o)

boolean remove(Object o, Object[] snapshot, int index) 等方法，原理一致，这里讲解下 remove(int index) 方法，源码如下：

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

正如上面代码所示，其实和新增元素时候是类似的，首先是获取独占锁保证删除数组期间，其他线程不能对array进行修改，然后获取数组中要给删除的元素，并把剩余的原始拷贝到新数组后，把新数组替换原来的数组，最后在返回前释放锁。

6.接下来要讲解一下弱一致性的迭代器。

遍历列表元素可以使用迭代器进行迭代操作，讲解什么是迭代器的弱一致性前先上一个例子说明下迭代器的使用。代码如下：

import java.util.concurrent.CopyOnWriteArrayList; /** * Created by cong on 2018/6/9. */ public class CopyOnWriteArrayListTest { public static void main( String[] args ) { CopyOnWriteArrayList<String> arrayList = new CopyOnWriteArrayList<>(); arrayList.add("hello"); arrayList.add("java"); Iterator<String> itr = arrayList.iterator(); while(itr.hasNext()){ System.out.println(itr.next()); } } }

运行结果如下：

其中迭代器的hasNext方法用来判断是否还有元素，next方法则是具体返回元素。那么接下来看CopyOnWriteArrayList中迭代器是弱一致性，所谓弱一致性是指返回迭代器后，其他线程对list的增删改对迭代器不可见，无感知的，那么下面就看看是如何做到的。源码如下：

public Iterator<E> iterator() { return new COWIterator<E>(getArray(), 0); } static final class COWIterator<E> implements ListIterator<E> { //array的快照版本 private final Object[] snapshot; //数组下标 private int cursor; //构造函数 private COWIterator(Object[] elements, int initialCursor) { cursor = initialCursor; snapshot = elements; } //是否遍历结束 public boolean hasNext() { return cursor < snapshot.length; } //获取元素 public E next() { if (! hasNext()) throw new NoSuchElementException(); return (E) snapshot[cursor++]; }
 }

如上代码当调用iterator()方法获取迭代器时候实际是返回一个COWIterator对象，COWIterator的snapshot变量保存了当前list的内容，cursor是遍历list数据的下标。

这里为什么说snapshot是list的快照呢？明明是指针传递的引用，而不是拷贝。如果在该线程使用返回的迭代器遍历元素的过程中，其他线程没有对list进行增删改，那么snapshot本身就是list的array,因为它们是引用关系。

但是如果遍历期间，有其他线程对该list进行了增删改，那么snapshot就是快照了，因为增删改后list里面的数组被新数组替换了，这时候老数组只有被snapshot索引用，所以这也就说明获取迭代器后，使用改迭代器进行变量元素时候，其它线程对该list进行的增删改是不可见的，

因为它们操作的是两个不同的数组，这也就是弱一致性的达成。

下面通过一个例子来演示多线程下，迭代器的弱一致性的效果：代码如下：

import java.util.Iterator; import java.util.concurrent.CopyOnWriteArrayList; /** * Created by cong on 2018/6/9. */ public class CopyOnWriteArrayListTest { private static volatile CopyOnWriteArrayList<String> arrayList = new CopyOnWriteArrayList<>(); public static void main( String[] args ) throws InterruptedException { arrayList.add("hello"); arrayList.add("Java"); arrayList.add("welcome"); arrayList.add("to"); arrayList.add("hangzhou"); Thread threadOne = new Thread(new Runnable() { @Override public void run() { //修改list中下标为1的元素为JavaSe arrayList.set(1, "JavaSe"); //删除元素 arrayList.remove(2); arrayList.remove(3); } }); //保证在修改线程启动前获取迭代器 Iterator<String> itr = arrayList.iterator(); //启动线程  threadOne.start(); //等在子线程执行完毕  threadOne.join(); //迭代元素 while(itr.hasNext()){ System.out.println(itr.next()); } } }