这是我参与8月更文挑战的第12天，活动详情查看：8月更文挑战

CopyOnWriteArrayList

属于JUC中的类

类头声明

 public class CopyOnWriteArrayList<E>
     implements List<E>, RandomAccess, Cloneable, java.io.Serializable
复制代码

类变量

 final transient ReentrantLock lock = new ReentrantLock();
 ​
 private transient volatile Object[] array;
复制代码

初始化代码块

 private void resetLock() {
     UNSAFE.putObjectVolatile(this, lockOffset, new ReentrantLock());
 }
 private static final sun.misc.Unsafe UNSAFE;
 private static final long lockOffset;
 static {
     try {
         UNSAFE = sun.misc.Unsafe.getUnsafe();
         Class<?> k = CopyOnWriteArrayList.class;
         lockOffset = UNSAFE.objectFieldOffset
             (k.getDeclaredField("lock"));
     } catch (Exception e) {
         throw new Error(e);
     }
 }
复制代码

方法

构造方法

 public CopyOnWriteArrayList() {
     setArray(new Object[0]);
 }
 ​
 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);
 }
 ​
 final void setArray(Object[] a) {
     array = a;
 }
 ​
 public CopyOnWriteArrayList(E[] toCopyIn) {
     setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
 }
复制代码

看到：

  elements = ((CopyOnWriteArrayList<?>)c).getArray();
  ......
  setArray(elements);
  }
复制代码

显然会有个问题：

• 如果是从相同的 CopyOnWriteArrayList创建而来，那么两个容器中的数组指向的是同一个数组：可以写一个demo来验证这一点。

如何保证从其他的CopyOnWriteArrayList创建而来的容器，是相对隔离可用的呢？【答案：快照】

基本方法

此处的基本方法，指的是：

• get
• set
• add
• remove

以及其他数组托管容器应该实现的基本操作。

get方法

 private E get(Object[] a, int index) {
         return (E) a[index];
     }
 ​
 public E get(int index) {
     return get(getArray(), index);
 }
复制代码

get方法本身是原子性的，也不会对其他操作产生影响，因此不做任何lock和copy操作。

set方法

 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();
     }
 }
复制代码

从这段代码上看，set方法做了如下工作

• 对于该容器对象而言，set方法是加锁的。

• set方法对新旧值做了比较

  • 如果是新旧值不相等（此处用的相等是**=而非equals**，对于对象而言指的是地址），那么会：

    • 复制一份新的数组
    • 新数组的目标索引处的值修改为目标值
    • 将托管的数组设置为新的数组

  • 如果不相等，那么将elements数组再塞回去。原因：

    • Not quite a no-op; ensures volatile write semantics,即：保证volatile写语义

    • 在这篇博客中详细介绍了为什么：是为了保证happens-before原则。
    • 这个地方将变量再塞回去，保证了外部（调用该方法的地方）的上下文不会被CPU进行重排序。

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();
     }
 }
 ​
 //指定索引位置插入
     public void add(int index, E element) {
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
             Object[] elements = getArray();
             //length和index的关系就不用多说了8
             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 {
                 //如果不是：前后复制，将index的地方空出来
                 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();
         }
     }
复制代码

add方法中，同样做了2个工作，保证该操作在多线程下的准确性：

• 使用ReentrantLock上锁
• 复制扩容数组（长度+1），在将扩容后的最后一位设置为目标对象后，将托管数组设置为新的数组。

remove方法

 //已知索引位置
 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();
     }
 }
 ​
 //目标删除
 public boolean remove(Object o) {
     Object[] snapshot = getArray();
     int index = indexOf(o, snapshot, 0, snapshot.length);
     return (index < 0) ? false : remove(o, snapshot, index);
 }
 ​
 //上面方法的一部分
 private boolean remove(Object o, Object[] snapshot, int index) {
     final ReentrantLock lock = this.lock;
     lock.lock();
     try {
         Object[] current = getArray();
         int len = current.length;
         if (snapshot != current) findIndex: {
             int prefix = Math.min(index, len);
             for (int i = 0; i < prefix; i++) {
                 if (current[i] != snapshot[i] && eq(o, current[i])) {//--------1
                     index = i;
                     break findIndex;
                 }
             }
             if (index >= len)
                 return false;
             if (current[index] == o)//------------------2
                 break findIndex;
             index = indexOf(o, current, index, len);//---------------3
             if (index < 0)
                 return false;
         }
         Object[] newElements = new Object[len - 1];
         System.arraycopy(current, 0, newElements, 0, index);
         System.arraycopy(current, index + 1,
                          newElements, index,
                          len - index - 1);
         setArray(newElements);
         return true;
     } finally {
         lock.unlock();
     }
 }
 ​
 //indexOf就不介绍了，使用for循环和==（null值）/equals（非null值）进行比较并返回索引位置
复制代码

remove方法也做了和上述两个方法相同的操作：

