CopyOnWriteArrayList

前言

作为java.util.concurrent包下的一员，CopyOnWriteArrayList是支持并发的List。但是，从它的名称我们就可以大体意识到，每当这个List发生了修改的时候，将会重新copy一份。无疑，CopyOnWriteArrayList适合读操作远远多于写操作的情况。

CopyOnWriteArrayList用于实现并发的策略很简单：在初始化后，存储值的数组Object[] array便被赋值，每当发生修改的时候，一个新的数组将会赋值给array，并且旧数组并不会被修改。再加上Iterator虽然基于创建时的array，但不支持修改操作（如set/remove/add)，所以所有曾经被复制给array的数组，在某种意义上，都是创建时便确定的不可变对象。而不可变对象，总是线程安全的。

导航

• 前言
• 构造方法
• add/remove
• removeAll
• iterator
• subList

构造方法

相对于ArrayList，CopyOnWriteArrayList由于采取了“写入即复制”的策略，所以不需要进行容量的设置以及扩容处理。

// volatile修饰，保证copy时的可见性
// 只能通过getArray/setArray访问
private transient volatile Object[] array;

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

public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] es;
    // 如果是CopyOnWriteArrayList，由于CopyOnWriteArrayList的array不可变，可以直接赋值，无需copy/clone数组
    if (c.getClass() == CopyOnWriteArrayList.class)
        es = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
        es = c.toArray();
        // 确保返回Object[]
        if (es.getClass() != Object[].class)
            es = Arrays.copyOf(es, es.length, Object[].class);
    }
    setArray(es);
}

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

add/remove

作为修改操作，CopyOnWriteArrayList会将array重新赋值。当热，这个过程中免不了加锁。

final transient Object lock = new Object();

public boolean add(E e) {
    synchronized (lock) { // 加锁
        Object[] es = getArray();
        int len = es.length;
        es = Arrays.copyOf(es, len + 1); // 复制array，同时保证容量
        es[len] = e; // 新数组添加新值
        setArray(es); // array赋新值
        return true;
    }
}

public E remove(int index) {
    synchronized (lock) { // 加锁
        Object[] es = getArray();
        int len = es.length;
        E oldValue = elementAt(es, index); // 获取旧值
        int numMoved = len - index - 1;
        Object[] newElements;
        if (numMoved == 0) // 删除末尾元素
            newElements = Arrays.copyOf(es, len - 1);
        else {
            newElements = new Object[len - 1];
            System.arraycopy(es, 0, newElements, 0, index); // copy index之前元素
            System.arraycopy(es, index + 1, newElements, index,
                             numMoved); // copy index之后元素
        }
        setArray(newElements);
        return oldValue; // 返回旧值
    }
}

removeAll

addAll实现思路与add相似，这里不再多说。我们来看一下removeAll方法：

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return bulkRemove(e -> c.contains(e)); // 批量操作
}

private boolean bulkRemove(Predicate<? super E> filter) {
    synchronized (lock) { // 加锁
        return bulkRemove(filter, 0, getArray().length);
    }
}

boolean bulkRemove(Predicate<? super E> filter, int i, int end) {
    // assert Thread.holdsLock(lock);
    final Object[] es = getArray();
    // Optimize for initial run of survivors
    // 获取实际开始下标
    for (; i < end && !filter.test(elementAt(es, i)); i++)
        ;
    if (i < end) {
        final int beg = i;
        final long[] deathRow = nBits(end - beg); // 使用bit set来表示是否需要删除（删除置1）
        int deleted = 1;
        deathRow[0] = 1L;   // set bit 0
        for (i = beg + 1; i < end; i++)
            if (filter.test(elementAt(es, i))) {
                setBit(deathRow, i - beg); // 删除置1
                deleted++; // 计数
            }
        // Did filter reentrantly modify the list?
        if (es != getArray())
            throw new ConcurrentModificationException();
        final Object[] newElts = Arrays.copyOf(es, es.length - deleted);
        int w = beg;
        for (i = beg; i < end; i++)
            if (isClear(deathRow, i - beg)) // 对应位为0（不删除）
                newElts[w++] = es[i];
        System.arraycopy(es, i, newElts, w, es.length - i);
        setArray(newElts);
        return true;
    } else {
        if (es != getArray())
            throw new ConcurrentModificationException();
        return false;
    }
}

// A tiny bit set implementation
// long[]的每一位代表着一个bit set的元素

private static long[] nBits(int n) {
    // long占64=2^6位，故n个元素需要((n - 1) >> 6) + 1个long
    return new long[((n - 1) >> 6) + 1];
}
private static void setBit(long[] bits, int i) {
    // 1L << i == 1L << (i%64)
    bits[i >> 6] |= 1L << i;
}
private static boolean isClear(long[] bits, int i) {
    return (bits[i >> 6] & (1L << i)) == 0;
}

iterator

注意到COWIterator基于创建时的array，所以无法获得最新的数据。

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

static final class COWIterator<E> implements ListIterator<E> {
    private final Object[] snapshot;
    private int cursor;

    COWIterator(Object[] es, int initialCursor) {
        cursor = initialCursor;
        snapshot = es; // 快照赋值
    }
}

subList

subList基于array，所以当通过subList获取原list的子视图后，若原list发生了修改，调用子视图方法将会抛出ConcurrentModificationException异常：

public static void main(String[] args) {
    var cowal = new CopyOnWriteArrayList<>(List.of(1, 2, 3));
    var sub = cowal.subList(1, 2);
    cowal.add(4); // 修改原list
    sub.get(0); //throws ConcurrentModificationException
}

public List<E> subList(int fromIndex, int toIndex) {
    synchronized (lock) { //加锁
        Object[] es = getArray();
        int len = es.length;
        int size = toIndex - fromIndex;
        if (fromIndex < 0 || toIndex > len || size < 0)
            throw new IndexOutOfBoundsException();
        return new COWSubList(es, fromIndex, size);
    }
}

private class COWSubList implements List<E>, RandomAccess {
    private final int offset;
    private int size;
    private Object[] expectedArray;

    COWSubList(Object[] es, int offset, int size) {
        // assert Thread.holdsLock(lock);
        expectedArray = es; // 设置expectedArray
        this.offset = offset;
        this.size = size;
    }

    public E get(int index) {
        synchronized (lock) {
            rangeCheck(index);
            checkForComodification();
            return CopyOnWriteArrayList.this.get(offset + index); // 调用外部类CopyOnWriteArrayList的方法
        }
    }

    private void checkForComodification() {
        // assert Thread.holdsLock(lock);
        if (getArray() != expectedArray) // 原list发生了修改
            throw new ConcurrentModificationException();
    }
}