深度解析CopyOnWriteArrayList，线程安全的ArrayList

前言

ArrayList是线程不安全的，这点无须置疑。由于ArrayList的所有方法既没有加锁，也没有进行额外的线程安全解决。而Vector作为线程安全版的ArrayList，存在感总是比较低。由于无论是add、remove还是get方法都加上了synchronized锁，所以效率低下。
JDK1.5引入的J.U.C包中，又实现了一个线程安全版的ArrayList——CopyOnWriteArrayList。

成员变量

先来看下CopyOnWriteArrayList类的定义和底层数据结构

public class CopyOnWriteArrayList<E>    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {    private static final long serialVersionUID = 8673264195747942595L;    /** The lock protecting all mutators */    transient final ReentrantLock lock = new ReentrantLock();    /** The array, accessed only via getArray/setArray. */    // 存储数据的array数组，注意此处是用volatile修饰的    private volatile transient Object[] array;}

根据定义来看，比ArrayList多了一个ReentrantLock成员变量，存储数据的数组用volatile修饰，其他的并没有多少区别。存储数据的结构仍然是数组。

构造方法

/*** Sets the array.* 语法糖*/final void setArray(Object[] a) {    array = a;}/*** Creates an empty list.*/public CopyOnWriteArrayList() {    setArray(new Object[0]);}/*** Creates a list holding a copy of the given array.* 创立一个保存给定数组副本的list（把参数给的数组拷贝给成员变量）** @throws NullPointerException if the specified array is null* 参数数组为null，抛出NullPointerException*/public CopyOnWriteArrayList(E[] toCopyIn) {    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));}

看完构造方法仍然有些疑惑，成员变量和构造方法看起来比ArrayList还要简单，究竟是如何保证线程安全的呢。或者许add方法会给我们答案。

核心方法

add(E e)

add(E e)方法用于往list尾部增加元素，CopyOnWriteArrayList中add(E e)方法源码如下：

/** * Appends the specified element to the end of this list. * 往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 {        // 获取成员变量array[]        Object[] elements = getArray();        int len = elements.length;        // 原数组拷贝给新数组（即将增加一个元素，所以 len + 1）        Object[] newElements = Arrays.copyOf(elements, len + 1);        newElements[len] = e;        // 新数组替换原数组        setArray(newElements);        return true;    } finally {        // 解锁        lock.unlock();    }}

从这段代码中可以得出如下信息：

• add方法通过ReentrantLock保证同一时刻最多只有一个线程向list中增加元素，一定是线程安全的
• 并不是直接往数组中增加元素，而是开拓新数组，把元素插入新数组，再用新数组替换旧数组

既然ReentrantLock已经保证了线程安全，为什么还需要开拓新数组？
由于volatile修饰数组时，仅能保证数组的引用具备volatile语义。也就是说volatile修饰的数组，即便数组中的元素被改变了，也不会触发可见性。想要处理这个问题有两种办法

• 使用AtomicIntegerArray或者者AtomicLongArray
• 修改数组的内存地址，也就是对数组进行重新赋值

除了volatile语义的问题，还有一个起因就是为了get方法，下文会详细详情这个方法。

add(int index, E element)

add(int index, E element)方法用于往list指定位置增加元素，源码如下：

/** * 指定位置增加元素 * * @throws IndexOutOfBoundsException {@inheritDoc} */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];            // 拷贝index之前的元素到新数组，拷贝前后，元素下标不变            System.arraycopy(elements, 0, newElements, 0, index);            // 拷贝index之后的元素到新数组，拷贝之后，下标+1            // 由于新数组index处需要空出来留给新添加元素            System.arraycopy(elements, index, newElements, index + 1,                             numMoved);        }        newElements[index] = element;        // 新数组替换原数组        setArray(newElements);    } finally {        // 解锁        lock.unlock();    }}

这两个add方法完成的功能不一样，但是实现步骤和原理都差不多，都可以笼统成5步：
1、加锁
2、开拓新数组
3、拷贝元素
4、新数组替换旧数组
5、解锁

CopyOnWriteArrayList尽管底部也是数组实现，但是没有扩容这个说法。由于每次add都会开拓新的数组。况且每次add都会加锁，所以效率是比较低的。

remove(int index)

