CopyOnWriteArrayList底层原理全面解析【建议收藏】

简介

CopyOnWriteArrayList是Java中的一个线程安全的集合类，是ArrayList线程安全版本，主要通过Copy-On-Write（写时复制，简称COW）机制来保证线程安全。

Copy-On-Write机制核心思想：向一个数组中添加数据时，不直接操作原始数组，而是拷贝原始数组生成一份原始数组副本，将需要添加的数据添加到原始数组副本中，操作完成后再用原始数组副本直接替换原始数组，从而保证多个线程同时操作原始数组时的线程安全。

应用场景

CopyOnWriteArrayList的主要应用场景：

读多写少的场景，CopyOnWriteArrayList允许多个线程同时对数据进行读操作，但同一时刻只允许一个线程对数据进行写操作，并且进行写操作时需要复制原始数据的副本，造成空间和时间的浪费。
允许读写数据时出现短暂不一致的场景，CopyOnWriteArrayList写操作完成后，需要使用更新后的数据副本替换原始数据，有可能使CopyOnWriteArrayList中的数据出现短暂不一致。

实现原理

CopyOnWriteArrayList类的继承关系：

CopyOnWriteArrayList类继承关系图

Iterable接口：CopyOnWriteArrayList类实现了Iterable接口，使得它可以被迭代遍历。通过实现iterator()方法，可以获取一个迭代器，用于遍历集合中的元素。
Collection接口：CopyOnWriteArrayList类继承了AbstractCollection类，间接实现了Collection接口。通过实现Collection接口，CopyOnWriteArrayList类获得了一些常用的集合操作方法，比如判断是否包含某个元素、计算集合的大小等。
List接口：CopyOnWriteArrayList类间接实现了List接口，通过继承AbstractList类实现了List接口的一些方法。List接口定义了有序的集合，CopyOnWriteArrayList类通过继承List接口，可以按照索引进行访问和操作集合中的元素。
Cloneable接口：CopyOnWriteArrayList类实现了Cloneable接口，使得它可以进行克隆操作。通过实现clone()方法，可以创建CopyOnWriteArrayList对象的副本。
Serializable接口：CopyOnWriteArrayList类实现了Serializable接口，使得它可以进行序列化操作。通过实现writeObject()和readObject()方法，可以将CopyOnWriteArrayList对象转换为字节流，并进行存储或传输。
RandomAccess接口：CopyOnWriteArrayList类实现了RandomAccess接口，表示它可以高效地随机访问元素。RandomAccess接口是一个标记接口，用于标识实现该接口的类可以通过索引进行快速随机访问，CopyOnWriteArrayList类通过实现该接口，表明它可以高效地随机访问元素。

重要属性

CopyOnWriteArrayList类中有两个重要的属性：

array：Object数组：用于存储CopyOnWriteArrayList中的数据。该属性使用transient和volatile关键字进行修饰：

transient：表示序列化CopyOnWriteArrayList对象时，array属性不会被自动序列化。

volatile：表示一个线程对CopyOnWriteArrayList数据的更新操作，对其他线程可见。
lock：ReentrantLock锁：用于保证多个线程同时对CopyOnWriteArrayList进行写操作的线程安全性。该属性也使用transient关键字进行修饰。

CopyOnWriteArrayList类定义代码如下：

public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    ...
    // ReentrantLock锁
    final transient ReentrantLock lock = new ReentrantLock();
    // Object数组
    private transient volatile Object[] array;
    ...
}

构造函数

CopyOnWriteArrayList的构造函数：

/**
 * 无参构造函数
 */
public CopyOnWriteArrayList() {
    // 创建Object数组
    setArray(new Object[0]);
}
/**
 * 有参构造函数
 * c：集合
 */
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    // 如果参数c为CopyOnWriteArrayList对象，则将c中的数组直接赋值给elements数组
    if (c.getClass() == CopyOnWriteArrayList.class)
        elements = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
        // 将参数c转换为数组并赋值给elements数组
        elements = c.toArray();
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        // 如果数组（c）的类型不是Object[]，则将数组（c）中的元素复制给Object数组，再将Object数组赋值给elements数组
        if (elements.getClass() != Object[].class)
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    // 将CopyOnWriteArrayList的array属性指向elements数组
    setArray(elements);
}
/**
 * 有参构造函数
 * toCopyIn：数组
 */
