「源码分析」CopyOnWriteArrayList中的隐藏的知识，你Get了吗？

从测得的结果中可以看到 CopyOnWriteArrayList 的新增耗时最久，其次是加锁的 Vector（Vector 的扩容默认是两倍）。而在获取时最快的是线程不安全的 ArrayList，其次是 CopyOnWriteArrayList，而 Vector 因为 Get 时加锁，性能最低。

java.util.concurrent.CopyOnWriteArrayList.size=100000,add耗时:2756ms
java.util.Vector.size=100000,add耗时:4ms
java.util.ArrayList.size=100000,add耗时:3ms
java.util.concurrent.CopyOnWriteArrayList.size=100000,get耗时:4ms
java.util.Vector.size=100000,get耗时:5ms
java.util.ArrayList.size=100000,get耗时:2ms

修改元素

修改元素和新增元素的思想是一致的，通过 ReentrantLock 锁保证线程安全性，实现代码也比较简单，本来不准备写进来的，但是在看源码时发现一个非常有意思的地方，看下面的代码。

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; // 指定位置赋新值
            setArray(newElements); // 替换掉老数组
        } else {
            // Not quite a no-op; ensures volatile write semantics
            setArray(elements);  // 有意思的地方来了
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

通过源码可以看到在修改元素前会先比较修改前后的值是否相等，而在相等的情况下，依旧 setArray(elements); 这就很奇妙了，到底是为什么呢？想了解其中的原因需要了解下 volatile 的特殊作用，通过下面这个代码例子说明。

// initial conditions
int nOnVolatileField= 0;
CopyOnWriteArrayList list = /* a single String */

// Thread 1
nOnVolatileField= 1;                 // (1)
list.set(0, "x");                     // (2)

// Thread 2
String s = list.get(0);               // (3)
if (s == "x") {
    int localVar = nonVolatileField;  // (4)
}
// 例子来自：https://***.com/questions/28772539/why-setarray-method-call-required-in-copyonwritearraylist

要想理解例子中的特殊之处，首先你要知道 volatile 可以防止指令重排，其次要了解 happens-before 机制。说简单点就是它们可以保证代码的执行前后顺序。

比如上面例子中的代码，1 会在 2 之前执行，3 会在 4 之前执行，这都没有疑问。还有一条是 volatile 修饰的属性写会在读之前执行，所以 2会在 3 之前执行。而执行顺序还存在传递性。所以最终 1 会在 4 之前执行。这样 4 获取到的值就是步骤 1 为 nonVolatileField 赋的值。如果 CopyOnWriteArrayList 中的 set 方法内没有为相同的值进行 setArray，那么上面说的这些就都不存在了。

删除元素

remove 删除元素方法一共有三个，这里只看public E 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); // 获取要删除的元素
        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(); // 解锁
    }
}

代码还是很简单的，使用 ReentrantLock 独占锁保证操作的线程安全性，然后使用删除元素后的剩余数组元素拷贝到新数组，使用新数组替换老数组完成元素删除，最后释放锁返回。

获取元素

获取下标为 index 的元素，如果元素不存在，会抛出IndexOutOfBoundsException 异常。

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

首先看到这里是没有任何的加锁操作的，而获取指定位置的元素又分为了两个步骤：

1. getArray() 获取数据数组。
2. get(Object[] a, int index) 返回指定位置的元素。

很有可能在第一步执行完成之后，步骤二执行之前，有线程对数组进行了更新操作。通过上面的分析我们知道更新会生成一个新的数组，而我们第一步已经获取了老数组，所以我们在进行 get 时依旧在老数组上进行，也就是说另一个线程的更新结果没有对我们的本次 get 生效。这也是上面提到的弱一致性问题。

迭代器的弱一致性

List list = new CopyOnWriteArrayList<>();
list.add("www.wdbyte.com");
list.add("未读代码");

Iterator iterator = list.iterator();
list.add("java");
while (iterator.hasNext()) {
    String next = iterator.next();
    System.out.println(next);
}

现在 List 中添加了元素 www.wdbyte.com 和 未读代码，在拿到迭代器对象后，又添加了新元素 java ,可以看到遍历的结果没有报错也没有输出 java 。也就是说拿到迭代器对象后，元素的更新不可见。

www.wdbyte.com
未读代码

这是为什么呢？要先从CopyOnWriteArrayList 的 iterator() 方法的实现看起。

public Iterator iterator() {
    return new COWIterator(getArray(), 0);
}
static final class COWIterator implements ListIterator {
    /** Snapshot of the array */
    private final Object[] snapshot;
    /** Index of element to be returned by subsequent call to next.  */
    private int cursor;

    private COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }
......

可以看到在获取迭代器时，先 getArray() 拿到了数据数组 然后传入到 COWIterator 构造器中，接着赋值给了COWIterator 中的 snapshot 属性，结合上面的分析结果，可以知道每次更新都会产生新的数组，而这里使用的依旧是老数组，所以更新操作不可见，也就是上面多次提到的弱一致性。

新版变化

上面的源码分析都是基于 JDK 8 进行的。写文章时顺便看了下新版的实现方式有没有变化，还真的有挺大的改变，主要体现在加锁的方式上，或许是因为 JVM 后来引入了 synchronized 锁升级策略，让 synchronized 性能有了不少提升，所以用了 synchronized 锁替换了老的 ReentrantLock 锁。

新增：

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

修改：

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;
        }
        // Ensure volatile write semantics even when oldvalue == element
        setArray(es);
        return oldValue;
    }
}

总结

通过上面的分析，得到下面几点关于 CopyOnWriteArrayList 的总结。

1. CopyOnWriteArrayList 采用读写分离，写时复制方式实现线程安全，具有弱一致性。
2. CopyOnWriteArrayList 因为每次写入时都要扩容复制数组，写入性能不佳。
3. CopyOnWriteArrayList 在修改元素时，为了保证 volatile 语义，即使元素没有任何变化也会重新赋值，
4. 在高版 JDK 中，得益于 synchronized 锁升级策略， CopyOnWriteArrayList 的加锁方式采用了 synchronized。

参考：

1. Why setArray() method call required in CopyOnWriteArrayList.

https://***.com/questions/28772539/why-setarray-method-call-required-in-copyonwritearraylist

2. What does volatile do?

http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html#volatile

JDK 源码分析系列文章

1. 集合 - 最通俗易懂的 HashMap 源码分析解读
2. 集合 - 还不懂 ConcurrentHashMap ？这份源码分析了解一下
3. 集合 - ArrayList和LinkedList如何实现的？我看你还有机会！

<完>

Hello world : ) 我是阿朗，一线技术工具人，认认真真写文章。

点赞的个个都是人才，不仅长得帅气好看，说话还好听。

文章持续更新，可以关注公众号「 程序猿阿朗 」或访问「未读代码博客 」。

回复【资料】有我准备的各系列知识点和必看书籍。

本文 Github.com/niumoo/JavaNotes 已经收录，有很多知识点和系列文章，欢迎Star。