高并发容器之CopyOnWriteArrayList

CopyOnWriteArrayList

前面讲到，Collections可以将基础容器包装为线程安全的同步容器，但是这些同步容器包装类在进行元素迭代时并不能进行元素添加操作。

(1)CopyOnWriteArrayList原理：

CopyOnWrite(写时复制)就是在修改器对一块内存进行修改时，不直接在原有内存块上进行写操作，而是将内存复制一份，在新的内存中进行写操作，写完之后，再将原来的指针(或者引用)指向新的内存，原来的内存被回收。

CopyOnWriteArrayList是写时复制思想的一种典型实现，其含有一个指向操作内存的内部指针array，而可变操作(add、set等)是在array数组的副本上进行的。当元素需要被修改或者增加时，并不直接在array指向的原有数组上操作，而是首先对array进行一次复制，将修改的内容写入复制的副本中。写完之后，再将内部指针array指向新的副本，这样就可以确保修改操作不会影响访问器的读取操作。原理如下图所示：

(2)CopyOnWriteArrayList读取操作：

访问器的读取操作没有任何同步控制和锁操作，理由是内部数组array不会发生修改，只会被另一个array替换，因此可以保证数据安全。

//操作内存的引用 
private transient volatile Object[] array;
public E get(int index) {
        return get(getArray(), index);
}
//获取元素
private E get(Object[] a, int index) {
        return (E) a[index];
}
//返回操作内存
final Object[] getArray() {
        return array;
}

(3)CopyOnWriteArrayList写入操作

CopyOnWriteArrayList的写入操作add()方法在执行时加了独占锁以确保只能有一个线程进行写入操作，避免多线程写的时候会复制出多个副本。

这块给出的都是部分源代码，API中重载方法很多

 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();	//释放锁
        }
 }
 final void setArray(Object[] a) {
        array = a;
 }

从add()操作可以看出，在每次进行添加操作时，CopyOnWriteArrayList底层都是重新复制一份数组，再往新的数组中添加新元素，待添加完了，再将新的array引用指向新的数组。当add()操作完成后，array的引用就已经指向另一个存储空间了。

既然每次添加元素的时候都会重新复制一份，那就增加了内存的开销，如果容器的写操作比较频繁，那么其开销就比较大。所以，在实际应用中，CopyOnWriteArrayList并不适合进行添加操作。但是在并发场景下，迭代操作比较频繁，CopyOnWriteArrayList就是一个不错的选择。

(4)CopyOnWriteArrayList迭代器实现

CopyOnWriteArrayList有自己的迭代器，该迭代器不会检查修改状态，也无需检查状态。因为被迭代的array数组可以说是只读的，不会有其他线程能够修改它。

总结：

1.CopyOnWriteArrayList的优点：

读取、遍历操作不需要同步，速度会非常快。所以CopyOnWriteArrayList适用于读操作多、写操作相对较少的场景(读多写少)，比如可以在进行“黑名单”拦截时使用CopyOnWriteArrayList。

2.CopyOnWriteArrayList与ReentrantReadWriteLock的比较

CopyOnWriteArrayList和ReentrantReadWriteLock读写锁的思想非常类似，即读读共享、写写互斥、读写互斥、写读互斥。但是前者相比后者更进一步：为了将读取的性能发挥到极致，CopyOnWriteArrayList读取是完全不用加锁的，而且写入也不会阻塞读取操作，只有写入和写入之间需要进行同步等待，读操作的性能得到大幅提升。