public CopyOnWriteArrayList(E[] toCopyIn) {
    // 将数组toCopyIn中的元素复制给Object数组，再将Object数组赋值给CopyOnWriteArrayList的array数组
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

核心方法

添加元素-add方法

CopyOnWriteArrayList通过CopyOnWriteArrayList#add方法向其中添加元素。

添加元素执行流程，如图所示：

添加元素执行流程

处理流程：

1）线程获得ReentrantLock锁，拷贝原始数组（array属性对应的数组）生成原始数组副本（数组长度为原始数组的长度+1）。
2）向原始数组副本中添加元素。
3）将CopyOnWriteArrayList中的array属性值替换为原始数组副本，线程释放ReentrantLock锁。

CopyOnWriteArrayList#add(E e)方法源码解析：

/**
 * 向数组中末尾位置添加元素
 * e：待添加的元素
 */
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lock();
    try {
        // 获取原始数组（array属性对应的数组）
        Object[] elements = getArray();
        int len = elements.length;
        // 拷贝原始数组生成原始数组副本（数组长度为原始数组的长度+1）
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 向原始数组副本中添加元素
        newElements[len] = e;
        // 将CopyOnWriteArrayList中的array属性值替换为原始数组副本
        setArray(newElements);
        return true;
    } finally {
        // 释放锁
        lock.unlock();
    }
}

CopyOnWriteArrayList#add(int index, E element)方法源码解析：

/**
 * 向数组中指定位置添加元素
 * index：数组下标
 * element：待添加的元素
 */
public void add(int index, E element) {
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lock();
    try {
        // 获取原始数组
        Object[] elements = getArray();
        int len = elements.length;
        // 数组下标超过数组长度或数组下标小于0，抛出数组越界异常
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len);
        Object[] newElements;
        int numMoved = len - index;
        // 在原始数组末尾插入元素
        if (numMoved == 0)
            // 拷贝原始数组生成原始数组副本（数组长度为原始数组的长度+1）
            newElements = Arrays.copyOf(elements, len + 1);
        else {
            // 在原始数组中间插入元素，创建新数组（数组长度为原始数组的长度+1）
            newElements = new Object[len + 1];
            // 拷贝原始数组中index下标之前的元素到新数组中
            System.arraycopy(elements, 0, newElements, 0, index);
            // 拷贝原始数组中index下标之后的元素到新数组中（注意：此部分元素从index位置开始向后移动一位）
            System.arraycopy(elements, index, newElements, index + 1,
                             numMoved);
        }
        // 向原始数组副本中添加元素
        newElements[index] = element;
        // 将CopyOnWriteArrayList中的array属性值替换为原始数组副本
        setArray(newElements);
    } finally {
        lock.unlock();
    }
}

删除元素-remove方法

CopyOnWriteArrayList通过CopyOnWriteArrayList#remove方法删除指定位置的元素。

CopyOnWriteArrayList#remove方法源码解析：

public E remove(int index) {
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lock();
    try {
        // 获取原始数组
        Object[] elements = getArray();
        int len = elements.length;
        // 获取原始数组中index下标对应的元素
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        // 删除原始数组末尾元素
        if (numMoved == 0)
            // 将CopyOnWriteArrayList的array属性重新指向删除指定位置元素之后的原始数组副本
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            // 删除原始数组中间元素，创建新数组（数组长度为原始数组的长度-1）
            Object[] newElements = new Object[len - 1];
            // 拷贝原始数组中index下标前面的元素到新数组中
            System.arraycopy(elements, 0, newElements, 0, index);
            // 拷贝原始数组中index下标后面的元素到新数组中（注意：此部分元素从index+1位置开始向前移动一位）
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            // 将CopyOnWriteArrayList中的array属性值替换为原始数组副本
            setArray(newElements);
        }
        return oldValue;
    } finally {
        // 释放锁
        lock.unlock();
    }
}

更新元素-set方法

CopyOnWriteArrayList通过CopyOnWriteArrayList#set方法更新指定位置的元素。

