关于java:源码分析CopyOnWriteArrayList-中的隐藏的知识你Get了吗

40次阅读

共计 9132 个字符，预计需要花费 23 分钟才能阅读完成。

前言

本觉 CopyOnWriteArrayList 过于简略，寻思看名字就能晓得外部的实现逻辑，所以没有写这篇文章的想法，最近又认真看了下 CopyOnWriteArrayList 的源码实现，大体逻辑没有意外，不过还是发现很多有意思的中央，固留此篇文章分享之。

看完这篇文章你会理解到：

  • CopyOnWriteArrayList 的实现原理，扩容机制。
  • CopyOnWriteArrayList 的读写拆散，弱一致性。
  • CopyOnWriteArrayList 的性能如何。
  • CopyOnWriteArrayList 批改元素时，为什么雷同值也要从新赋值（作者 Doug Lea 这么写都是有情理的）。
  • CopyOnWriteArrayList 在高版本 JDK 的实现有什么不同，为什么。

<!– more –>

线程平安 List

在 Java 中，线程平安的 List 不止一个，除了明天的配角 CopyOnWriteArrayList 之外，还有 Vector 类和 SynchronizedList 类，它们都是线程平安的 List 汇合。在介绍 CopyOnWriteArrayList 之前，先简略介绍下另外两个。

如果你尝试你查看它们的源码，你会发现有点不对头，并发汇合不都是在 java.util.concurrent 包中嘛，为什么Vector 类和 SynchronizedList 类 这两个是在 java.util 包里呢？

的确是这样的，这两个线程平安的 List 和线程平安的 HashTable 是一样的，都是比较简单粗犷的实现形式，间接办法上减少 synchronized 关键字实现的，而且不论增删改查，通通加上，即便是 get 办法也不例外，没错，就是这么粗犷。

Vector 类的 get 办法：

// Vector 中的 get 操作增加了 synchronized
public synchronized E get(int index) {if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

SynchronizedList 类的 ge t 办法：

public E get(int index) {synchronized (mutex) {return list.get(index);}
}

同学无妨思考一下，其实在 get 办法上增加同步机制也是有起因的，尽管升高了效率，然而能够让写入的数据立刻能够被查问到，这也保障了数据的强一致性。另外下面对于 synchronized 简略粗犷的形容也是不够精确的，因为在高版本的 JDK 中，synchronized 曾经能够依据运行时状况，主动调整锁的粒度，前面介绍 CopyOnWriteArrayList 时会再次讲到。

CopyOnWriteArrayList

在 JDK 并发包中，目前对于 List 的并发汇合，只有 CopyOnWriteArrayList 一个。下面简略介绍了 Vector 和 SynchronizdList 的粗犷实现，既然还有 CopyOnWriteArrayList，那么它肯定是和下面两种是有区别的，作为惟一的并发 List，它有什么不同呢？

在探索 CopyOnWriteArrayList 的实现之前，咱们无妨先思考一下，如果是你，你会怎么来实现一个线程平安的 List。

  1. 并发读写时该怎么保障线程平安呢？
  2. 数据要保障强一致性吗？数据读写更新后是否立即体现？
  3. 初始化和扩容时容量给多少呢？
  4. 遍历时要不要保证数据的一致性呢？须要引入 Fail-Fast 机制吗？

通过类名咱们大抵能够猜测到 CopyOnWriteArrayList 类的实现思路：Copy-On-Write, 也就是写时复制策略；开端的 ArrayList 示意数据寄存在一个数组里。在对元素进行增删改时，先把现有的数据数组拷贝一份，而后增删改都在这个拷贝数组上进行，操作实现后再把原有的数据数组替换成新数组。这样就实现了更新操作。

然而这种写入时复制的形式必定会有一个问题，因为每次更新都是用一个新数组替换掉老的数组，如果不巧在更新时有一个线程正在读取数据，那么读取到的就是老数组中的老数据。其实这也是 读写拆散 的思维，放弃数据的强一致性来换取性能的晋升。

剖析源码 (JDK8)

下面曾经说了，CopyOnWriteArrayList 的思维是 写时复制 ， 读写拆散，它的外部保护着一个应用 volatile 润饰的数组，用来寄存元素数据。

/** The array, accessed only via getArray/setArray. */
private transient volatile Object[] array;

CopyOnWriteArrayList 类中办法很多，这里不会一一介绍，上面会剖析其中的几个罕用的办法，这几个办法了解后根本就能够把握 CopyOnWriteArrayList 的实现原理。

构造函数

CopyOnWriteArrayList 的构造函数一共有三个，一个是无参结构，间接初始化数组长度为 0；另外两个传入一个汇合或者数组作为参数，而后会把汇合或者数组中的元素间接提取进去赋值给 CopyOnWriteArrayList 外部保护的数组。

// 间接初始化一个长度为 0 的数组
public CopyOnWriteArrayList() {setArray(new Object[0]);
}
// 传入一个汇合，提取汇合中的元素赋值到 CopyOnWriteArrayList 数组
public CopyOnWriteArrayList(Collection<? extends E> c) {Object[] es;
    if (c.getClass() == CopyOnWriteArrayList.class)
        es = ((CopyOnWriteArrayList<?>)c).getArray();
    else {es = c.toArray();
        if (c.getClass() != java.util.ArrayList.class)
            es = Arrays.copyOf(es, es.length, Object[].class);
    }
    setArray(es);
}
// 传入一个数组，数组元素提取后赋值到 CopyOnWriteArrayList 数组
public CopyOnWriteArrayList(E[] toCopyIn) {setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

构造函数是实例创立时调用的，没有线程平安问题，所以构造方法都是简略的赋值操作，没有非凡的逻辑解决。

新增元素

元素新增依据入参的不同有好几个，然而原理都是一样的，所以上面只贴出了 add(E e) 的实现形式，是通过一个 ReentrantLock 锁保障线程平安的。

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
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); // 拷贝一个数据数组，长度 +1
        newElements[len] = e; // 退出新元素
        setArray(newElements); // 用新数组替换掉老数组
        return true;
    } finally {lock.unlock();
    }
}

