CopyOnWriteArrayList

本文最后更新于 1446 天前，其中的信息可能已经有所发展或是发生改变。

简介

Copy-On-Write简称COW，中文翻译为写时复制，是一种用于程序设计中的优化策略，一开始是用于Linux的fork方法，通过fork方法来创建子进程，为了提高效率，使用了写时复制技术。基本思想就是，当有其他线程修改数据的时候，会首先复制一下共享数据，在新副本上进行修改，修改结束后再将副本替换为修改后的新副本。这样就会避免在并发情况导致的一些问题。

什么是CopyOnWrite容器

CopyOnWrite容器即写时复制的容器，当插入数据的时候，不会直接插入当前的容器，而是先将容器进行复制，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。这样做的好处是我们可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。

CopyOnWriteArrayList是ArrayList的线程安全实现，重写了add，set方法，在修改数据的时候复制新的数据副本，在新的数据副本进行添加。虽然这样会导致修改成本过高，但是当在频繁遍历的情况下，它可能比其他方法更加高效，并且在您不能或不想通过同步遍历来排除并发线程的干扰时，这样做更加有效。在获得迭代器的时候，会返回一个迭代器的快照，这个快照通过将数据指向之前的数据副本，从而使得在迭代器销毁之前永远不会改变，从而避免了多线程修改从而导致抛出ConcurrentModificationException异常。但是这个迭代器是不支持remove、set、add操作的，如果进行这些操作会抛出UnsupportedOperationException异常。

优势：

读操作不需要加锁，读取操作永远不会被堵塞。
不会因为多线程干扰而导致读取到脏数据或者导致集合数据数量异常。
不会因为多线程修改了集合，导致迭代器抛出ConcurrentModificationException异常。

劣势：

数据的时效性比较差，如果集合数据量比较大时，插入一个数据可能很久才能生效。
插入代价太高，因为每次插入数据都需要复制一个新副本，如果频繁插入的话会堵塞进程，所以官方建议如果大量插入最好利用addAll方法直接插入一个临时集合。
迭代器不支持修改操作，从而使得在遍历过程中移除或修改数据实现更加复杂。

类变量

final transient ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array;

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

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

类变量为一个锁变量和一个用volatile修饰的对象数据，并提供了get和set方法来修改数据指向。

容器构造函数

CopyOnWriteArrayList提供三种构造函数，一个是无参数构造函数。

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);
}

这个构造函数是将一个集合包装成CopyOnWriteArrayList，这个需要传入一个继承Collection类的集合，他会判断如果就是CopyOnWriteArrayList，就只需要调用getArray方法将集合变为数组就可以了。如果不是就需要判断一下传入的集合调用toArray方法转成的数组是不是Object数组，为什么要进行判断呢，我们可以看一下Arrays的内部类ArrayList。

