源码分析：线程安全的列表—CopyOnWriteArrayList

Published: at 17:13:42

简介

CopyOnWriteArrayList 是一个线程安全的ArrayList，但是它的每次操作（add ，set，remove等）都是通过复制一个底层的数组副本来实现的，在写操作的时候都会加上锁，有读写分离的意思。

CopyOnWrite

写入时复制（英语：Copy-on-write，简称COW）是一种计算机程序设计领域的优化策略。其核心思想是，如果有多个调用者（callers）同时请求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的。此作法主要的优点是如果调用者没有修改该资源，就不会有副本（private copy）被创建，因此多个调用者只是读取操作时可以共享同一份资源。——维基百科

结构分析

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

CopyOnWriteArrayList实现了List接口，所以具有列表的基础功能；同时实现了RandomAccess接口，所以也支持随机访问（数组随机访问特性）；实现了Cloneable和Serializable接口，支持克隆和序列号。

重要属性

// 锁
final transient ReentrantLock lock = new ReentrantLock();
// 数组
private transient volatile Object[] array;

CopyOnWriteArrayList内部使用的ReentrantLock非公平锁，还有一个volatile修饰的数组，保证了更换数组引用后对其他线程的可见性，并且两个属性都不支持序列化。

内部类：COWIterator

static final class COWIterator<E> implements ListIterator<E> {
        /** Snapshot of the array */
        private final Object[] snapshot; // array 快照
        /** Index of element to be returned by subsequent call to next.  */
        private int cursor; // 游标，后续调用 next 将返回的元素索引
  ...
}

COWIterator 表示迭代器，实现了ListIterator接口，内部有一个Object类型的数组作为CopyOnWriteArrayList数组的快照，在创建迭代器的时候记录了当时数组状态的引用。

在迭代器内不支持add、set、remove操作，会抛出UnsupportedOperationException异常。

public void remove() {
    throw new UnsupportedOperationException();
}
public void set(E e) {
    throw new UnsupportedOperationException();
}
public void add(E e) {
    throw new UnsupportedOperationException();
}

方法分析

构造方法

// 初始化默认无参数构造方法
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);
}

// 创建一个包含给定数组副本的列表
public CopyOnWriteArrayList(E[] toCopyIn) {
    // 将toCopyIn转化为Object[]类型数组，然后设置当前数组
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

最终调用的都是setArray方法。

final void setArray(Object[] a) {
    array = a;
}

构造方法小结：

  1. 初始化时没有指定数组的初始长度。
  2. Arrays.copyOf的逻辑就是底层的System.arraycopy数组赋值。

添加元素：add(e)方法

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    // 0.加锁
    lock.lock();
    try {
        // 1.拿到数组引用
        Object[] elements = getArray();
        int len = elements.length;
        // 2.copy一个长度+1的数组
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 3.将新增元素加入到数组的最后
        newElements[len] = e;
        // 4.覆盖旧数组
        setArray(newElements);
        return true;
    } finally {
        // 5.解锁
        lock.unlock();
    }
}
// 获取数组
final Object[] getArray() {
    return array;
}
// 覆盖数组
final void setArray(Object[] a) {
    array = a;
}

add方法小结：

  1. 加锁
  2. 拿到原数组引用
  3. copy一个长度+1的新数组
  4. 将新增元素加入到新数组的最后
  5. 新数组覆盖旧数组
  6. 释放锁，返回结果

添加元素：add(index, element)方法

指定添加元素的索引

public void add(int index, E element) {
    final ReentrantLock lock = this.lock;
    // 0.获得锁
    lock.lock();
    try {
        //1.原数组引用
        Object[] elements = getArray();
        //2.原数组长度
        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);
            System.arraycopy(elements, index, newElements, index + 1,
                             numMoved);
        }
        // 指定位置设置成新的元素
        newElements[index] = element;
        // 覆盖数组
        setArray(newElements);
    } finally {
        lock.unlock();
    }
}

add 方法小结：

  1. 大体逻辑和上面没有指定位置的方法一致
  2. 指定的中间位置，相当于把原数组切割成了两个数组，需要分别复制到长度+1的新数组

添加元素：addIfAbsent(e)方法

如果添加的元素不存在，才可以添加成功，该方法可避免多线程情况下重复添加元素。

public boolean addIfAbsent(E e) {
    Object[] snapshot = getArray();
    // indexOf 的功能就是找到元素是否存在，存在则返回其索引，不存在返回-1by:https://jingling.im
    return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
        addIfAbsent(e, snapshot);
}