具体步骤：

  1. 加锁，获取目前的数据数组开始操作（加锁保障了同一时刻只有一个线程进行减少 / 删除 / 批改操作）。
  2. 拷贝目前的数据数组，且长度减少一。
  3. 新数组中放入新的元素。
  4. 用新数组替换掉老的数组。
  5. finally 开释锁。

因为每次 add 时容量只减少了 1，所以每次减少时都要创立新的数组进行数据复制，操作实现后再替换掉老的数据，这必然会升高数据新增时候的性能。上面通过一个简略的例子测试 CopyOnWriteArrayList、Vector、ArrayList 的新增和查问性能。

public static void main(String[] args) {CopyOnWriteArrayList<Object> copyOnWriteArrayList = new CopyOnWriteArrayList<>();
    Vector vector = new Vector<>();
    ArrayList arrayList = new ArrayList();

    add(copyOnWriteArrayList);
    add(vector);
    add(arrayList);

    get(copyOnWriteArrayList);
    get(vector);
    get(arrayList);
}
public static void add(List list) {long start = System.currentTimeMillis();
    for (int i = 0; i < 100000; i++) {list.add(i);
    }
    long end = System.currentTimeMillis();
    System.out.println(list.getClass().getName() + ".size=" + list.size() + ",add 耗时:" + (end - start) + "ms");
}
public static void get(List list) {long start = System.currentTimeMillis();
    for (int i = 0; i < list.size(); i++) {Object object = list.get(i);
    }
    long end = System.currentTimeMillis();
    System.out.println(list.getClass().getName() + ".size=" + list.size() + ",get 耗时:" + (end - start) + "ms");
}

从测得的后果中能够看到 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<String> 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://stackoverflow.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<String> list = new CopyOnWriteArrayList<>();
list.add("www.wdbyte.com");
list.add("未读代码");

Iterator<String> 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<E> iterator() {return new COWIterator<E>(getArray(), 0);
}
static final class COWIterator<E> implements ListIterator<E> {
    /** 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://stackoverflow.com/que…

  1. What does volatile do?

http://www.cs.umd.edu/~pugh/j…

JDK 源码剖析系列文章

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

最初的话

文章曾经收录在 Github.com/niumoo/JavaNotes，欢送 Star 和指教。更有一线大厂面试点，Java 程序员须要把握的外围常识等文章，也整顿了很多我的文字，欢送 Star 和欠缺，心愿咱们一起变得优良。

文章有帮忙能够点个「赞 」或「 分享 」，都是反对，我都喜爱！
文章每周继续更新，要实时关注我更新的文章以及分享的干货，能够关注「未读代码」公众号或者我的博客。

正文完
java
发表至： java
2020-10-19
 0
关于java:JAVA线程安全性
夯实Java基础系列8深入理解Java内部类及其实现原理
tomcat设置默认路径致使项目url冲突解决方法
关于java:Java面试问题汇总SpringCloudDubboZookeeper