CopyOnWriteArrayList介绍

2021-10-18 09:07:55 浏览数 (1)

简介

在很多应用场景中，读操作可能会远远大于写操作。由于读操作根本不会修改原有的数据，因此如果每次读取都进行加锁操作，其实是一种资源浪费。我们应该允许多个线程同时访问 List 的内部数据，毕竟读操作是线程安全的。

JDK中提供了 CopyOnWriteArrayList 类，相比于在读写锁的思想又更进一步。为了将读取的性能发挥到极致，CopyOnWriteArrayList 读取是完全不用加锁的，并且更厉害的是：写入也不会阻塞读取操作，只有写入和写入之间需要进行同步等待，读操作的性能得到大幅度提升。

CopyOnWriteArrayList 类的所有可变操作（add、set等）都是通过创建底层数组的新副本来实现的。CopyOnWriteArrayList为线程安全的ArrayList。当 List 需要被修改的时候，并不直接修改原有数组对象，而是对原有数据进行一次拷贝，将修改的内容写入副本中。写完之后，再将修改完的副本替换成原来的数据，这样就可以保证写操作不会影响读操作了。

从 CopyOnWriteArrayList 的名字可以看出，CopyOnWriteArrayList 是满足 CopyOnWrite 的 ArrayList，所谓 CopyOnWrite 的意思：、就是对一块内存进行修改时，不直接在原有内存块中进行写操作，而是将内存拷贝一份，在新的内存中进行写操作，写完之后，再将原来指向的内存指针指到新的内存，原来的内存就可以被回收。

类结构

CopyOnWriteArrayList类关系图：

CopyOnWriteArrayList实现了List接口的所有方法，主要包含如下两个成员变量：

代码语言：javascript复制
// 可重入锁，用于对写操作加锁
final transient ReentrantLock lock = new ReentrantLock();

// Object类型数组，存放数据，volatile修饰，目的是一个线程对这个字段的修改另外一个线程立即可见
private transient volatile Object[] array;

CopyOnWriteArrayList中并没有和容量有关的属性或者常量，下面通过对一些常用方法的源码解析，就可以知道原因。

方法解析

构造函数

CopyOnWriteArrayList()空参构造函数：无参构造函数直接创建了一个长度为0的Object数组。

代码语言：javascript复制
public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}

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

CopyOnWriteArrayList(Collection<? extends E> c)集合类型的构造函数

代码语言：javascript复制
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    if (c.getClass() == CopyOnWriteArrayList.class)
        // 如果集合类型就是CopyOnWriteArrayList，则直接将其array赋值给当前CopyOnWriteArrayList
        elements = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
        // 如果不是CopyOnWriteArrayList类型，则将集合转换为数组
        elements = c.toArray();
        // 就如ArrayList源码分析所述那样，c.toArray()返回类型不一定是Object[].class，所以需要转换
        if (elements.getClass() != Object[].class)
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    // 设置array值
    setArray(elements);
}

CopyOnWriteArrayList(E[] toCopyIn)数组类型的构造函数

代码语言：javascript复制
public CopyOnWriteArrayList(E[] toCopyIn) {
    // 入参为数组，拷贝一份赋值给array
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

add(E e)

add(E e)往CopyOnWriteArrayList末尾添加元素：

代码语言：javascript复制
public boolean add(E e) {
    // 获取可重入锁
    final ReentrantLock lock = this.lock;
    // 上锁，同一时间内只能有一个线程进入
    lock.lock();
    try {
        // 获取当前array属性值
        Object[] elements = getArray();
        // 获取当前array数组长度
        int len = elements.length;
        // 复制一份新数组，新数组长度为当前array数组长度 1
        Object[] newElements = Arrays.copyOf(elements, len   1);
        // 在新数组末尾添加元素
        newElements[len] = e;
        // 新数组赋值给array属性
        setArray(newElements);
        return true;
    } finally {
        // 锁释放
        lock.unlock();
    }
}

final Object[] getArray() {
    return array;
}

可以看到，add操作通过ReentrantLock来确保线程安全。通过add方法，我们也可以看出CopyOnWriteArrayList修改操作的基本思想为：复制一份新的数组，新数组长度刚好能够容纳下需要添加的元素；在新数组里进行操作；最后将新数组赋值给array属性，替换旧数组。这种思想也称为“写时复制”，所以称为CopyOnWriteArrayList。

此外，我们可以看到CopyOnWriteArrayList中并没有类似于ArrayList的grow方法扩容的操作。

add(int index, E element)

add(int index, E element)指定下标添加指定元素：

代码语言：javascript复制
public void add(int index, E element) {
    // 获取可重入锁
    final ReentrantLock lock = this.lock;
    // 上锁，同一时间内只能有一个线程进入
    lock.lock();
    try {
        // 获取当前array属性值
        Object[] elements = getArray();
         // 获取当前array数组长度
        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)
            // numMoved为0，说明是在末尾添加，过程和add(E e)方法一致
            newElements = Arrays.copyOf(elements, len   1);
        else {
            // 否则创建一个新数组，数组长度为旧数组长度值 1
            newElements = new Object[len   1];
            // 分两次复制，分别将index之前和index 1之后的元素复制到新数组中
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index, newElements, index   1,
                             numMoved);
        }
        // 在新数组的index位置添加指定元素
        newElements[index] = element;
        // 新数组赋值给array属性，替换旧数组
        setArray(newElements);
    } finally {
        // 锁释放
        lock.unlock();
    }
}

