一文解读CopyOnWriteArrayList
今天面试了有赞，被怼了（总结还是太菜了），赶紧复习一下。因为面试问到了CopyOnWriteArrayList我就重新看了一下CopyOnWriteArrayList的源码，整理一下思路，写了这篇关于CopyOnWriteArrayList的博客（博客原文地址在这）
ArrayList是常用的Java数据结构，不过在多线程环境下对ArrayList进行并发修改会造成很多意想不到的错误：
- 并发导致数据丢失
- 并发导致插入null
- 并发导致数组越界
所以ArrayList不是线程安全的类，在并发环境下需要使用线程安全的ArrayList进行修改操作，线程安全的ArrayList有这些：Vector和CopyOnWriteArrayList
官方不推荐使用Vector，毕竟它是一个遗留类，而且并发性能很差。这里就来聊一聊CopyOnWriteArrayList这个并发容器，看看它是如何解决并发问题的。
CopyOnWriteArrayList简介
在很多的应用场景中，读操作的可能会远远大于写操作。对于这些场景我们希望是读操作尽可能地快，而写操作慢一些也没有太大的关系。由于读操作根本不会修改原有的数据，因此对于每一次的读取都进行加锁是一种资源的浪费。根据读写锁的思想，读锁与读锁之间不冲突。但是读操作会受到写操作的阻碍，当写操作发生时，读就必须等待。否则可能读到不一致的数据。同时，如果读操作正在进行，程序也不能进行写入。
CopyOnWriteArrayList，从名字上看，在写入操作时，进行一次自我复制。也就是对原有的数据进行一次复制，将修改的内容写入副本中。写完之后，再将修改完的副本替换原来的数据。
CopyOnWriteArrayList的特点：
- 实现了List接口
- 内部持有一个ReentrantLock lock = new ReentrantLock();
- 底层是用volatile transient声明的数组 array
- 读写分离，写时复制出一个新的数组，完成插入、修改或者移除操作后将新数组赋值给array
接下来看一下CopyOnWriteArrayList的源码，理解一下它是如何做到这点的吧
CopyOnWriteArrayList源码解析
概览
public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
//序列号
private static final long serialVersionUID = 8673264195747942595L;
/**
* 可重入锁，对数组增删改时，使用它加锁
*/
final transient ReentrantLock lock = new ReentrantLock();
/**
* 存放元素的数组，其实就是本体
*/
private transient volatile Object[] array;
} 怎么说呢， CopyOnWriteArrayList的成员变量没有比ArrayList多，比较精简，这么设置跟 CopyOnWriteArrayList的特性有关，接下来就可以看出来了
构造方法
/**
* 默认构造方法，构建数组长度为0，
* 没错就是0，接下来会知道为什么这么做
*/
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
/**
* 通过集合类来构造
*/
public CopyOnWriteArrayList(Collection<? extends E> c) {
Object[] elements;
if (c.getClass() == CopyOnWriteArrayList.class)
elements = ((CopyOnWriteArrayList<?>)c).getArray();
else {
elements = c.toArray();
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elements.getClass() != Object[].class)
elements = Arrays.copyOf(elements, elements.length, Object[].class);
}
setArray(elements);
}
/**
* 通过数组来构造
*/
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
} 在上述的构造方法中都使用了setArray()这个方法，不过这个方法只是将array引用指向对应的数组对象罢了，这个方法不是关键。
//设置数组引用指向的数组对象
final void setArray(Object[] a) {
array = a;
} get方法
//这个是真正用于查询的方法
@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
return (E) a[index];
}
/**
* 向外开放的方法
*/
public E get(int index) {
return get(getArray(), index);
}
final Object[] getArray() {
return array;
} 从上面的代码来看，在对CopyOnWriteArrayList读取元素时，根本没有加锁，这极大的避免了加锁带来的开销。
接下来，CopyOnWriteArrayList核心就要来了，看大师如何将CopyOnWriteArrayList打造成线程安全的ArrayList。
add方法
//直接将元素添加到末尾
public boolean add(E e) {
//获取锁
final ReentrantLock lock = this.lock;
//加锁
lock.lock();
try {
//先获取原先的数组
Object[] elements = getArray();
int len = elements.length;
//构建一个新的数组，大小是原数组的大小 1
Object[] newElements = Arrays.copyOf(elements, len 1);
//将元素插入到数组末尾
newElements[len] = e;
//将array引用指向新的数组，原来的数组会被垃圾收集器回收
setArray(newElements);
return true;
} finally {
//释放锁
lock.unlock();
}
}
//在指定位置插入新元素
public void add(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
//判断是否越界
if (index > len || index < 0)
throw new IndexOutOfBoundsException("Index: " index ", Size: " len);
Object[] newElements;
//计算插入位置与数组末尾下标的距离
int numMoved = len - index;
//若为0，则是添加到数组末尾
if (numMoved == 0)
newElements = Arrays.copyOf(elements, len 1);
else {
//不为0，则将原数组分开复制
newElements = new Object[len 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index, newElements, index 1, numMoved);
}
newElements[index] = element;
setArray(newElements);
} finally {
lock.unlock();
}
} 看了add()方法，一切疑问都解释了，我来梳理一下：
- CopyOnWriteArrayList刚创建时，默认的大小为0，当向其插入一个元素时，将原数组复制到一个比原数组大1的新数组中，然后直接将插入的元素放置到新数组末尾，之后修改array引用到新数组就可以，原来的数组就会被垃圾收集器回收。
- 初始化为什么要设置数组大小为0呢，这是因为每次进行添加操作时，都会复制原数组到新的数组中，相当于CopyOnWriteArrayList在进行add操作时，实际占用的空间是原来的两倍，这样的空间开销，导致了CopyOnWriteArrayList不能像ArrayList那样初始化大小为10，不然太浪费空间了，而且CopyOnWriteArrayList主要用于读多写少的地方。因为CopyOnWriteArrayList在进行增删改操作时，都是在新数组上进行，所以此时对CopyOnWriteArrayList进行读取完全不会导致阻塞或是出错。CopyOnWriteArrayList通过将读写分离实现线程安全。
set方法
//修改元素
public E set(int index, E element) {
final ReentrantLock lock = this.lock;
//加锁
lock.lock();
try {
Object[] elements = getArray();
E oldValue = get(elements, index);
//判断原来的元素的值是否等于新值，相等则直接修改array的引用(这么做为了防止remove误删元素，见下面)，
//不相等则复制一份到新数组中再进行修改
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();
}
} set方法也体现了CopyOnWriteArrayList的特点，源码上有注释，这里就不过多解释了。
remove方法
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);
//这里跟add方法很像,判断删除元素的下标与数组末尾下标的距离
//如果为0，则是删除末尾元素，直接将前面的元素复制到新数组中
int numMoved = len - index - 1;
if (numMoved == 0)
setArray(Arrays.copyOf(elements, len - 1));
else {
//若不为0，则创建一个比原来数组小1的新数组，再将要删除元素下标之外的所有元素全部复制到新数组
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();
}
}
//通过元素删除元素
public boolean remove(Object o) {
Object[] snapshot = getArray();
//获取元素下标
int index = indexOf(o, snapshot, 0, snapshot.length);
return (index < 0) ? false : remove(o, snapshot, index);
}
/**
* 删除方法本体
*/
private boolean remove(Object o, Object[] snapshot, int index) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] current = getArray();
int len = current.length;
//若在执行romove操作时，数组已经改变了，则需要对要删除的元素重新定位，防止误删（因为这个删除方法在最初进入时没有加锁，在这个时候可能会发生改变）
if (snapshot != current) findIndex: {
//取最小的遍历范围
int prefix = Math.min(index, len);
for (int i = 0; i < prefix; i ) {
//找到元素对应下标，跳出，重新判断
if (current[i] != snapshot[i] && eq(o, current[i])) {
index = i;
break findIndex;
}
}
//若没有在指定范围中找到对应元素，则进行下一步判断
//元素被删除或不存在
if (index >= len)
return false;
if (current[index] == o)
break findIndex;
index = indexOf(o, current, index, len);
//元素不存在或是被删除
if (index < 0)
return false;
}
//删除
Object[] newElements = new Object[len - 1];
System.arraycopy(current, 0, newElements, 0, index);
System.arraycopy(current, index 1, newElements, index, len - index - 1);
setArray(newElements);
return true;
} finally {
//释放锁
lock.unlock();
}
}
private static boolean eq(Object o1, Object o2) {
return (o1 == null) ? o2 == null : o1.equals(o2);
}
private static int indexOf(Object o, Object[] elements, int index, int fence) {
if (o == null) {
for (int i = index; i < fence; i )
if (elements[i] == null)
return i;
} else {
for (int i = index; i < fence; i )
if (o.equals(elements[i]))
return i;
}
return -1;
} remove也使用也这样的方法来实现读写分离，不过第二个remove方法因为可能会出现在加锁之前发生修改，所以需要重新判断。
总结
从以上的增删改查中我们可以发现，增删改都需要获得锁，并且锁只有一把，而读操作不需要获得锁，支持并发。为什么增删改中都需要创建一个新的数组，操作完成之后再赋给原来的引用？这是为了保证get的时候都能获取到元素，如果在增删改过程直接修改原来的数组，可能会造成执行读操作获取不到数据。
CopyOnWriteArrayList为什么并发安全且性能比Vector好
Vector是增删改查方法都加了synchronized，保证同步，但是每个方法执行的时候都要去获得锁，性能就会大大下降，而CopyOnWriteArrayList 只是在增删改上加锁，但是读不加锁，在读方面的性能就好于Vector，CopyOnWriteArrayList支持读多写少的并发情况。
CopyOnWriteArrayList缺点
- 最大的缺点就是在进行增删改操作时会让CopyOnWriteArrayList占用内存翻倍，如果是对有大量元素的CopyOnWriteArrayList进行增删改，空间消耗是不容忽视的。
- CopyOnWriteArrayList还有一个缺点是数据不具有实时性，即对CopyOnWriteArrayList进行增删改操作，与此同时有其他线程来访问CopyOnWriteArrayList中的元素，因为增删改操作未完成，所以读取元素的线程看不到新数据。如果强调数据的实时性，那么CopyOnWriteArrayList并不是一个好的选择。
查看13道真题和解析
投递华为等公司10个岗位 >