remove(int index)方法用于删除并返回指定位置的元素，其源码如下：

/** * 删除并返回指定位置的元素 * * @throws IndexOutOfBoundsException {@inheritDoc} */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];            // 拷贝index之前的元素到新数组，拷贝前后下标不变            System.arraycopy(elements, 0, newElements, 0, index);            // 拷贝index之后的元素到新数组，拷贝之后下标-1            System.arraycopy(elements, index + 1, newElements, index,                             numMoved);            // 新数组替换原数组            setArray(newElements);        }        // 返回删除的值        return oldValue;    } finally {        // 解锁        lock.unlock();    }}

从源码可以看出，不论是add也好，还是remove也好。都是通过ReentrantLock + volatile + 数组拷贝来实现线程安全的。
写到这里，也并没有看出来CopyOnWriteArrayList比Vector高效到哪里去，况且前者每次add/remove操作都会开拓新数组，相当于白费了一倍的空间。

那么，接下来就是见证奇…

咳咳，没有奇迹，来看看CopyOnWriteArrayList的优点。
vector效率低就低在get也加上了synchronized锁，但是CopyOnWriteArrayList的get方法就不用了加锁

get(int index)

get(int index)方法用于获取指定位置的元素，源码如下：

/** * {@inheritDoc} * * @throws IndexOutOfBoundsException {@inheritDoc} */public E get(int index) {    // 调用内部get方法    return get(getArray(), index);}@SuppressWarnings("unchecked")private E get(Object[] a, int index) {    return (E) a[index];}

可以看到get(int index)不需要加锁，由于CopyOnWriteArrayList在add/remove操作时，不会修改原数组，所以读操作不会存在线程安全问题。这其实就是读写分离的思想，只有写入的时候才加锁，复制副原本进行修改。CopyOnWriteArrayList也叫写时复制容器。

而且在迭代过程中，即便数组的结构被改变也不会抛出ConcurrentModificationException异常。由于迭代的始终是原数组，而所有的变化都发生在原数组的副本上。所以对于迭代器来说，迭代的集合结构不会发生改变。

优缺点

CopyOnWriteArrayList的优点主要有两个：

• 线程安全
• 大大的提高了“读”操作的并发度（相比于Vector）

缺点也很显著：

• 每次“写”操作都会开拓新的数组，白费空间
• 无法保证明时性，由于“读”和“写”不在同一个数组，且“读”操作没有加互斥锁，所以不能保证强一致性，只能保证最终一致性
• add/remove操作效率低，既要加锁，还要拷贝数组

所以CopyOnWriteArrayList比较适合读多写少的场景。

注意：千万千万不要在循环中对CopyOnWriteArrayList进行add/remove操作，CopyOnWriteArrayList提供了对应的批量解决方法addAll和removeAll。
以下是在循环中进行add操作和addAll操作比照：

/** * 循环 + add vs addAll */public class CopyOnWriteArrayListDemo {    private static final int COUNT = 100000;    private static final List<Integer> list1 = new CopyOnWriteArrayList<>();    private static final List<Integer> list2 = new CopyOnWriteArrayList<>();    public static void main(String[] args) {        List<Integer> dataList = new ArrayList<>(COUNT);        for (int i = 0; i < COUNT; i++) {            dataList.add(i);        }        testCopyOnWriteArrayList(dataList);    }    private static void testCopyOnWriteArrayList(List<Integer> dataList) {        long time1 = System.currentTimeMillis();        for (Integer data : dataList) {            list1.add(data);        }        long time2 = System.currentTimeMillis();        System.out.println("循环+add 耗时：" + (time2 - time1) / 1000.0 + " 秒");        list2.addAll(dataList);        long time3 = System.currentTimeMillis();        System.out.println("addAll  耗时：" + (time3 - time2) / 1000.0 + " 秒");    }}

执行结果

循环+add 耗时：2.604 秒addAll  耗时：0.001 秒

这样很直观的看到了两者的效率差异。

总结

CopyOnWriteArrayList利用ReentrantLock + volatile + 数组拷贝实现了线程安全的ArrayList。在特定的场景下使用CopyOnWriteArrayList既能保证线程安全，又能有较好的体现。

作者：Sicimike
原文链接：https://blog.csdn.net/Baisitao_/article/details/103377409