private static class ArrayList<E> extends AbstractList<E>
    implements RandomAccess, java.io.Serializable
{
    private static final long serialVersionUID = -2764017481108945198L;
    private final E[] a;

    ArrayList(E[] array) {
        a = Objects.requireNonNull(array);
    }
    @Override
    public Object[] toArray() {
        return a.clone();
    }

这个ArrayList和java.util里面的ArrayList不是一个，这个只是一个适配器模式设计的一个类，通过这个类可以将一个数组包装成一个集合，但是它实际还是一个数组，而且这个类没有实现增删改查功能的，而且最大的区别就是，集合里面存储的是Object数组，这里是存储的实际数组类型的，这个toArray看似是返回一个Object数组，实际我们可以测试一下。

public void test1() {
    String[] a = {"11","22","33","44"};
    List<String> stringList = Arrays.asList(a);
    Object[] objects = stringList.toArray();
    System.out.println(objects.getClass());
}

虽然objects是Object数组，但是不代表objects实际是Object数组，这就涉及面向对象的多态了，如果忘了多态的同学可以去复习一下。大家可以试一下，这个最后打印的是String数组。

那又会有人问了，这个并不能说明问题，那我们再做一个实验，如果去掉这一步验证的话，会导致什么问题。

public void test2() {
    Man[] men = new Man[3];
    List<Man> manList = Arrays.asList(men);
    CopyOnWriteArrayList<People> copyOnWriteArrayList = new CopyOnWriteArrayList<>(manList);
    copyOnWriteArrayList.add(new People());
}

这应该是我们常用的用父类容器存储子类数据，这样可以使这个方法更加灵活。上面这段代码是有验证的代码，会正确执行。

public void test3() {
    Man[] men = new Man[3];
    List<Man> manList = Arrays.asList(men);
    Object[] b = manList.toArray();
    b[1] = new People();
}

这个代码是模拟如果没验证会出现什么问题，这个只是个模拟，不是完全实现一个没有验证的CopyOnWriteArrayList容器，如果你执行这个测试，你会发现抛出了ArrayStoreException异常，因为多态的里氏代换原则只能父类指向子类元素，不能子类元素指向父类元素，所以这里就会抛出素组存储异常，因为b数组其实是个Man数组，而不是Object数组，当你存储他的父类People的时候就会报错。

public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

这个构造方法就是传入一个数组来构造一个容器，这个和asList那个不是一种设计，这个是创建一个集合，而asList只是让数组看起来像一个集合。

get操作

读取方法应该是CopyOnWriteArrayList最简单的方法，因为CopyOnWriteArrayList是修改加锁，读不加锁，所以读实现很容易。

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

public E get(int index) {
    return get(getArray(), index);
}

直接取出数组数组index位置的数据就可以了，因为修改的时候是先生成新的副本然后才将数据指向新的副本，所以读操作不需要加锁。

add操作

add是数据添加操作，CopyOnWriteArrayList提供两个添加方法，一个是直接插入数据，一个是指定插入的位置。

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

在添加的时候首先需要加锁，因为CopyOnWriteArrayList插入是同步操作，然后getArray获得数据，之后调用Arrays.copyOf方法来复制数据，复制之后的数据是没有插入新数据的，需要将新数组的最后一个位置插入。然后将数据指向新的副本，然后释放锁，这样就完成了添加。

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];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index, newElements, index + 1,
                             numMoved);
        }
        newElements[index] = element;
        setArray(newElements);
    } finally {
        lock.unlock();
    }
}

这个方法是向指定位置插入，相对添加到末尾，这个方法里设计相对末尾添加，多了一步将数组移动的操作。首先需要判断要移动多少个元素，如果不用移动元素说明，就是在集合末尾添加，就直接扩充数组就可以了。如果需要移动数组，就首先从0开始复制index个数据，然后从index开始复制，新数组从index+1开始，复制numMoved个元素，之后将需要插入的数组插入到index位置，然后将数据指向新的副本，然后释放锁。

remove操作

在开始分析remove操作之前，我们需要说一下CopyOnWriteArrayList相对与普通ArrayList不同的几个方法实现。

private static boolean eq(Object o1, Object o2) {
    return (o1 == null) ? o2 == null : o1.equals(o2);
}

private static int indexOf(Object o, Object[] elements,
                           int index, int fence) {
    if (o == null) {
        for (int i = index; i < fence; i++)
            if (elements[i] == null)
                return i;
    } else {
        for (int i = index; i < fence; i++)
            if (o.equals(elements[i]))
                return i;
    }
    return -1;
}

private static int lastIndexOf(Object o, Object[] elements, int index) {
    if (o == null) {
        for (int i = index; i >= 0; i--)
            if (elements[i] == null)
                return i;
    } else {
        for (int i = index; i >= 0; i--)
            if (o.equals(elements[i]))
                return i;
    }
    return -1;
}

这三个方法分别为比较，查找指定元素在数组的位置，查找元素在数组最后出现的位置（倒序查找）。这三个方法在CopyOnWriteArrayList中是静态实现，而在其他集合都是普通方法实现，每个不同的实现都应该有对应的作用，在indexOf注释有下面这句话。

