CopyOnWriteArrayList是ArrayList的一个线程安全的变体，其中所有可变操作（add、set 等等）都是通过对底层数组进行一次新的复制来实现的。

CopyOnWriteArrayList是一个写时复制的容器，采用了读写分离的思想。通俗点来讲，在对容器进行写操作时，不直接修改当前容器，而是先对当前容器进行拷贝得到一个副本，然后对副本进行写操作，最后再将原容器的引用指向拷贝出来的副本。这样做的好处就是可以对容器进行并发读而不用进行加锁。

一、类的继承关系

1
2
public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

含义不需要再赘述了。

二、类的属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/** 用于在对数组产生写操作的方法加锁. */
final transient ReentrantLock lock = new ReentrantLock();

/** 底层的存储结构. */
private transient volatile Object[] array;

/** 反射机制. */
private static final sun.misc.Unsafe UNSAFE;

/** lock域的内存偏移量.是通过反射拿到的 */
private static final long lockOffset;

static {
    try {
        UNSAFE = sun.misc.Unsafe.getUnsafe();
        Class<?> k = CopyOnWriteArrayList.class;
        lockOffset = UNSAFE.objectFieldOffset
            (k.getDeclaredField("lock"));
    } catch (Exception e) {
        throw new Error(e);
    }
}

三、数组末尾添加一个元素

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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();
    }
}

基本原理很简单，就是对当前数组加锁，内部复制一个新数组，处理完毕，修改引用即可，达到最终一致的效果。

四、如果没有这个元素则添加

1
2
3
4
5
public boolean addIfAbsent(E e) {
    Object[] snapshot = getArray();
    return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
        addIfAbsent(e, snapshot);
}

该函数用于添加元素（如果数组中不存在，则添加；否则，不添加，直接返回）。如何可以保证多线程环境下不会重复添加元素？

答案：通过快照数组和当前数组进行对比来确定是否一致，确保添加元素的线程安全

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
private boolean addIfAbsent(E e, Object[] snapshot) {
    // 重入锁
    final ReentrantLock lock = this.lock;
    // 获取锁
    lock.lock();
    try {
        // 获取数组
        Object[] current = getArray();
        // 数组长度
        int len = current.length;
        if (snapshot != current) { // 快照不等于当前数组，对数组进行了修改
            // 取较小者
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++) // 遍历
                if (current[i] != snapshot[i] && eq(e, current[i])) // 当前数组的元素与快照的元素不相等并且e与当前元素相等
                    // 表示在snapshot与current之间修改了数组，并且设置了数组某一元素为e，已经存在
                    // 返回false
                    return false;
            if (indexOf(e, current, common, len) >= 0) // 在当前数组中找到e元素
                    // 返回false
                    return false;
        }
        // 复制数组
        Object[] newElements = Arrays.copyOf(current, len + 1);
        // 对数组len索引的元素赋值为e
        newElements[len] = e;
        // 设置数组
        setArray(newElements);
        return true;
    } finally {
        // 释放锁
        lock.unlock();
    }
}

该函数的流程如下：

  1. 获取锁，获取当前数组为current，current长度为len，判断数组之前的快照snapshot是否等于当前数组current，若不相等，则进入步骤2；否则，进入步骤3
  2. 不相等，表示在snapshot与current之间，对数组进行了修改，直接返回false结束;
  3. 说明当前数组等于快照数组，说明数组没有被改变。在当前数组中索引指定元素，若能够找到，说明已经存在此元素，直接返回false结束；否则进入4
  4. 说明没有当前要插入的元素，通过数组复制的方式添加到末尾
  5. 无论如何，都要释放锁

五、获取指定索引的元素

1
2
3
4
5
6
7
public E get(int index) {
    return get(getArray(), index);
}

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

通过写时复制的方式，CopyOnWriteArrayList 的 get 方法不用加锁也可以保证线程安全，所以 CopyOnWriteArrayList 并发读的效率是非常高的，它是直接通过数组下标获取元素的。

六、总结

简单而言要记住它的三个特点：
  • CopyOnWriteArrayList 是一个并发的数组容器，它的底层实现是数组。
  • CopyOnWriteArrayList 采用写时复制的方式来保证线程安全。
  • 通过写时复制的方式，可以高效的进行并发读，但是对于写操作，每次都要进行加锁以及拷贝副本，效率非常低，所以 CopyOnWriteArrayList 仅适合读多写少的场景。

Vector虽然是线程安全的，但是只是一种相对的线程安全而不是绝对的线程安全，它只能够保证增、删、改、查的单个操作一定是原子的，不会被打断，但是如果组合起来用，并不能保证线程安全性。

CopyOnWriteArrayList在并发下不会产生任何的线程安全问题，也就是绝对的线程安全

另外，有两点必须讲一下。

我认为CopyOnWriteArrayList这个并发组件，其实反映的是两个十分重要的分布式理念：

（1）读写分离

我们读取CopyOnWriteArrayList的时候读取的是CopyOnWriteArrayList中的Object[] array，但是修改的时候，操作的是一个新的Object[] array，读和写操作的不是同一个对象，这就是读写分离。这种技术数据库用的非常多，在高并发下为了缓解数据库的压力，即使做了缓存也要对数据库做读写分离，读的时候使用读库，写的时候使用写库，然后读库、写库之间进行一定的同步，这样就避免同一个库上读、写的IO操作太多

（2）最终一致

对CopyOnWriteArrayList来说，线程1读取集合里面的数据，未必是最新的数据。因为线程2、线程3、线程4四个线程都修改了CopyOnWriteArrayList里面的数据，但是线程1拿到的还是最老的那个Object[] array，新添加进去的数据并没有，所以线程1读取的内容未必准确。不过这些数据虽然对于线程1是不一致的，但是对于之后的线程一定是一致的，它们拿到的Object[] array一定是三个线程都操作完毕之后的Object array[]，这就是最终一致。最终一致对于分布式系统也非常重要，它通过容忍一定时间的数据不一致，提升整个分布式系统的可用性与分区容错性。当然，最终一致并不是任何场景都适用的，像火车站售票这种系统用户对于数据的实时性要求非常非常高，就必须做成强一致性的。

最后总结一点，随着CopyOnWriteArrayList中元素的增加，CopyOnWriteArrayList的修改代价将越来越昂贵，因此，CopyOnWriteArrayList适用于读操作远多于修改操作的并发场景中。

感谢

http://www.cnblogs.com/xrq730/p/5020760.html

http://blog.csdn.net/u013124587/article/details/52863533

https://www.cnblogs.com/leesf456/p/5547853.html