【JUC并发编程】18 CopyOnWriteArrayList源码也就够看2分钟

1、CopyOnWriteArrayList概述

CopyOnWriteArrayList相当于线程安全的ArrayList，底层是一个可变数组。

特点如下：

1. 线程安全：基于ReentrantLock实现同步；
2. add/set/remove操作均是基于数组的copy进行；
3. 迭代器进行遍历的速度很快，不会与其他线程发生冲突；
4. 在迭代器上不允许进行的元素更改操作（remove、set和add），因为迭代器依赖于不变的数组快照。

适用于List 大小通常很小，只读操作远多于可变操作，并且需要在遍历期间防止线程冲突。

2、原理 / 源码

在⼤多数的应⽤场景中，读操作的⽐例远远⼤于写操作。当执⾏读操作的时候，对数据是没有修改的，所以，⽆须对数据进⾏加锁操作。⽽针对于写操作的场景中，则需要加锁来保证数据的正确性。

因此，CopyOnWriteArrayList基于volatile关键字 + ReentrantLock 实现互斥访问、保证线程安全性。

• 内部采用数组存储数据，并且数据被volatile修饰，并且在add/set/remove操作是都会新建一个数组，操作数据都体现在新数组中。操作数据完成之后会将新数组的引用赋值给volatile数组。
  • 保存数据的数组array采用volatile修饰，保证了array在线程之间的可见性。当写操作完成后，读操作可以立即感知到新数组的引用。
  • 这也是为什么这个List叫CopyOnWrite的原因。
• 因为操作数据都需要新建一个数组，所以它的数据操作效率不高；但是在遍历的时候，效率比较高，并且写操作也不会阻塞读的操作。
  • 写的过程中，从旧数据中读取；保证写数据的同时不影响读数据操作。
• 在add/set/remove操作数据时，都会先获取互斥锁ReentrantLock，数据操作完毕之后，再释放互斥锁，以达到线程安全的效果。

1）构造函数

public class CopyOnWriteArrayList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable {private static final long serialVersionUID = 8673264195747942595L;/*** 监视器锁*/final transient Object lock = new Object();/** 一个缓存数组，使用volatile修饰。 */private transient volatile Object[] array;/*** Gets the array.  Non-private so as to also be accessible* from CopyOnWriteArraySet class.*/final Object[] getArray() {return array;}/*** Sets the array.*/final void setArray(Object[] a) {array = a;}
}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();if (c.getClass() != java.util.ArrayList.class)elements = Arrays.copyOf(elements, elements.length, Object[].class);}setArray(elements);
}public CopyOnWriteArrayList(E[] toCopyIn) {setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

• CopyOnWriteArrayList的主体是volatile修饰Object[]；线程安全由互斥锁ReentrantLock保证。
• 并且由于数组也被transient关键字修饰，所以array数组不会被自动序列化。

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

方法解析：

• 执⾏写操作时，⾸先进⾏lock加锁，然后复制原数组创建⼀个⻓度加1的新数组，即：副本数组；
  • 当操作新增操作完毕后，将副本数组替换旧的数组。
  • 由于array是volatile修饰的，所以替换后，array在多线程之间是可⻅的。
• 带来的效果就是：
  • 执⾏写操作的时候，针对的是副本数组；
  • 而读操作，⼀直是针对着原数组；
  • 以此做到写操作不会阻塞读操作；

3）get()

//根据index直接获取数组元素
public E get(int index) {return elementAt(getArray(), index);
}

读操作非常简单，就是以不加锁的方式从数组中获取对应下标为index的元素。

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

方法解析：

• 只要操作数组中的数据，都是先加互斥锁ReentrantLock。
• 如果被删除的是最后一个元素，则直接通过Arrays.copyOf()进行处理，截取旧数组的前array.length - 1，实际也是新建了一个数组。
• 否则，直接新建一个数组，将旧数组以index为界限，分两块（不包括index位置的数据）拷贝到新数组中。
• 操作完成时，更新volatile数组的引用，释放互斥锁。

5）iterator()

public Iterator<E> iterator() {return new COWIterator<E>(getArray(), 0);
}

基于COWIterator进行遍历。

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 boolean hasNext() {return cursor < snapshot.length;}public boolean hasPrevious() {return cursor > 0;}@SuppressWarnings("unchecked")public E next() {if (! hasNext())throw new NoSuchElementException();return (E) snapshot[cursor++];}@SuppressWarnings("unchecked")public E previous() {if (! hasPrevious())throw new NoSuchElementException();return (E) snapshot[--cursor];}public int nextIndex() {return cursor;}public int previousIndex() {return cursor-1;}/*** Not supported. Always throws UnsupportedOperationException.* @throws UnsupportedOperationException always; {@code remove}*         is not supported by this iterator.*/public void remove() {throw new UnsupportedOperationException();}/*** Not supported. Always throws UnsupportedOperationException.* @throws UnsupportedOperationException always; {@code set}*         is not supported by this iterator.*/public void set(E e) {throw new UnsupportedOperationException();}/*** Not supported. Always throws UnsupportedOperationException.* @throws UnsupportedOperationException always; {@code add}*         is not supported by this iterator.*/public void add(E e) {throw new UnsupportedOperationException();}@Overridepublic void forEachRemaining(Consumer<? super E> action) {Objects.requireNonNull(action);Object[] elements = snapshot;final int size = elements.length;for (int i = cursor; i < size; i++) {@SuppressWarnings("unchecked") E e = (E) elements[i];action.accept(e);}cursor = size;}
}

从COWIterator源码可以看出：CopyOnWriteArrayList的迭代器中不支持修改元素的操作。

• 因为迭代器的remove()、set()、add()操作，COWIterator都会抛出异常UnsupportedOperationException。

另外，CopyOnWriteArrayList迭代器不会抛出ConcurrentModificationException异常，因此它不是fail-fast（快速失败），而是fail-safe（安全失败）。