探究CopyOnWriteArrayList中的方法原理

71 阅读 0 评论 47 点赞

我是靠谱客的博主忧伤凉面，最近开发中收集的这篇文章主要介绍探究CopyOnWriteArrayList中的方法原理，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

CopyOnWriteArrayList 实现自 List 接口，所以我们可以像使用 ArrayList 一样使用 CopyOnWriteArrayList。CopyOnWriteArrayList 类的字段定义如下：

public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, Serializable {

    /** 支撑同步操作的重入锁 */
    final transient ReentrantLock lock = new ReentrantLock();
    /** 底层数组 */
    private transient volatile Object[] array;

首先来看一下添加元素的操作，CopyOnWriteArrayList 定义了多个重载版本的 add 的方法实现，包括：

CopyOnWriteArrayList#add(E)
CopyOnWriteArrayList#add(int, E)
CopyOnWriteArrayList#addIfAbsent(E)
CopyOnWriteArrayList#addAll(Collection<? extends E>)
CopyOnWriteArrayList#addAll(int, Collection<? extends E>)
CopyOnWriteArrayList#addAllAbsent

这些方法在实现上思想都是相通的，下面以 add(E) 方法为例分析往 CopyOnWriteArrayList 中添加元素的运行机制，方法实现如下：

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    // 加锁，保证同一时间只有一个线程修改底层数组
    lock.lock();
    try {
        // 获取底层数组
        Object[] elements = this.getArray();
        int len = elements.length;
        // 复制出一份新的数组，长度加 1，以容纳待添加的元素
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        // 更新底层数组
        this.setArray(newElements);
        return true;
    } finally {
        // 释放锁
        lock.unlock();
    }
}

再来看一下获取元素的操作，CopyOnWriteArrayList 仅定义了一个 get 方法，用于获取指定下标的元素值，实现如下：

public E get(int index) {
    // 直接返回底层数组 index 下标的元素
    return this.get(this.getArray(), index);
}

private E get(Object[] a, int index) {
    return (E) a[index];
}

继续来看一下修改元素的操作，CopyOnWriteArrayList 同样仅定义了一个 CopyOnWriteArrayList#set 方法，用于修改指定下标的元素值，实现如下：

public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    // 获取锁
    lock.lock();
    try {
        // 获取底层数组
        Object[] elements = this.getArray();
        // 获取数组 index 下标值
        E oldValue = this.get(elements, index);
        // 待更新的元素值与数组中指定位置的元素值不同
        if (oldValue != element) {
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len);
            // 更新 index 位置的元素值
            newElements[index] = element;
            // 更新底层数组
            this.setArray(newElements);
        } else {
            // Not quite a no-op; ensures volatile write semantics
            // 待更新的元素值与数组中指定位置的元素值相同，无需执行更新操作
            this.setArray(elements); // 保证 volatile 写语义
        }
        return oldValue;
    } finally {
        // 释放锁
        lock.unlock();
    }
}

最后来看一下删除元素的操作，CopyOnWriteArrayList 针对删除操作定义了多个重载版本的 remove 的方法实现，包括：

CopyOnWriteArrayList#remove(int)
CopyOnWriteArrayList#remove(java.lang.Object)
CopyOnWriteArrayList#removeAll
CopyOnWriteArrayList#removeIf

下面以 remove(int) 方法为例分析从 CopyOnWriteArrayList 中删除元素的运行机制，方法实现如下：

public E remove(int index) {
    final ReentrantLock lock = this.lock;
    // 获取锁
    lock.lock();
    try {
        // 获取底层数组
        Object[] elements = this.getArray();
        int len = elements.length;
        // 获取指定下标元素
        E oldValue = this.get(elements, index);
        int numMoved = len - index - 1;
        // 如果是删除最后一个元素，则直接 copy 即可，无需移动
        if (numMoved == 0) {
            this.setArray(Arrays.copyOf(elements, len - 1));
        } else {
            // 否则，分两次进行拷贝，去掉原 index 下标的元素
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index, numMoved);
            this.setArray(newElements);
        }
        return oldValue;
    } finally {
        // 释放锁
        lock.unlock();
    }
}

除了上面分析的核心操作方法，CopyOnWriteArrayList 还实现了iterator 方法返回一个迭代器，实现如下：

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

总结

本文分析了 CopyOnWriteArrayList 的设计与实现，CopyOnWriteArrayList 对于数据的修改操作均在副本上完成，并基于 ReentrantLock 保证同一时间只有一个线程能够对底层数组执行修改操作。线程在读取 CopyOnWriteArrayList 时都是拿到底层数组的一个最新快照，并在快照上执行读取操作，所以期间的修改结果对于读操作是不可见的，这也就导致了读写的弱一致性。但是对于读多写少的场景来说，CopyOnWriteArrayList 能够在保证线程安全的同时媲美 ArrayList 的性能。