• 上锁
• 复制数组

在查找-remove的方法中，有一个小细节：

• 如果查找到了，进了remove具体方法再上锁，且入参中包含了查找时的数组快照。

• 如果快照和当前的托管数组不同，就进行比较：

  • 只有当前数组包含要remove的元素时才会进行下一步操作。（1，2，3）

使用了label代码块的技巧，快速跳出判断。

增强list方法

还有一些基于list的增强方法，例如：

 removeRange(int fromIndex, int toIndex)//上锁，判断，拷贝
 ​
 ​
 //查找索引，为-1才上锁
 //如果上锁后发现快照不一致，快照前后数组list一一比较，如果有前后不同且和e相同的，就返回
     public boolean addIfAbsent(E e) {
         Object[] snapshot = getArray();
         return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
             addIfAbsent(e, snapshot);
     }
 ​
  private boolean addIfAbsent(E e, Object[] snapshot) {
         final ReentrantLock lock = this.lock;
         lock.lock();
         try {
             Object[] current = getArray();
             int len = current.length;
             if (snapshot != current) {
                 // Optimize for lost race to another addXXX operation
                 int common = Math.min(snapshot.length, len);
                 for (int i = 0; i < common; i++)
                     if (current[i] != snapshot[i] && eq(e, current[i]))
                         return false;
                 if (indexOf(e, current, common, len) >= 0)
                         return false;
             }
             Object[] newElements = Arrays.copyOf(current, len + 1);
             newElements[len] = e;
             setArray(newElements);
             return true;
         } finally {
             lock.unlock();
         }
     }
复制代码

Iterator

内部类定义

 static final class COWIterator<E> implements ListIterator<E> {
     /** Snapshot of the array */
     private final Object[] snapshot;
     /** Index of element to be returned by subsequent call to next.  */
     private int cursor;
 ​
     private COWIterator(Object[] elements, int initialCursor) {
         cursor = initialCursor;
         snapshot = elements;
     }
  ...
 }
复制代码

• 同样基于数组的特性，提供了往前/往后的遍历功能。

• 只能做遍历，不支持删除/设置/添加的操作：

   public void remove() {
       throw new UnsupportedOperationException();
   }
   public void set(E e) {
               throw new UnsupportedOperationException();
           }
   public void add(E e) {
           throw new UnsupportedOperationException();
           }
  复制代码

SubList

获取方法

 public List<E> subList(int fromIndex, int toIndex) {
     final ReentrantLock lock = this.lock;
     lock.lock();
     try {
         Object[] elements = getArray();
         int len = elements.length;
         if (fromIndex < 0 || toIndex > len || fromIndex > toIndex)
             throw new IndexOutOfBoundsException();
         return new COWSubList<E>(this, fromIndex, toIndex);
     } finally {
         lock.unlock();
     }
 }
复制代码

类定义

 private static class COWSubList<E>
     extends AbstractList<E>
     implements RandomAccess
 {
     private final CopyOnWriteArrayList<E> l;
     private final int offset;
     private int size;
     private Object[] expectedArray;
 ​
     // only call this holding l's lock
     COWSubList(CopyOnWriteArrayList<E> list,
                int fromIndex, int toIndex) {
         l = list;
         expectedArray = l.getArray();
         offset = fromIndex;
         size = toIndex - fromIndex;
     }
     //ArrayList里，是用modCount进行异步修改检查的
     private void checkForComodification() {
             if (l.getArray() != expectedArray)
                 throw new ConcurrentModificationException();
         }
     ...
 }
复制代码

对subList的操作，简单介绍如下：

• 无论是CRUD中的哪个种类，操作流程都是：

  • 取父对象的锁并上锁
  • 检查边界，检查异步编辑情况
  • 调用父对象的方法
  • 解锁

线程安全问题

COWArrayList并不能完全避免线程安全问题。

原因：

• 在get方法中：并不检查index，只是根据当前Array，获取当前Array的某个索引上的数据。

• remove方法中：copy数组后赋值。

• 所以存在这种可能：

  • 线程1进入get方法，index = size-1，该位置有值。
  • 线程2进入remove方法，线程1挂起，修改了数组的大小为size-1。
  • 线程2结束，线程1获得时间片继续运行，此时线程1的index值已是非法的值，发生了越界的error。
  • 当然，remove方法比get方法长这么多，同时get方法并不上锁，基本上remove方法很难在get方法挂起时获取的时间片中，完成整个流程，因此这个地方也是理论分析，正常情况下基本是不太可能发生这种事情。

• 虽然数组是volatile注释的，但是是在两个线程中，volatile并不能保证线程挂起的问题。

• 但源码中

  • 注释中明确标出get方法会抛出越界异常
  • 并且get方法并没有对边界的检查，因此可能设计时就考虑到了这种情况，只是并没有作为一个bug进行修复，只是作为一个常规的list的特性。