精读JDK源码之CopyOnWriteArrayList

大家都知道ArrayList是线程不安全的，推荐我们自己加锁或者使用Collections.synchronizedList方法，其实JDK还提供了一种线程安全的List-CopyOnWriteArrayList,它的特征如下：

1、线程安全
2、通过锁+数组拷贝+volatile关键字保证了线程安全
3、每次数组操作，都会把数组拷贝一份出来，在新数组上进行操作，操作成功之后再赋值回去

整体思路

从整体讲，CopyOnWriteArrayList数据结构和ArrayList是一致的，底层是个数组

CopyOnWriteArrayList对数组进行操作时，会进行一下操作
1、加锁
2、从原数组中拷贝出新数组
3、在新数组上进行操作，并把新数组赋值给数组容器
4、解锁

另外CopyOnWriteArrayList底层数组采用volatile修饰，保证了可见性

不知道看到这里你是否和我有同样的疑问，既然加锁了，为什么还要加volatile关键字？

读到后面发现CopyOnWriteArrayList读操作并不会加锁，也就是不同线程操作可能拿到不同的锁（或者说有的不拿到锁），也就没法保证happens-before原则，volatile可以保证happens-before语意

新增

新增有很多种情况，比如新增到数组尾部、新增到数组某一个索引位置、批量新增等

首先是新增到数组尾部，源码如下:

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

可以看到，整个过程可以分为五步，加锁、新建数组拷贝原来数组、插入数据、给原来数组赋值、解锁

不知道看到这里你是否和我有同样的疑问，为什么要拷贝一份数据出来呢？

这里其实是和volatile有关，因为volatile修饰的是数组，线程的工作内存只拷贝了数组的引用，如果只改变数组值，无法触发可见性

再看指定位置插入数据

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

可以看到，如果插入位置正好是末尾，只需要拷贝一次。否则，会进行两次拷贝

删除

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

可以看得出，删除操作与新增操作类似。分为四步

1、加锁
2、判断索引位置，选择不同策略拷贝数组
3、给原来数组赋值
4、解锁

批量删除

源码如下：

public boolean removeAll(Collection<?> c) {
        if (c == null) throw new NullPointerException();
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            if (len != 0) {
                // temp array holds those elements we know we want to keep
                int newlen = 0;
                Object[] temp = new Object[len];
                for (int i = 0; i < len; ++i) {
                    Object element = elements[i];
                    if (!c.contains(element))
                        temp[newlen++] = element;
                }
                if (newlen != len) {
                    setArray(Arrays.copyOf(temp, newlen));
                    return true;
                }
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

从源码中可以看到，批量删除并不会直接对数组中得到元素挨个删除，而是先对数组中值进行循环判断，把不需要删除的放到临时数组中，最后临时数组中的数据就是我们不需要删除的数据（个人觉得这是一种空间换时间的思想，因为删除操作需要o(n)的时间复杂度）