// 不存在则添加
private boolean addIfAbsent(E e, Object[] snapshot) {
    final ReentrantLock lock = this.lock;
    // 1.加锁
    lock.lock();
    try {
        // 数组引用
        Object[] current = getArray();
        int len = current.length;
        if (snapshot != current) { // 不一致？说明其他线程先行一步更改了数组
            // Optimize for lost race to another addXXX operation
            // snapshot.length 是旧的数组长度   len是发现变化后的数组长度
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++)
                 // 判断两个数组的内容是否一致，并检查当前要加入的元素是否已经存在于变化后的数组中
                if (current[i] != snapshot[i] && eq(e, current[i]))
                    // 检查不通过返回false（两个条件都要满足）
                    return false;
            if (indexOf(e, current, common, len) >= 0) // 再检查一次
                    return false;
        }
        // 正常的流程，和上面的add一致by:https://jingling.im
        Object[] newElements = Arrays.copyOf(current, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

方法小结：

  1. 大体逻辑和上面没有指定位置的方法一致
  2. 多了一个检查环节，如果添加时，数组发生了变化，要检查加入的元素是否已经存在于变化后的数组中（by:https://jingling.im）
  3. 数组有变化，也会加入到变化后的新数组中

删除元素：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];
            // 复制两次，相当于删掉了elements[index]
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements); // 设置新数组的引用
        }
        return oldValue; // 返回旧值by:https://jingling.im
    } 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: { // 数组有变化会进入到if分支里面
            int prefix = Math.min(index, len);
            for (int i = 0; i < prefix; i++) {
                // 在新的数组中找到了和旧的元素不一致，并且就是要移除的值
                if (current[i] != snapshot[i] && eq(o, current[i])) {
                    index = i; // 从新数组中重新确认的索引
                    break findIndex;
                }
            }
            // 上面for循环没找到，有可能元素在新的数组中还是在那个index位置没变化（current[i] != snapshot[i] 条件不满足）
            if (index >= len) // 如果新数组是移除了一个元素，index最多也就等于len,既然新数组移除了元素，上面又没检查出来？直接返回false
                return false;
            if (current[index] == o) // 元素在新数组的同一个位置，没变化
                break findIndex;
            index = indexOf(o, current, index, len); // 位置有变化，就重新找到新位置
            if (index < 0)  // 没找到，已经删掉了，本次删除失败 by:https://jingling.im
                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();
    }
}

remove方法小结

  1. 加锁，找索引，copy删除，覆盖旧数组，解锁返回
  2. 复杂点的是移除指定元素的时候要检测在删除的过程中，数组是否发生了变化
  3. 如果有变化，需要重新校验元素是否还存在，并且找到删除元素在新数组中的索引位置，然后删除。

修改值：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方法小结：

  1. 加锁
  2. 找到指定索引的值
  3. 复制一个长度一样的新数组
  4. 在新数组中指定位置设置新元素
  5. 设置为新数组，解锁返回

获取元素：get方法

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

get方法小结：

  1. get 没有加锁
  2. 直接拿到当前数组，获取返回指定位置的值
  3. 这里有可能getArray 获取到的还是一个旧的数组（比如其他线程调用了add、set、remove方法，但是还没有调用setArray(newElements)方法），所以这里是弱一致性。

迭代器：iterator

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
}
public ListIterator<E> listIterator() {
    return new COWIterator<E>(getArray(), 0);
}
public ListIterator<E> listIterator(int index) {
    Object[] elements = getArray();
    int len = elements.length;
    if (index < 0 || index > len)
        throw new IndexOutOfBoundsException("Index: "+index);

    return new COWIterator<E>(elements, index);
}

可以以上3个迭代器最终都是通过构造一个COWIterator。

private COWIterator(Object[] elements, int initialCursor) {
    cursor = initialCursor; // 初始迭代的光标
    snapshot = elements; // 获取迭代器时，当前数组的快照
}

在获取迭代器时，COWIterator内部保留了当前数组的快照。

迭代遍历的方法：

public boolean hasNext() {
    // 判断是否还有下一个元素
    return cursor < snapshot.length;
}

public boolean hasPrevious() {
    // 判断是否还有上一个元素
    return cursor > 0;
}

@SuppressWarnings("[unchecked](http://jingling.im)")
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]; // 获取上一个元素
}

测试CopyOnWriteArrayList的弱一致性

从上面的get方法分析和迭代器分析中，我们发现他们拿到的数组都有可能是已经过时了的数组，也就是在其他线程调用了add、set、remove方法，但是还没有调用setArray(newElements)方法时，可能就没法获取到最新的数据。

示例：

CopyOnWriteArrayList cowArray = new CopyOnWriteArrayList();
cowArray.add(1);
cowArray.add(2);
cowArray.add(3);
cowArray.add(4);
Iterator it = cowArray.iterator();
while(it.hasNext()){
    System.out.print(it.next()+ " ");
}
cowArray.add("jingling.im");
if(it.hasNext()){
    System.out.print(it.next()+ " ");
}

输出结果只会有：1 2 3 4，后面再次迭代时，持有的还是获取迭代器前的数组，因为每次add操作都会产生一个新的数组，而迭代器包含的数组引用是是不包含jingling.im的，所以迭代器没法遍历出最后新添加的数据，也就是CopyOnWriteArrayList 的弱一致特性。

总结

  1. CopyOnWriteArrayList 是一个线程安全的ArrayList，以上是基于jdk1.8的分析。
  2. 每次对数据的修改都会copy一份新的数组（哪怕数组的长度没变化），对内存要求比较高。
  3. CopyOnWriteArrayList 是弱一致性，不能保证修改数据后，其他线程马上就能感知。
  4. CopyOnWriteArrayList 不能限制数组的最长长度，使用需要谨慎。
  5. jdk1.8版本是通过ReentrantLock锁实现的，jdk11就已经改成了synchronized锁。