并发容器之写时拷贝的list和set

对于一个对象来说，我们为了保证它的并发性，通常会选择使用声明式加锁方式交由我们的 Java 虚拟机来完成自动的加锁和释放锁的操作，例如我们的 synchronized。也会选择使用显式锁机制来主动的控制加锁和释放锁的操作，例如我们的 ReentrantLock。但是对于容器这种经常发生读写操作的类型来说，频繁的加锁和释放锁必然是影响性能的，基于此，jdk 中为我们集成了很多适用于不同并发场景下的优秀容器类，本篇以及接下来的几篇文章，我们将学习这些并发容器类的基本使用以及实现原理。本篇的主要内容如下：

• 同步容器的几种实现及其核心缺陷
• 并发容器之 CopyOnWriteArrayList
• 并发容器之 CopyOnWriteArraySet

一、同步容器的几种实现及其核心缺陷

在介绍并发容器之前，我们想先简单介绍下 jdk 中几种常见的同步容器并通过对比同步容器的缺陷来凸显我们并发容器相对于它的优势点。

//返回一个线程安全的 Collection 集合
public static <T> Collection<T> synchronizedCollection(Collection<T> c)

//返回一个线程安全的 List 集合
public static <T> List<T> synchronizedList(List<T> list)

//返回一个线程安全的 Map 集合
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)

这三个容器就隶属于我们的同步容器，它们是线程安全的，区别于原生的 List 和 Map 以及 Collection。当然它的线程安全特性的实现也是粗暴的，我们跟进去看看：

public static <T> Collection<T> synchronizedCollection(Collection<T> c) {
    return new SynchronizedCollection<>(c);
}

static class SynchronizedCollection<E> implements Collection<E>, Serializable {

   final Collection<E> c;  // Backing Collection
   final Object mutex;     // Object on which to synchronize

   SynchronizedCollection(Collection<E> c) {
       this.c = Objects.requireNonNull(c);
       mutex = this;    //信号量指向当前容器对象本身
    }

   SynchronizedCollection(Collection<E> c, Object mutex) {
       this.c = Objects.requireNonNull(c);
       this.mutex = Objects.requireNonNull(mutex);
   }

   public int size() {
       synchronized (mutex) {return c.size();}
   }
   public boolean isEmpty() {
       synchronized (mutex) {return c.isEmpty();}
   }
   public boolean contains(Object o) {
       synchronized (mutex) {return c.contains(o);}
   }
   ..........省略其他方法
}

很明显，Collections 给我们返回的同步容器是 Collections 的子类实现，而在该子类的实现中并没有增加额外的任何一个方法，仅仅将父类中所有方法增加 synchronized 关键字修饰。这样，所有想要访问该容器的线程都需要首先获得该 Collections 实例的锁，进而保证了线程安全。那么这么做也不能完全保证容器的线程安全特性，例如在以下的几种情况下，线程的安全特性是得不到保证的：

• 复合操作
• 迭代操作

1、复合操作

//自定义一个类
public class CompoundOperations {
    
    private List list;
    
    public CompoundOperations(List list) {
        this.list = Collections.synchronizedList(list);
    }
    
    public void addIfAbsent(Object obj) {
        int size = list.size();
        if(size == 0) {
            list.add(obj);
        }
    }
}

如上，我们定义了一个 CompoundOperations 类，在该类创建时，我们会为其 list 属性注入一个线程安全的同步容器 List 实例。现在模拟多个线程同时访问同一个 CompoundOperations 实例的 addIfAbsent 方法，原先线程安全的 list，现在还安全吗？

线程 A 和线程 B 同时获取到 list 的 size 属性的值，假设都为 0，然后各自都往容器中添加一个元素，原本要求只有在容器为空的时候才能向其中添加元素，在多线程的情况下，该条件显然已经不足以成为限制。虽然我能保证 list 集合的所有操作都是线程安全的，但是我不能保证你对 list 复合操作下的线程依然安全。这就是复合操作下对同步容器线程安全特性的一个冲击。

2、迭代操作

