并发List：CopyOnWriteArrayList

CopyOnWriteArrayList

适合写多读少

介绍

JUC包中的并发List只有CopyOnWriteArrayList。CopyOnWriteArrayList是一个线程安全的ArrayList，使用了写时复制策略，对其进行的修改操作都是在底层的一个复制的数组上进行的。

• CopyOnWriteList 实现的接口和 ArrayList 完全相同，所以 ArrayList 提供的 api ，CopyOnWriteArrayList 也提供

• 其实说白了就是每次要增、删、改的时候，会创建一个新的 array，并把旧的 array 全部复制过来，操作完后再让 array 指向这个新创建的 array，所以也不存在什么扩容问题，因为每次 add 都要扩容

CopyOnWriteArrayList类图中

• 每个CopyOnWriteArrayList对象有一个array数组存放具体元素
• ReentrantLock独占锁用来保证只有一个线程对array进行修改。

属性

/** The lock protecting all mutators */
final transient ReentrantLock lock = new ReentrantLock();

/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array; // 存放具体元素

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

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

构造函数

CopyOnWriteArrayList 内部包含一个array存放具体元素：

• 无参构造函数在内部创建了一个大小为0的object数组作为array的初始值
• 有参构造函数
  • 数组：创建一个list，内部元素是入参toCopyIn的副本
  • 入参为集合，将集合里的元素复制到副本list

/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;
public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}
// 有参构造函数
// 创建一个list，内部元素是入参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);
}

关于“c.toArray might (incorrectly) not return Object[] (see 6260652)”的注释可参考《JDK1.6集合框架bug：c.toArray might (incorrectly) not return Object[] (see 6260652)》。

源码解析

add

操作：add过程加了锁，所以是原子操作

1. 获取独占锁（保证同时最多有一个线程调用此方法，其他线程会被阻塞直到锁被释放。）
2. 获取array后，将array复制到新数组（从代码可知新数组的长度比原长度大1，所以CopyOnWriteArrayList是无界list），把新增元素添加到新数组（将元素赋值了一个快照，然后在快照上进行添加）
3. 使用新数组替换原数组，在返回前释放独占锁

• 不指定索引

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    //上锁，同一个 CopyOnWriteList 对象的 增、删、改都使用的同一把锁
    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();
    }
}

• 指定索引

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)
            // 不是的话，那直接把全部元素拷贝到一个 size 增加 1 的新数组上
            newElements = Arrays.copyOf(elements, len + 1);
        else {
            // 否则，自己 new 一个 size + 1 的数组，然后执行分段拷贝
            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();
    }
}

get(int index)

使用E get(int index)获取下标为index的元素，如果元素不存在则抛出IndexOutOfBoundException异常。

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

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

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

获取指定位置的元素需要两步：

1. 获取array，
2. 然后通过下标访问指定位置的元素。

整个过程没有加锁，在多线程下会出现弱一致性问题。

假设某一时刻CopyOnWriteArrayList中有1，2，3中三个元素，如下图所示：

由于整个过程未加锁，可能导致一个线程x在获取array后，另一个线程y进行了remove操作，假设要删除的元素为3。remove操作首先会获取独占锁，然后进行写时复制操作，也就是复制一份当前array数组，然后再复制的数组里面删除线程x通过get方法要访问的元素3，之后让array指向复制的数组。而这时线程x仍持有对原来的array的引用，导致虽然线程y删除了元素3，线程x仍能获得3这个元素，如图：

set(int index, E element)

使用E set(int index, E element)方法修改指定元素的值，如果指定位置的元素不存在则抛出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;
            // 设置新数组到array
            setArray(newElements);
        } else {
            // Not quite a no-op; ensures volatile write semantics
            // 重新设置数组
            setArray(elements); 
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

首先获取独占锁，从而阻止其他线程对array数组进行修改，然后获取当前数组，并调用get方法获取指定位置的元素，如果指定位置的元素值与新值不一致就创建新数组并复制元素，然后在新数组上修改指定位置的元素值并设置新数组到array。即使指定位置的元素值与新值一样，为了保证volatile语义，也需要重新设置array（此处可参看《CopyOnWriteArrayList与java内存模型》）。

remove

删除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);
        // index之后的元素个数
        int numMoved = len - index - 1;
        // 被删除的元素是最后一个 直接新数组长度减小1拷贝过去
        if (numMoved == 0)
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            // 否则 new 一个长度减小 1 的新数组，然后分段拷贝
            // 分两次复制删除后剩余的元素到新数组
            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();
    }
}

首先获取独占锁以保证线程安全，然后获取要被删除的元素，并把剩余的元素复制到新数组，之后使用新数组替换原来的数组，最后在返回前释放锁。

迭代器(弱一致性)

弱一致性指返回迭代器后，其他线程对list的改动对迭代器时不可见的。

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

