JDK12源码分析_05 CopyOnWriteArrayList、CopyOnWriteArraySet 源码分析

• CopyOnWriteArrayList
• CopyOnWriteArraySet

CopyOnWriteArrayList

CopyOnWriteArrayList 是并发版的ArrayList。

它的本质是修改操作时，在底层复制一个数据库快照上进行，然后再把新的数组指针赋值给该集合。

所以原来已经开始遍历的还是用的旧的引用。即为写时复制策略。

接下来我们看一个英文的描述。

A thread-safe variant of java.util.ArrayList in which all mutative operations add, set, and so on are implemented by making a fresh copy of the underlying array. This is ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations, and is useful when you cannot or don’t want to synchronize traversals, yet need to preclude interference among concurrent threads. The “snapshot” style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException. The iterator will not reflect additions, removals, or changes to the list since the iterator was created. Element-changing operations on iterators themselves (remove, set, and add) are not supported. These methods throw UnsupportedOperationException. All elements are permitted, including null. Memory consistency effects: As with other concurrent collections, actions in a thread prior to placing an object into a CopyOnWriteArrayList.

我的翻译：

java.util.ArrayList的线程安全变体。其中所有的更改操作add、set等都是通过创建底层数组的新副本来实现的。这通常开销太大，但是当遍历操作的数量远远超过更改时，它可能比替代方法更有效；当您不能或不想同步遍历，但又需要排除并发线程之间的干扰时，它很有用。“快照”样式迭代器方法使用对创建迭代器时数组状态的引用。该数组在迭代器的生命周期内从未更改，因此不可能发生干扰，并且保证迭代器不会抛出ConcurrentModificationException。自创建迭代器以来，迭代器不会反映列表的添加、删除或更改。不支持对迭代器本身(删除、设置和添加)进行元素更改操作。这些方法抛出 UnsupportedOperationException。所有元素都是允许的，包括null。内存一致性效果:与其他并发集合一样，在将对象放入 CopyOnWriteArrayList之前，线程中的操作。

final transient Object lock = new Object();

private transient volatile Object[] array;
           

volatile Object[] array 这个数组用来存储数据。

这里我们可以看到JDK12已经放弃ReentrantLock了，而采用了 Object lock。

我们看一下官方解释为什么要换成这样？

The lock protecting all mutators. (We have a mild preference for builtin monitors over ReentrantLock when either will do.)

这里可以看出本质上监视器锁和ReentrantLock 可重入锁效果是一样的。这里使用监视器锁可以获得更好的性能。那我们不妨来看看它是怎样add操作的。

public boolean add(E e) {
        synchronized (lock) {
            Object[] es = getArray();
            int len = es.length;
            es = Arrays.copyOf(es, len + 1);
            es[len] = e;
            setArray(es);
            return true;
        }
    }
           

整个add的操作需要获得 Object lock 的监视器锁，被synchronized 包裹住了，所以同一时间只有一个线程能够执行add代码块里面的内容。

这在曾经的JDK版本里面，都是ReentrantLock 获取锁，然后再执行，最后释放锁的流程，现在修改成了synchronized 为了取得更好的性能，更简单的代码结构，不用再考虑finally释放锁的问题。

我们这里看到 Object[] es = getArray();是获取数组，Arrays.copyOf把数组进行了复制，并添加新元素，最后再把这个新数组的指针给这个集合setArray。add操作并没有在原数组上进行。

也就是说如果已经有循环在变老的数组，这里的setArray本质是指针操作，原数组引用依旧还在，依旧可以继续循环遍历。所以说他是add时复制策略。

这里我们也能看出add的操作的开销非常大，每一次的新增操作必然要复制Arrays.copyOf 老的数组。如果写入操作非常频繁的话，应该是不能使用这个集合的。CopyOnWriteArrayList 适合读多写少的场景。

接下来我们来看如何获取指定位置的元素

public E get(int index) {
        return elementAt(getArray(), index);
}
final Object[] getArray() {
        return array;
}    
static <E> E elementAt(Object[] a, int index) {
        return (E) a[index];
}
           

根据下标获取元素总共有三个方法，而这三个方法执行起来是没有加锁的，所以说如果元素不存在，还是会抛下标越界的异常 IndexOutOfBoundsException。