public static void main(String[] args) {
    List<String> list = Collections.synchronizedList(new ArrayList());
    list.add("single");
    list.add("walker");
    list.add("hello");
    Thread thread1 = new Thread() {
        @Override
        public void run() {
            //迭代容器
            for(String value : list) {
                System.out.println(value);
            }
        }
    };
    Thread thread2 = new Thread() {
        @Override
        public void run() {
            //更改容器结构
            try {
                Thread.sleep(10);
            } catch (InterruptedException e) {}
            list.add("world");
        }
    };
        
    thread1.start();
    thread2.start();
}

程序运行输出的结果如下：

这个 ConcurrentModificationException 异常，我们以前的分析 ArrayList 源码的时候也曾经提及过。这是容器迭代的时候由于其他线程将该容器的内部结构更改导致的，也就是说容器在迭代的时候是不允许发生 add，remove 操作的。显然，无论是我们原生的 List 集合或是这里的同步 List 集合都没有解决这样的一个问题。这是另一个对同步容器线程安全特性的冲击。

上述简单的介绍了同步容器的一些简单的实现原理，以及存在一些不足缺陷，下面我们将详细看看 jdk 中都分别有哪些并发容器，各自又都具有怎样的适用场景。

二、并发容器之 CopyOnWriteArrayList

CopyOnWriteArrayList 是一款基于写时拷贝的并发容器，其基本操作和 ArrayList 一样，我们主要来分析下它是如何支持并发操作的。首先看读取操作：

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

和 ArrayList 一样，内部封装了一个 Object 数组，通过索引可以随机访问集合中的元素。但是与 ArrayList 不同的是，ArrayList 中调用 get 方法将直接返回相应的数组元素，而我们的 CopyOnWriteArrayList 拷贝了一份当前数组并调用另一个 get 方法根据传入的数组及索引进行返回。

也就是说，在 CopyOnWriteArrayList 中，所有的读操作都是先拷贝一份当前数组调用另一个方法进行数据的返回。但是所有的写操作都是需要加锁的，CopyOnWriteArrayList 使用显式锁 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 {
            setArray(elements);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

可以看到，写操作虽然是加了锁了，但是进行更新的时候还是基于整个数组进行更新的。写操作之前，先拷贝一份当前数组：

 Object[] elements = getArray();

写操作完成之时，整体上重置原数组：

setArray(newElements);

那么这样看来，多线程之间可以并发的读取，可以并发的写入，并且多线程之间还可以读写并发进行。

对于同步容器不能保证复合操作下的线程安全的情况，CopyOnWriteArrayList 做了一些解决，但并不彻底。例如，它提供了两个原子性的复合操作：

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

这两个方法内部是使用的显式锁进行实现的，所以整体上看这两个方法也是线程安全的。

另外需要说的一点就是 CopyOnWriteArrayList 的迭代器，它的迭代器是不支持修改操作的。例如：

public void remove() {
   throw new UnsupportedOperationException();
}

public void set(E e) {
   throw new UnsupportedOperationException();
}

public void add(E e) {
   throw new UnsupportedOperationException();
}

也就是说，在迭代 CopyOnWriteArrayList 的时候，你只能调用他的 next 方法返回下一个元素的值，而不能进行 add ，remove 等操作。和原生的 ArrayList 不同的是，CopyOnWriteArrayList 直接不支持在迭代的时候对容器进行修改，而 ArrayList 本身的迭代器是支持迭代中更改容器结构的，但是前提是你得调用 iterator 中更改的方法对容器结构进行更改，一旦你调用了 ArrayList 中更改容器结构的方法，那么下一次迭代必然报错，这就是两者的区别。

至于我们未提到的写时拷贝的 Set，Set 的内部是基于我们上述的 CopyOnWriteArrayList ，但是区别在于 Set 中的元素要求不可重复，其他的实现基本类似，此处不再赘述。

最后，我们对这种基于写时拷贝思想的容器做一点小结。写时拷贝在每次写操作的时候都需要完全复制一份原数组，并在写操作完成后重置原数组的引用。这种并发容器只有在写操作不是很频繁的场景下才具有更高的效率，一旦写操作过于频繁，那么程序消耗的资源也是急剧上升的。