CopyOnWriteArrayList#set方法源码解析：

public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lock();
    try {
        // 获取原始数组
        Object[] elements = getArray();
        // 获取原始数组中index下标对应的元素
        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();
    }
}

获取元素-get方法

CopyOnWriteArrayList通过CopyOnWriteArrayList#get方法获取指定位置的元素。

CopyOnWriteArrayList#get方法源码解析：

/**
 * 获取指定位置的元素
 * index：数组下标
 */
public E get(int index) {
    // 返回array数组中指定下标对应的元素
    return get(getArray(), index);
}
private E get(Object[] a, int index) {
    return (E) a[index];
}

遍历元素-iterator方法

CopyOnWriteArrayList可以通过CopyOnWriteArrayList#iterator方法进行遍历。在调用CopyOnWriteArrayList#iterator方法时，会创建一个COWIterator迭代器，创建COWIterator迭代器时传入的是array数组的快照并初始化一个游标，通过游标遍历array数组快照中的所有元素。

CopyOnWriteArrayList#iterator方法源码解析：

// 迭代方法
public Iterator<E> iterator() {
    // 通过COWIterator迭代器遍历array数组
    return new COWIterator<E>(getArray(), 0);
}
// COWIterator迭代器
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 void remove() {
        throw new UnsupportedOperationException();
    }
    // 修改
    public void set(E e) {
        throw new UnsupportedOperationException();
    }
    // 新增
    public void add(E e) {
        throw new UnsupportedOperationException();
    }
    ...
}

其中，COWIterator迭代器遍历的是array数组快照，因此，对array数组快照进行增删改操作时会抛出
UnsupportedOperationException异常。

使用示例

/**
 * @author 南秋同学
 * CopyOnWriteArrayList使用示例
 */
@Slf4j
public class CopyOnWriteArrayListExample {
    private static CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
    @SneakyThrows
    public static void main(String[] args) {
        // 创建新增元素线程
        Thread thread1 = new Thread(new Runnable() {
            @SneakyThrows
            @Override
            public void run() {
                for (int i = 0; i < 8; i++) {
                    list.add("element-" + i);
                    log.info("添加元素 element-{}", i);
                    Thread.sleep(100);
                }
            }
        });
        // 创建删除元素线程
        Thread thread2 = new Thread(new Runnable() {
            @SneakyThrows
            @Override
            public void run() {
                for (int i = 0; i < 5; i++) {
                    if(list.size() > 0){
                        list.remove(0);
                        log.info("删除元素----- element-{}", i);
                    }
                    Thread.sleep(200);
                }
            }
        });
        thread1.start();
        thread2.start();
        thread1.join();
        thread2.join();
        log.info("list中的最终元素：{}", list);
        // 遍历元素
        for (String element: list){
            log.info("打印元素：{}", element);
        }
    }
}

执行结果：

23:03:24.187 [Thread-0]  - 添加元素 element-0
23:03:24.187 [Thread-1]  - 删除元素----- element-0
23:03:24.296 [Thread-0]  - 添加元素 element-1
23:03:24.397 [Thread-1]  - 删除元素----- element-1
23:03:24.397 [Thread-0]  - 添加元素 element-2
23:03:24.498 [Thread-0]  - 添加元素 element-3
23:03:24.600 [Thread-1]  - 删除元素----- element-2
23:03:24.600 [Thread-0]  - 添加元素 element-4
23:03:24.703 [Thread-0]  - 添加元素 element-5
23:03:24.805 [Thread-1]  - 删除元素----- element-3
23:03:24.807 [Thread-0]  - 添加元素 element-6
23:03:24.909 [Thread-0]  - 添加元素 element-7
23:03:25.007 [Thread-1]  - 删除元素----- element-4
23:03:25.211 [main]  - list中的最终元素：[element-5, element-6, element-7]
23:03:25.212 [main]  - 打印元素：element-5
23:03:25.212 [main]  - 打印元素：element-6
23:03:25.212 [main]  - 打印元素：element-7

从执行结果可以看出，多个线程同时对CopyOnWriteArrayList进行写操作时，可以保证线程安全。