这里CopyOnWriteArrayList 体现了写时复制策略的弱一致性问题。getArray的过程中存在其他线程删除或修改数据。并且弱一致性问题也会影响set(int index, E element)修改指定位置元素的方法，同样会抛IndexOutOfBoundsException。

public E set(int index, E element) {
        synchronized (lock) {
            Object[] es = getArray();
            E oldValue = elementAt(es, index);

            if (oldValue != element) {
                es = es.clone();
                es[index] = element;
                setArray(es);
            }
            return oldValue;
        }
}
           

这里我们看set方法，依旧是被包在synchronized 监视器锁里面的，如果新对象和老对象不一致，只会创建新的数组并复制元素，再把新数组要修改的修改好了，设置setArray到集合array上面。

老版本的JDK不管新对象和老对象是否一致，都会重新修改array得指针，现在JDK12不会有这个没有意义的操作了。是否可以考虑成synchronized 监视器锁里面不需要考虑volatile 的 array 语义一致性问题。

删除操作也是一样，如果是删除末尾的元素，直接复制之前的元素。

如果是删除中间的元素，那么会进行两次复制，把一头一尾两段数组拼接起来组成新的数组，替代老的数组。

接下来我们举个例子。

// 陈涛版权所有，禁止转载，QQ邮箱：[email protected]
    public static void main(String[] args) {
        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<String>();
        list.add("chentao1");
        list.add("chentao2");

        Iterator<String> iterator = list.iterator();
        list.add("chentao3");

        System.out.println("Iterator迭代器输出：");
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

        System.out.println("Consumer消费者模式输出：");
        list.forEach(new Consumer<String>() {
            public void accept(String s) {
                System.out.println(s);
            }
        });

        List<String> arrayList = new ArrayList<String>(list);
        Iterator<String> iteratorArrayList = arrayList.iterator();
        arrayList.add("chentao4");
        // 抛出异常 java.util.ConcurrentModificationException
        while (iteratorArrayList.hasNext()) {
            System.out.println(iteratorArrayList.next());
        }
    }
           

输出：

Iterator迭代器输出：

chentao1

chentao2

Consumer消费者模式输出：

chentao1

chentao2

chentao3

Exception in thread “main” java.util.ConcurrentModificationException

这里可以看出执行了list.iterator();以后再对CopyOnWriteArrayList集合进行新增操作不会影响Iterator迭代器输出。

list.forEach(new Consumer() {…}）是JDK8以后新增的消费者forEach模式，需要自己实现accept方法，也可以传入Lambda 表达式（Lambda允许把函数作为一个方法的参数）。

ArrayList如果使用Iterator之后再修改集合，就会抛出ConcurrentModificationException异常。原因是checkForComodification的判断 modCount != expectedModCount

final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
           

CopyOnWriteArraySet

CopyOnWriteArraySet的原理和CopyOnWriteArrayList非常相似，接下来我们看一下构造函数就明白了。

private final CopyOnWriteArrayList<E> al;

public CopyOnWriteArraySet() {
    al = new CopyOnWriteArrayList<E>();
}
           

CopyOnWriteArraySet底层就是CopyOnWriteArrayList al 来保存数据的，所有操作当然也是依赖List的，接下来我们介绍不一样的地方。

Set最重要的功能是去除重复，我们来看是怎样实现的。

public boolean add(E e) {
        return al.addIfAbsent(e);
    }
           

这里我们看到 add的方法的本质是 CopyOnWriteArrayList的addIfAbsent，我们去看一下CopyOnWriteArrayList的源码。

public boolean addIfAbsent(E e) {
        Object[] snapshot = getArray();
        return indexOfRange(e, snapshot, 0, snapshot.length) < 0
            && addIfAbsent(e, snapshot);
    }
           

这里依旧是在snapshot 镜像上面操作的。

indexOfRange本质是for循环进行equals比较，他有从前往后循环和从后往前循环两种模式。

如果indexOfRange没有找到这个元素，会执行addIfAbsent(e, snapshot)，里面的代码是包含在synchronized里面的，最终还是Arrays.copyOf复制数组增加元素，并设置新数组给集合。

所以这里的CopyOnWriteArraySet和Map结构完全没有关系，本质是一个数组！