第5章 Java并发包中并发List源码剖析

    CopyOnWriteArrayList内部包含一个array：

    无参构造函数在内部创建了一个大小为0的object数组作为array的初始值

    2.     setArray(new Object[0]);
    3. }

    下面看有参构造函数：

    1. // 根据传入数组创建array对象
    2. public CopyOnWriteArrayList(E[] toCopyIn) {
    3.     setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
    4. }
    6. // 根据集合创建array对象
    7. public CopyOnWriteArrayList(Collection<? extends E> c) {
    8.     Object[] elements;
    9.     if (c.getClass() == CopyOnWriteArrayList.class)
    10.         elements = ((CopyOnWriteArrayList<?>)c).getArray();
    11.     else {
    12.         elements = c.toArray();
    13.         // c.toArray might (incorrectly) not return Object[] (see 6260652)
    14.         if (elements.getClass() != Object[].class)
    15.             elements = Arrays.copyOf(elements, elements.length, Object[].class);
    16.     }
    17.     setArray(elements);
    18. }

    关于“c.toArray might (incorrectly) not return Object[] (see 6260652)”的注释可参考。

    添加元素

    CopyOnWriteList中用来添加元素的函数有add(E e)、add(int index, E element)、addIfAbsent(E e)等，其原理类似，下面以add(E e)为例进行讲解。

    调用add方法的线程会首先获取独占锁，保证同时最多有一个线程调用此方法，其他线程会被阻塞直到锁被释放。

    获取array后将array复制到一个新数组（从代码可知新数组的长度比原长度大1，所以CopyOnWriteArrayList时无界list），并把新增的元素添加到新数组。

    1. public E get(int index) {
    2.     return get(getArray(), index);
    3. }
    5. private E get(Object[] a, int index) {
    6.     return (E) a[index];
    7. }
    9. final Object[] getArray() {
    10.     return array;
    11. }

    获取指定位置的元素需要两步：首先获取array，然后通过下标访问指定位置的元素。整个过程没有加锁，在多线程下会出现弱一致性问题。

    假设某一时刻CopyOnWriteArrayList中有1，2，3中三个元素，如下图所示：

    由于整个过程未加锁，可能导致一个线程x在获取array后，另一个线程y进行了remove操作，假设要删除的元素为3。remove操作首先会获取独占锁，然后进行写时复制操作，也就是复制一份当前array数组，然后再复制的数组里面删除线程x通过get方法要访问的元素3，之后让array指向复制的数组。而这时线程x仍持有对原来的array的引用，导致虽然线程y删除了元素3，线程x仍能获得3这个元素，如图：

    第5章 Java并发包中并发List源码剖析 - 图1

    修改指定元素

    使用E set(int index, E element)方法修改指定元素的值，如果指定位置的元素不存在则抛出IndexOutOfBoundsException异常：

    1. public E set(int index, E element) {
    2.     lock.lock();
    3.     try {
    4.         Object[] elements = getArray();
    5.         E oldValue = get(elements, index);
    7.         if (oldValue != element) {
    9.             Object[] newElements = Arrays.copyOf(elements, len);
    10.             newElements[index] = element;
    11.             setArray(newElements);
    12.         } else {
    13.             // Not quite a no-op; ensures volatile write semantics
    14.             setArray(elements);
    15.         }
    16.         return oldValue;
    17.     } finally {
    18.         lock.unlock();
    19.     }
    20. }

    首先获取独占锁，从而阻止其他线程对array数组进行修改，然后获取当前数组，并调用get方法获取指定位置的元素，如果指定位置的元素值与新值不一致就创建新数组并复制元素，然后在新数组上修改指定位置的元素值并设置新数组到array。即使指定位置的元素值与新值一样，为了保证volatile语义，也需要重新设置array（此处可参看《CopyOnWriteArrayList与java内存模型》）。

    首先获取独占锁以保证线程安全，然后获取要被删除的元素，并把剩余的元素复制到新数组，之后使用新数组替换原来的数组，最后在返回前释放锁。

    弱一致性的迭代器

    弱一致性指返回迭代器后，其他线程对list的改动对迭代器时不可见的。

    1. public Iterator<E> iterator() {
    2.     return new COWIterator<E>(getArray(), 0);
    3. }
    5. static final class COWIterator<E> implements ListIterator<E> {
    7.     // array的快照
    8.     private final Object[] snapshot;
    9.     // 数组下标
    10.     private int cursor;
    12.     private COWIterator(Object[] elements, int initialCursor) {
    13.         cursor = initialCursor;
    14.         snapshot = elements;
    15.     }
    17.     public boolean hasNext() {
    18.         return cursor < snapshot.length;
    19.     }
    21.     public E next() {
    22.         if (! hasNext())
    23.             throw new NoSuchElementException();
    24.     }
    25. }

    调用iterator()方法时实际上会返回一个COWIterator对象，COWIterator对象的snapshot变量保存了当前list的内容。之所以说snapshot是list的快照是因为虽然snapshot获得了array的引用，但当其他线程修改了list时，array会指向新复制出来的数组，而snapshot仍指向原来array指向的数组，两者操作不同的数组，这就是弱一致性。

    以下为弱一致性的示例：

    1. public class CopyListTest {
    4.     public static void main(String[] args) throws InterruptedException {
    5.         arrayList.add("Java");
    6.         arrayList.add("Scala");
    7.         arrayList.add("Groovy");
    8.         arrayList.add("Kotlin");
    10.         Thread threadOne = new Thread(new Runnable() {
    11.             @Override
    12.             public void run() {
    13.                 arrayList.set(0, "hello");
    14.                 arrayList.remove(2);
    15.             }
    16.         });
    18.         // 在修改之前获取迭代器
    19.         Iterator<String> it = arrayList.iterator();
    21.         threadOne.start();
    23.         // 等待子线程执行完毕
    24.         threadOne.join();
    26.         // 迭代
    27.         while(it.hasNext()) {
    28.             System.out.println(it.next());
    29.         }
    31.         System.out.println("=========================================");
    33.         // 再次迭代
    34.         it = arrayList.iterator();
    36.         // 迭代
    37.         while(it.hasNext()) {
    38.             System.out.println(it.next());
    39.         }
    40.     }

    输出如图：

    由上可知，对list的修改对于首次迭代是不可见的，这即是弱一致性的体现。