17.0 第17章并发容器 17.1 写时复制的List和Set

发表于 2021-12-07 更新于 2021-12-08 分类于 9 Java编程的逻辑， 5第五部分并发，第17章并发容器 Waline：本文字数： 3.5k 阅读时长 ≈ 3 分钟

第17章并发容器

本章，我们探讨Java并发包中的容器类，具体包括：

写时复制的List和Set；
ConcurrentHashMap；
基于SkipList的Map和Set；
各种并发队列。

它们都有什么用？如何使用？与普通容器类相比，有哪些特点？是如何实现的？本章进行详细讨论。

17.1 写时复制的List和Set

本节先介绍两个简单的类：CopyOnWriteArrayList和CopyOnWriteArraySet，讨论它们的用法和实现原理。它们的用法比较简单，我们需要理解的是它们的实现机制。Copy-On-Write即写时复制，或称写时拷贝，这是解决并发问题的一种重要思路。

17.1.1 CopyOnWriteArrayList

CopyOnWriteArrayList实现了List接口，它的用法与其他List（如ArrayList）基本是一样的。CopyOnWriteArrayList的特点如下：

它是线程安全的，可以被多个线程并发访问；
它的迭代器不支持修改操作，但也不会抛出ConcurrentModificationException；
它以原子方式支持一些复合操作。

我们在15.2.3节提到过基于synchronized的同步容器的几个问题。迭代时，需要对整个列表对象加锁，否则会抛出ConcurrentModificationException,CopyOnWriteArrayList没有这个问题，迭代时不需要加锁。

基于synchronized的同步容器的另一个问题是复合操作，比如先检查再更新，也需要调用方加锁，而CopyOnWriteArrayList直接支持两个原子方法：

//不存在才添加，如果添加了，返回true，否则返回false
public boolean addIfAbsent(E e)
//批量添加c中的非重复元素，不存在才添加，返回实际添加的个数
public int addAllAbsent(Collection<? extends E> c)

CopyOnWriteArrayList的内部也是一个数组，但这个数组是以原子方式被整体更新的。每次修改操作，都会新建一个数组，复制原数组的内容到新数组，在新数组上进行需要的修改，然后以原子方式设置内部的数组引用，这就是写时复制。

所有的读操作，都是先拿到当前引用的数组，然后直接访问该数组。在读的过程中，可能内部的数组引用已经被修改了，但不会影响读操作，它依旧访问原数组内容。

换句话说，数组内容是只读的，写操作都是通过新建数组，然后原子性地修改数组引用来实现的。下面我们通过代码具体介绍（基于Java 7），包括内部组成、构造方法、add方法和indexOf方法。

内部数组声明为：

1	private volatile transient Object[] array;

注意：它声明为了volatile，这是必需的，以保证内存可见性，即保证在写操作更改之后读操作能看到。有两个方法用来访问/设置该数组：

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

在CopyOnWriteArrayList中，读不需要锁，可以并行，读和写也可以并行，但多个线程不能同时写，每个写操作都需要先获取锁。CopyOnWriteArrayList内部使用Reentrant-Lock，成员声明为：

1	transient final ReentrantLock lock = new ReentrantLock();

默认构造方法为：

1
2
3

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

上述代码就是设置了一个空数组。

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);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

上述代码也容易理解，add方法是修改操作，整个过程需要被锁保护，先获取当前数组elements，然后复制出一个长度加1的新数组newElements，在新数组中添加元素，最后调用setArray原子性地修改内部数组引用。

查找元素indexOf的代码为：

public int indexOf(Object o) {
    Object[] elements = getArray();
    return indexOf(o, elements, 0, elements.length);
}

先获取当前数组elements，然后调用另一个indexOf进行查找，具体代码就不列举了。这个indexOf方法访问的所有数据都是通过参数传递进来的，数组内容也不会被修改，不存在并发问题。

每次修改都要创建一个新数组，然后复制所有内容，这听上去是一个难以令人接受的方案，如果数组比较大，修改操作又比较频繁，可以想象，CopyOnWriteArrayList的性能是很低的。事实确实如此，CopyOnWriteArrayList不适用于数组很大且修改频繁的场景。它是以优化读操作为目标的，读不需要同步，性能很高，但在优化读的同时牺牲了写的性能。

之前我们介绍了保证线程安全的两种思路：一种是锁，使用synchronized或Reentrant-Lock；另外一种是循环CAS，写时复制体现了保证线程安全的另一种思路。锁和循环CAS都是控制对同一个资源的访问冲突，而写时复制通过复制资源减少冲突。对于绝大部分访问都是读，且有大量并发线程要求读，只有个别线程进行写，且只是偶尔写的场合，写时复制就是一种很好的解决方案。

写时复制是一种重要的思维，用于各种计算机程序中，比如操作系统内部的进程管理和内存管理。在进程管理中，子进程经常共享父进程的资源，只有在写时才复制。在内存管理中，当多个程序同时访问同一个文件时，操作系统在内存中可能只会加载一份，只有程序要写时才会复制，分配自己的内存，复制可能也不会全部复制，只会复制写的位置所在的^1。

17.1.2 CopyOnWriteArraySet

CopyOnWriteArraySet实现了Set接口，不包含重复元素，使用比较简单，我们就不赘述了。下面，主要介绍其内部组成，以及add与contains方法的代码。CopyOnWriteArraySet内部是通过CopyOnWriteArrayList实现的，其成员声明为：

1	private final CopyOnWriteArrayList<E> al;

在构造方法中被初始化，如：

1
2
3

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

其add方法代码为：

1
2
3

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

add方法就是调用了CopyOnWriteArrayList的addIfAbsent方法。

contains方法代码为：

1
2
3

public boolean contains(Object o) {
    return al.contains(o);
}

由于CopyOnWriteArraySet是基于CopyOnWriteArrayList实现的，所以与之前介绍过的Set的实现类如HashSet/TreeSet相比，它的性能比较低，不适用于元素个数特别多的集合。如果元素个数比较多，可以考虑ConcurrentHashMap或ConcurrentSkipListSet这两个类，我们稍后介绍。

简单总结下，CopyOnWriteArrayList和CopyOnWriteArraySet适用于读远多于写、集合不太大的场合，它们采用了写时复制，这是计算机程序中一种重要的思维和技术。

第17章 并发容器

17.1 写时复制的List和Set

17.1.1 CopyOnWriteArrayList

17.1.2 CopyOnWriteArraySet

第17章并发容器