CopyOnWriteArrayList 原理解析

介绍

在 Java 并发包中的并发 List 只有 CopyOnWriteArrayList，CopyOnWriteArrayList 是一个线程平安的 ArrayList，对其进行的批改操作都是在底层的一个复制的数组（快照）上进行的，也就是应用了写时复制策略。

在 CopyOnWriteArrayList 的类图中，每个 CopyOnWriteArrayList 对象外面有一个 array 数组用来寄存具体的元素，ReentrantLock独占锁来保障同时只有一个线程对 array 进行批改。

如果让咱们本人做一个写时复制的线程平安的 list 咱们会怎么做，有哪些点须要思考？

何时初始化 list，初始化的 list 元素个数为多少，list 是无限大小吗？
如何保障线程平安，比方多个线程进行读写时如何保障是线程平安的？
如何保障应用迭代器遍历 list 时的数据一致性？

上面咱们看一下 CopyOnWriteArrayList 是如何实现的。

次要办法解析

初始化

在无参构造函数中，默认创立大小为 0 的 Object 数组作为初始值。

public CopyOnWriteArrayList() {        setArray(new Object[0]);}

有参构造函数：

//传入的toCopyIn的正本public CopyOnWriteArrayList(E[] toCopyIn) {    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));}

//入参为汇合，复制到list中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 中用来增加元素的函数有：

add(E e)
add(int index,E e)
addIfAbsent(E e)
addAllAbsent(Collection<? extents E> c)等

这些函数原理相似，咱们以 add(E e)为例来解析。

public boolean add(E e) {        // 获取独占锁        final ReentrantLock lock = this.lock;        lock.lock();        try {            // 获取array            Object[] elements = getArray();            int len = elements.length;            //复制array到新数组并且增加新元素到新数组            Object[] newElements = Arrays.copyOf(elements, len + 1);            newElements[len] = e;            // 应用新数组替换旧的数组            setArray(newElements);            return true;        } finally {            //开释独占锁            lock.unlock();        }}

在上述代码中，首先会获取独占锁，如果有多个线程同时调用 add 办法则只有一个线程能获取到该锁，其它线程会被阻塞直到锁被开释。

之后应用新数组替换原数组，并开释锁，须要留神的就是在增加元素时，首先复制了一个快照，而后在快照上进行增加，而不是间接在原来数组上进行。

获取指定地位元素

应用 get(int index)办法获取下标为 index 的元素，如果元素不存在则抛出 IndexOutOfBoundsException 异样。

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

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

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

上述代码中，当某个线程调用 get 办法获取指定地位元素时，首先获取 array 数组，而后通过下标获取指定地位元素，这是两步操作，然而在整个过程中没有进行加锁同步。

假如 array 外面有元素 1，2，3。

因为第一步获取 array 和第二步依据下标拜访指定地位元素没有桎梏，这就可能导致线程 x 在执行第一步后第二步前，另外一个线程 y 进行了 remove 操作，假如删除1，remove 操作首先会获取独占锁，进行写时复制，也就是复制一份以后 array 数组而后在复制后的数组里删除线程 x 通过 get 办法拜访的元素1，之后让 array 指向新的数组。

而这时候 array 之前指向的数组的援用计数为 1 而不是 0，因为线程 x 还在应用它，这时线程 x 开始执行第二步，操作的数组是线程 y 删除元素之前的数组。

总结：尽管线程 y 曾经删除了 index 处的元素，然而线程 x 的第二步还是会返回 index 处的元素，这其实就是写时复制策略产生的弱一致性问题。

批改指定元素

应用 set(int index,E element)批改 list 中指定元素的值，如果指定元素的元素不存在则抛出 IndexOutOfBoundsException 异样。

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

该办法也是先获取独占锁，随后获取以后数组，并调用 get 办法后去指定地位元素，如果指定地位元素不等于新值则创立新数组并复制元素到新的数组中。

如果指定地位元素和新值一样，则为了保障 volatile 语义，还是须要从新设置 array，尽管 array 内容并没有变动。

该目标就是刷新一下缓存，告诉其余线程，也就是所谓的操作后果可见。

删除元素

删除 list 中指定元素，能够应用如下办法。

E remove(int index)
boolean remove(Object o)
Boolean remove(Object o,Object[] snapshot,int index)等

原理大抵相似，这里解说 remove(int 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();        }}

首先获取独占锁以保障删除数据期间其余线程不能对 array 进行批改，而后获取数组中要被删除的元素，并把残余的元素复制到新数组，之后应用新数组替换原来的数组，最初在返回前开释锁。

迭代器

上面来看 CopyOnWriteArrayList 中迭代器的弱一致性是怎么回事，所谓弱一致性是指返回迭代器后，其余线程对 list 的增删改对迭代器是不可见的，上面看看这是如何做到的。

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

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 boolean hasNext() {        return cursor < snapshot.length;    }    //获取元素    public E next() {        if (! hasNext())            throw new NoSuchElementException();        return (E) snapshot[cursor++];    }}

当调用 iterator 办法获取迭代器时实际上会返回一个COWIterator对象，COWIterator 对象的 snapshot 变量保留了以后 list 的内容，cursor 是遍历 list 时数据的下标。

为什么说 snapshot 是 list 的快照呢？明明是指针传递的援用，而不是正本。

如果在该线程应用返回的迭代器遍历元素的过程中，其余线程没有对 list 进行增删改，那么 snapshot 自身就是 list 的 array，因为它们是援用关系。

然而如果在遍历期间其余线程对该 list 进行了增删改，那么 snapshot 就是快照了，因为增删改后 list 外面的数组被新数组替换了，这时候老数组被snapshot援用。这也阐明获取迭代器后，应用该迭代器元素时，其余线程对该 list 进行的增删改不可见，因为它们操作的是两个不同的数组，这就是弱一致性。

总结

CopyOnWriteArrayList 应用写时复制的策略来保障 list 的一致性，而获取—批改—写入三步操作并不是原子性的，所以在增删改的过程中都应用了独占锁，来保障在某个工夫只有一个线程能对 list 数组进行批改。

另外 CopyOnWriteArrayList 提供了弱一致性的迭代器，从而保障在获取迭代器后，其余线程对 list 的批改是不可见的，迭代器遍历的数组是一个快照。

CopyOnWrite 并发容器用于读多写少的并发场景，毛病：内存占用问题、数据一致性问题（只能保证数据的最终一致性，不能保证数据的实时一致性）。