get(int index)

代码语言：javascript复制
public E get(int index) {
    return get(getArray(), index);
}
final Object[] getArray() {
    return array;
}

可以看到，get(int index)操作是分两步进行的：

  1. 通过getArray()获取array属性值；
  2. 获取array数组index下标值。

这个过程并没有加锁，所以在并发环境下可能出现如下情况：

  1. 线程1调用get(int index)方法获取值，内部通过getArray()方法获取到了array属性值；
  2. 线程2调用CopyOnWriteArrayList的增删改方法，内部通过setArray方法修改了array属性的值；
  3. 线程1还是从旧的array数组中取值。

所以get方法是弱一致性的。

set(int index, E element)

set(int index, E element)设置指定位置的值：

代码语言：javascript复制
public E set(int index, E element) {
    // 获取可重入锁
    final ReentrantLock lock = this.lock;
    // 上锁，同一时间内只能有一个线程进入
    lock.lock();
    try {
    	// 获取当前array属性值
        Object[] elements = getArray();
        // 获取当前array指定index下标值
        E oldValue = get(elements, index);
        if (oldValue != element) {
        	// 如果新值和旧值不相等
            int len = elements.length;
            // 复制一份新数组，长度和旧数组一致
            Object[] newElements = Arrays.copyOf(elements, len);
            // 修改新数组index下标值
            newElements[index] = element;
            // 新数组赋值给array属性，替换旧数组
            setArray(newElements);
        } else {
            // 即使新值和旧值一致，为了确保volatile语义，需要重新设置array
            setArray(elements);
        }
        return oldValue;
    } finally {
    	// 释放锁
        lock.unlock();
    }
}

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

remove(int index)

remove(int index)删除指定下标元素：

代码语言：javascript复制
public E remove(int index) {
    // 获取可重入锁
    final ReentrantLock lock = this.lock;
    // 上锁，同一时间内只能有一个线程进入
    try {
    	// 获取当前array属性值
        Object[] elements = getArray();
        // 获取当前array长度
        int len = elements.length;
        // 获取旧值
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        if (numMoved == 0)
        	// 如果删除的是最后一个元素，则将当前array设置为新数组
        	// 新数组长度为旧数组长度-1，这样刚好截去了最后一个元素
            setArray(Arrays.copyOf(elements, len - 1));
        else {
        	// 分段复制，将index前的元素和index 1后的元素复制到新数组
        	// 新数组长度为旧数组长度-1
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index   1, newElements, index,
                             numMoved);
            // 设置array
            setArray(newElements);
        }
        return oldValue;
    } finally {
    	// 锁释放
        lock.unlock();
    }
}

可以看到，CopyOnWriteArrayList中的增删改操作都是在新数组中进行的，并且通过加锁的方式确保同一时刻只能有一个线程进行操作，操作完后赋值给array属性，替换旧数组，旧数组失去了引用，最终由GC回收。

size()

代码语言：javascript复制
public int size() {
    return getArray().length;
}

size()方法返回当前array属性长度，因为CopyOnWriteArrayList中的array数组每次复制都刚好能够容纳下所有元素，并不像ArrayList那样会预留一定的空间。所以CopyOnWriteArrayList中并没有size属性，元素的个数和数组的长度是相等的。

迭代器

代码语言：javascript复制
public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
}
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;
    }
    ......
}

可以看到，迭代器也是弱一致性的，并没有在锁中进行。如果其他线程没有对CopyOnWriteArrayList进行增删改的操作，那么snapshot还是创建迭代器时获取的array，但是如果其他线程对CopyOnWriteArrayList进行了增删改的操作，旧的数组会被新的数组给替换掉，但是snapshot还是原来旧的数组的引用：

总结

  • CopyOnWriteArrayList体现了写时复制的思想，增删改操作都是在复制的新数组中进行的；
  • CopyOnWriteArrayList的取值方法是弱一致性的，无法确保实时取到最新的数据；
  • CopyOnWriteArrayList的增删改方法通过可重入锁确保线程安全；
  • CopyOnWriteArrayList线程安全体现在多线程增删改不会抛出java.util.ConcurrentModificationException异常，并不能确保数据的强一致性；
  • 同一时刻只能有一个线程对CopyOnWriteArrayList进行增删改操作，而读操作没有限制，并且 CopyOnWriteArrayList增删改操作都需要复制一份新数组，增加了内存消耗，所以CopyOnWriteArrayList适合读多写少的情况。
任务调度

0 人点赞