static final class COWIterator<E> implements ListIterator<E> {

    // array的快照
    // 所以如果在迭代过程中，进行了增删，是不会影响迭代的，因为迭代的是 snapshot 快照（也就是修改后要丢弃的老数组）
    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++]; // 从 snapshot 取值
    }
}

调用iterator()方法时实际上会返回一个COWIterator对象，COWIterator对象的snapshot变量保存了当前list的内容。之所以说snapshot是list的快照是因为虽然snapshot获得了array的引用，但当其他线程修改了list时，array会指向新复制出来的数组，而snapshot仍指向原来array指向的数组，两者操作不同的数组，这就是弱一致性。

以下为弱一致性的示例：

public class CopyListTest {
    private static volatile CopyOnWriteArrayList<String> arrayList  = new CopyOnWriteArrayList<>();

    public static void main(String[] args) throws InterruptedException {
        arrayList.add("Java");
        arrayList.add("Scala");
        arrayList.add("Groovy");
        arrayList.add("Kotlin");

        Thread threadOne = new Thread(new Runnable() {
            @Override
            public void run() {
                arrayList.set(0, "hello");
                arrayList.remove(2);
            }
        });

        // 在修改之前获取迭代器
        Iterator<String> it = arrayList.iterator();

        threadOne.start();

        // 等待子线程执行完毕
        threadOne.join();

        // 迭代
        while(it.hasNext()) {
            System.out.println(it.next());
        }

        System.out.println("=========================================");

        // 再次迭代
        it = arrayList.iterator();
        
        // 迭代
        while(it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

输出如图：

由上可知，对list的修改对于首次迭代是不可见的，这即是弱一致性的体现。

问题总结

何时初始化list，初始化list的元素个数是多少，list是有限大小吗？

CopyOnWriteArrayList 在创建时并不会立即初始化 list ，只有在第一次添加元素操作时才会进行初始化，这样可以节约内存空间。此时初始化的元素个数为 0 ，如果需要指定初始容量，可以通过使用带参数的构造函数或者工厂方法来指定。

CopyOnWriteArrayList 是没有固定大小限制的，它的大小会根据插入的元素自动扩展以容纳更多元素。由于该集合的写操作需要复制原有的集合并修改新集合，因此对于大规模数据或频繁修改的操作，使用 CopyOnWriteArrayList 可能会增加内存消耗和延迟，因此需要根据具体情况选择是否使用该集合。

如何保持线程安全，比如多个线程进行读写如何保证是线程安全？

CopyOnWriteArrayList 通过对写操作进行复制和修改，从而在保持线程安全的同时支持并发读操作。具体来说，它的实现机制如下：

1. 当执行一个写操作（如 add、set 等）时，CopyOnWriteArrayList 会先复制一份当前的内部数组（即快照），然后对新的内部数组进行修改，而原来的内部数组不会改变。
2. 写操作结束后，CopyOnWriteArrayList 将新的内部数组赋值给内部的 volatile 变量 array，这样其他线程就能够看到最新的数组。
3. 对于读操作（如 get、iterator 等），CopyOnWriteArrayList 直接从当前的内部数组中读取元素，这样就不用加锁了。

由于读操作不需要加锁，多个线程可以同时进行读操作，这样就提高了并发读的性能。而对于写操作，虽然每次写操作都要复制一份内部数组，但由于写操作相对较少，并且采用了“写时复制”的机制，因此总体上还是比较高效的。

因此，多个线程进行读写操作时，CopyOnWriteArrayList 能够保证线程安全，而且读操作的性能较高，适用于读多写少的场景。

如何保证使用迭代器遍历list时的数据一致性？

CopyOnWriteArrayList 使用迭代器遍历 list 时，能够保证遍历过程中数据的一致性，即迭代器遍历到的元素都是在迭代器创建时的快照中存在的元素。

具体来说，迭代器会从 CopyOnWriteArrayList 当前的内部数组中读取元素进行遍历，而这个内部数组是通过“写时复制”机制来维护的。也就是说，如果在遍历过程中有其他线程修改了 CopyOnWriteArrayList 的内容，那么它们实际上会修改一个新的内部数组，在修改完成后，CopyOnWriteArrayList 会将新的内部数组赋值给内部的 volatile 变量 array，因此迭代器不会受到这些修改的影响。

同时，由于 CopyOnWriteArrayList 中每个元素的值都不会被改变，因此在遍历过程中，每个元素的值都是一定不变的，保证了迭代器遍历时元素的一致性。

需要注意的是，由于 CopyOnWriteArrayList 采用“写时复制”的机制来增加、删除或更新元素，因此在使用迭代器遍历时，不能对 CopyOnWriteArrayList 进行修改操作，否则会抛出 UnsupportedOperationException 异常。