[Java知识库]波吉学源码——CopyOnWriteArrayList源码剖析

CopyOnWriteArrayList源码剖析

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

在CopyOnWriteArrayList的类图中，每个CopyOnWriteArrayList对象里有一个array数组对对象用来存放具体元素，ReentrantLock独占锁对象用来保证同时每个线程对array修改。

构造方法

无参构造方法通过setArray()初始化一个大小为0的数组

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

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

将集合中的元素复制到数组中

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

传入一个数组，通过Arrays.copyOf()方法赋值给array数组

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

添加元素

其它添加元素的原理与下面函数原理一致，所以只讲解add(E e)方法

public boolean add(E e) {
    //1.获取独占锁
    final ReentrantLock lock = this.lock;
    //2.上锁，确保只有一个线程可以操作数组
    lock.lock();
    try {
        //3.获取到array数组
        Object[] elements = getArray();
        int len = elements.length;
        //4.复制一个长度比原来+1的新数组
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        //5.将元素添加到新数组的末尾
        newElements[len] = e;
        //6.将新数组替换了array数组
        setArray(newElements);
        return true;
    } finally {
        //7.解锁
        lock.unlock();
    }
}

需要注意的是，在添加元素时，首先复制了一个快照，然后在快照上进行操作，而不是直接在原数组上操作

修改指定位置元素

public E set(int index, E element) {
    //1.获取独占式锁(可重入锁)
    final ReentrantLock lock = this.lock;
    //2.上锁
    lock.lock();
    try {
        //3.获取一个当前数组的快照
        Object[] elements = getArray();
        //4.获取指定位置的元素
        E oldValue = get(elements, index);
        //5.如果该位置的元素和element不相当，执行替换操作
        if (oldValue != element) {        
            int len = elements.length;
            //复制一个快照的数组在该数组上操作
            Object[] newElements = Arrays.copyOf(elements, len);
            newElements[index] = element;
            setArray(newElements);
        } else {
            //6.如果该位置的元素和element相等那么就不做更改
            setArray(elements);
        }
        return oldValue;
    } finally {
        //7.解锁
        lock.unlock();
    }
}

删除指定位置元素

其它删除元素的函数与下面函数原理一致

public E remove(int index) {
    //1.获取独占锁
    final ReentrantLock lock = this.lock;
    //2.上锁
    lock.lock();
    try {
        //3.获取快照数组
        Object[] elements = getArray();
        int len = elements.length;
        //4.获取指定位置元素的值和
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        //5.如果删除的是最后一个元素
        if (numMoved == 0)
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            //6.如果不是最后一个元素，分两次复制数组
            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 {
        //7.解锁
        lock.unlock();
    }
}

获取指定位置元素

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

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

在如上代码中，当线程x调用get方法获取指定位置的元素时，分两步走

1. 获取array数组
2. 通过下标获取元素

注意整个过程没有加锁！由于执行两个过程的时候没有加锁，这就可能导致线程x执行完步骤1之后执行步骤2，另外一个线程y执行了remove操作，假设要删除元素1，remove操作首先会获取独占式锁，然后进行写时复制操作，也就是复制了一份当前的array数组，然后在复制的数组里删除线程x通过get方法要返回的元素1，之后让array指向复制的数组。而这时候array之前指向的数组的引用计数器为1而不是0，因为线程x还在使用它，这个时候线程x执行步骤2，步骤2操作的数组是线程y删除元素之前的数组

所以，虽然线程y已经删除了index处的元素，但是由于线程x的步骤1首先获得了array数组所以步骤2还是会返回原本index的元素，这就是写时复制策略产生的弱一致性问题

弱一致性的迭代器

所谓弱一致性是指返回迭代器以后，其他线程对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;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        if (! hasNext())
            throw new NoSuchElementException();
        return (E) snapshot[cursor++];
    }

}

为什么说snapshot是list的快照呢？如果在遍历期间其它线程对list进行增删改，那么snapshot就是快照了，因为增删改会将新数组替换

总结

CopyOnWriteArrayList使用写时复制策略来保证list的一致性，而获取-修改-写入三步操作并不是原子性的，所以在操作的时候使用了独占锁，来保证某个时刻只有一个线程对list操作，另外CopyOnWriteArrayList提供了弱一致性的遍历器，从而保证在获取迭代器后，其他线程对list不可见。