static version of indexOf, to allow repeated calls without needing to re-acquire array each time.

这句话的意思是，静态版本的indexOf，在任何时候重复调用方法都不用重新获得数组。

？？？其实我没理解这句话到底是在说什么。如果这个方法是在重复调用时都只需要获取一次数组，那为什么要在参数里传入elements呢。这不矛盾了。

之后经过我的分析，他这句话的意思，如果直接把数组的引用传入到方法里，就不需要直接遍历对象里的数组了，因为对象里的数组会因为其他线程对集合的修改从而改变引用，这样会导致方法遍历数组时数组是可能改变的。这样最后的结果就没有意义了，但是方法传递参数的时候，会复制一份原来数组引用的备份，这样就算数据被修改过。我们方法里面的这个数组引用是不会变的，从而避免了其他线程的影响。

那为什么不用对象方法啊。可以参考这个stackOverFlow问题。主要就是两点：

Make it clear to the reader that they will not modify the state of the object.
为了清晰地表明该方法不会对所在对象造成任何更改。
The JIT compiler will anyways inline and optimize it.

JIT会在任何地方内联方法并优化它。

下面来说remove方法，remove方法有两个重载，一个是按index进行删除，一个是按元素进行删除。

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];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

按index这个删除相对来说比较简单，和插入操作十分相同。因为是修改操作，需要先加锁。首先算出删除之后需要移动多少数据，如果移动数组为0说明删除的就是最后一个数据，直接在复制的时候直接复制len-1就可以了。如果移动数据数量不为0，就需要复制数据了，先从0开始复制index个数据，然后从index开始复制，复制numMoved个数据，然后将数组更新为新副本。然后返回删除的值并释放锁，删除结束。

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: {
            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;
                }
            }
            if (index >= len)
                return false;
            if (current[index] == o)
                break findIndex;
            index = indexOf(o, current, index, len);
            if (index < 0)
                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();
    }
}

第二个删除方法是传入一个元素，如果有相同的元素就删除，这个相对index删除，多了一个查找的过程，这就会导致一个问题，就是查找元素时候和删除操作的数据副本可能不是一个，所以这个删除更加复杂。

首先，进行快照来保存查找的数据副本，防止查找的数据副本和当前数据副本不同步，然后调用remove(Object o, Object[] snapshot, int index)这个方法，这个方法才是真正的删除操作，所以需要进行加锁，然后拿到当前数据副本。

如果snapshot 和current不相同，说明当前副本和刚刚快照的副本不相同，说明在查找过程中，有线程修改了数据副本，数据的指向发生改变，因为不知其他线程是删除了数据还是添加了数据，所以首先需要在len和index之间取一个最小值，来进行遍历，从0遍历到prefix，如果发现当前副本的i位置和快照的i位置不相同，但和删除元素相同，说明因为数据修改，导致删除元素移动到index的前面，所以就将index修改为i，就可以进行下一步删除操作了。
如果遍历到最后都没找到，就需要判断index是不是比len小，如果比len小，说明遍历了一遍都没发现删除元素o，所以就说明这个元素不存在了，直接返回false。
如果current[index] 等于o说明修改了数据，但是删除的元素相对快照来说没有变化，这样就可以进行下一步删除操作了。
如果上面两条都不满足，说明由于数据变化，删除的元素可能移动到index后面了，所以只能再进行一次indexOf，如果还小于0说明这个元素不在这个集合之中，直接返回false，如果大于等于0，就可以进行下一步删除操作了。

之后进行的删除操作和remove(int index)的操作相同，这里就不详细介绍了。

原创声明
本文由 makese 于2018年11月28日发表在我的博客
如未特殊声明，本站所有文章均为原创；你可以在保留作者及原文地址的情况下转载
转载请注明：CopyOnWriteArrayList | 我的博客

简介

什么是CopyOnWrite容器