简介
CopyOnWriteArrayList 是一个线程安全的ArrayList，但是它的每次操作（add ，set，remove等）都是通过复制一个底层的数组副本来实现的，在写操作的时候都会加上锁，有读写分离的意思。
CopyOnWrite
写入时复制（英语：Copy-on-write，简称COW）是一种计算机程序设计领域的优化策略。其核心思想是，如果有多个调用者（callers）同时请求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的。此作法主要的优点是如果调用者没有修改该资源，就不会有副本（private copy）被创建，因此多个调用者只是读取操作时可以共享同一份资源。——维基百科
结构分析
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
CopyOnWriteArrayList实现了List接口，所以具有列表的基础功能；同时实现了RandomAccess接口，所以也支持随机访问（数组随机访问特性）；实现了Cloneable和Serializable接口，支持克隆和序列号。
重要属性
// 锁
final transient ReentrantLock lock = new ReentrantLock();
// 数组
private transient volatile Object[] array;
CopyOnWriteArrayList内部使用的ReentrantLock非公平锁，还有一个volatile修饰的数组，保证了更换数组引用后对其他线程的可见性，并且两个属性都不支持序列化。
内部类：COWIterator
static final class COWIterator<E> implements ListIterator<E> {
/** Snapshot of the array */
private final Object[] snapshot; // array 快照
/** Index of element to be returned by subsequent call to next. */
private int cursor; // 游标，后续调用 next 将返回的元素索引
...
}
COWIterator 表示迭代器，实现了ListIterator接口，内部有一个Object类型的数组作为CopyOnWriteArrayList数组的快照，在创建迭代器的时候记录了当时数组状态的引用。
在迭代器内不支持add、set、remove操作，会抛出UnsupportedOperationException异常。
public void remove() {
throw new UnsupportedOperationException();
}
public void set(E e) {
throw new UnsupportedOperationException();
}
public void add(E e) {
throw new UnsupportedOperationException();
}
方法分析
构造方法
// 初始化默认无参数构造方法
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) {
// 将toCopyIn转化为Object[]类型数组，然后设置当前数组
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
最终调用的都是setArray方法。
final void setArray(Object[] a) {
array = a;
}
构造方法小结：
- 初始化时没有指定数组的初始长度。
- Arrays.copyOf的逻辑就是底层的System.arraycopy数组赋值。
添加元素：add(e)方法
public boolean add(E e) {
final ReentrantLock lock = this.lock;
// 0.加锁
lock.lock();
try {
// 1.拿到数组引用
Object[] elements = getArray();
int len = elements.length;
// 2.copy一个长度+1的数组
Object[] newElements = Arrays.copyOf(elements, len + 1);
// 3.将新增元素加入到数组的最后
newElements[len] = e;
// 4.覆盖旧数组
setArray(newElements);
return true;
} finally {
// 5.解锁
lock.unlock();
}
}
// 获取数组
final Object[] getArray() {
return array;
}
// 覆盖数组
final void setArray(Object[] a) {
array = a;
}
add方法小结：
- 加锁
- 拿到原数组引用
- copy一个长度+1的新数组
- 将新增元素加入到新数组的最后
- 新数组覆盖旧数组
- 释放锁，返回结果
添加元素：add(index, element)方法
指定添加元素的索引
public void add(int index, E element) {
final ReentrantLock lock = this.lock;
// 0.获得锁
lock.lock();
try {
//1.原数组引用
Object[] elements = getArray();
//2.原数组长度
int len = elements.length;
if (index > len || index < 0) // 检测索引是否越界
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+len);
Object[] newElements;
int numMoved = len - index; // 移动的数
if (numMoved == 0)
// 实际上也就是复制一个数组加入到数组的最后
newElements = Arrays.copyOf(elements, len + 1);
else {
// 新数组
newElements = new Object[len + 1];
// index位置分割的两个数组，分段复制
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index, newElements, index + 1,
numMoved);
}
// 指定位置设置成新的元素
newElements[index] = element;
// 覆盖数组
setArray(newElements);
} finally {
lock.unlock();
}
}
add 方法小结：
- 大体逻辑和上面没有指定位置的方法一致
- 指定的中间位置，相当于把原数组切割成了两个数组，需要分别复制到长度+1的新数组
添加元素：addIfAbsent(e)方法
如果添加的元素不存在，才可以添加成功，该方法可避免多线程情况下重复添加元素。
public boolean addIfAbsent(E e) {
Object[] snapshot = getArray();
// indexOf 的功能就是找到元素是否存在，存在则返回其索引，不存在返回-1by:https://jinglingwang.cn
return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
addIfAbsent(e, snapshot);
}
// 不存在则添加
private boolean addIfAbsent(E e, Object[] snapshot) {
final ReentrantLock lock = this.lock;
// 1.加锁
lock.lock();
try {
// 数组引用
Object[] current = getArray();
int len = current.length;
if (snapshot != current) { // 不一致？说明其他线程先行一步更改了数组
// Optimize for lost race to another addXXX operation
// snapshot.length 是旧的数组长度 len是发现变化后的数组长度
int common = Math.min(snapshot.length, len);
for (int i = 0; i < common; i++)
// 判断两个数组的内容是否一致，并检查当前要加入的元素是否已经存在于变化后的数组中
if (current[i] != snapshot[i] && eq(e, current[i]))
// 检查不通过返回false（两个条件都要满足）
return false;
if (indexOf(e, current, common, len) >= 0) // 再检查一次
return false;
}
// 正常的流程，和上面的add一致by:https://jinglingwang.cn
Object[] newElements = Arrays.copyOf(current, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
方法小结：
- 大体逻辑和上面没有指定位置的方法一致
- 多了一个检查环节，如果添加时，数组发生了变化，要检查加入的元素是否已经存在于变化后的数组中（by:https://jinglingwang.cn）
- 数组有变化，也会加入到变化后的新数组中
删除元素：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);
// 索引位置后面的元素个数
int numMoved = len - index - 1;
if (numMoved == 0)
// 是最后一个元素，全部复制到一个长度减一的新数组中
setArray(Arrays.copyOf(elements, len - 1));
else {
// 新的长度减一的数组
Object[] newElements = new Object[len - 1];
// 复制两次，相当于删掉了elements[index]
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements); // 设置新数组的引用
}
return oldValue; // 返回旧值by:https://jinglingwang.cn
} 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;
if (snapshot != current) findIndex: { // 数组有变化会进入到if分支里面
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;
}
}
// 上面for循环没找到，有可能元素在新的数组中还是在那个index位置没变化（current[i] != snapshot[i] 条件不满足）
if (index >= len) // 如果新数组是移除了一个元素，index最多也就等于len,既然新数组移除了元素，上面又没检查出来？直接返回false
return false;
if (current[index] == o) // 元素在新数组的同一个位置，没变化
break findIndex;
index = indexOf(o, current, index, len); // 位置有变化，就重新找到新位置
if (index < 0) // 没找到，已经删掉了，本次删除失败 by:https://jinglingwang.cn
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();
}
}
remove方法小结
- 加锁，找索引，copy删除，覆盖旧数组，解锁返回
- 复杂点的是移除指定元素的时候要检测在删除的过程中，数组是否发生了变化
- 如果有变化，需要重新校验元素是否还存在，并且找到删除元素在新数组中的索引位置，然后删除。
修改值：set方法
修改指定位置的值。
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 {
// Not quite a no-op; ensures volatile write semantics
// 值一样，设置数组
setArray(elements);
}
return oldValue; // 返回旧值
} finally {
lock.unlock(); // 解锁
}
}
set方法小结：
- 加锁
- 找到指定索引的值
- 复制一个长度一样的新数组
- 在新数组中指定位置设置新元素
- 设置为新数组，解锁返回
获取元素：get方法
public E get(int index) {
return get(getArray(), index);
}
private E get(Object[] a, int index) {
return (E) a[index];
}
get方法小结：
- get 没有加锁
- 直接拿到当前数组，获取返回指定位置的值
- 这里有可能
getArray获取到的还是一个旧的数组（比如其他线程调用了add、set、remove方法，但是还没有调用setArray(newElements)方法），所以这里是弱一致性。
迭代器：iterator
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
public ListIterator<E> listIterator() {
return new COWIterator<E>(getArray(), 0);
}
public ListIterator<E> listIterator(int index) {
Object[] elements = getArray();
int len = elements.length;
if (index < 0 || index > len)
throw new IndexOutOfBoundsException("Index: "+index);
return new COWIterator<E>(elements, index);
}
可以以上3个迭代器最终都是通过构造一个COWIterator。
private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor; // 初始迭代的光标
snapshot = elements; // 获取迭代器时，当前数组的快照
}
在获取迭代器时，COWIterator内部保留了当前数组的快照。
迭代遍历的方法：
public boolean hasNext() {
// 判断是否还有下一个元素
return cursor < snapshot.length;
}
public boolean hasPrevious() {
// 判断是否还有上一个元素
return cursor > 0;
}
@SuppressWarnings("[unchecked](http://jinglingwang.cn)")
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++]; // 获取下一个元素
}
@SuppressWarnings("unchecked")
public E previous() {
if (! hasPrevious())
throw new NoSuchElementException();
return (E) snapshot[--cursor]; // 获取上一个元素
}
测试CopyOnWriteArrayList的弱一致性
从上面的get方法分析和迭代器分析中，我们发现他们拿到的数组都有可能是已经过时了的数组，也就是在其他线程调用了add、set、remove方法，但是还没有调用setArray(newElements)方法时，可能就没法获取到最新的数据。
示例：
CopyOnWriteArrayList cowArray = new CopyOnWriteArrayList();
cowArray.add(1);
cowArray.add(2);
cowArray.add(3);
cowArray.add(4);
Iterator it = cowArray.iterator();
while(it.hasNext()){
System.out.print(it.next()+ " ");
}
cowArray.add("jinglingwang.cn");
if(it.hasNext()){
System.out.print(it.next()+ " ");
}
输出结果只会有：1 2 3 4，后面再次迭代时，持有的还是获取迭代器前的数组，因为每次add操作都会产生一个新的数组，而迭代器包含的数组引用是是不包含jinglingwang.cn的，所以迭代器没法遍历出最后新添加的数据，也就是CopyOnWriteArrayList 的弱一致特性。
总结
CopyOnWriteArrayList是一个线程安全的ArrayList，以上是基于jdk1.8的分析。- 每次对数据的修改都会copy一份新的数组（哪怕数组的长度没变化），对内存要求比较高。
CopyOnWriteArrayList是弱一致性，不能保证修改数据后，其他线程马上就能感知。CopyOnWriteArrayList不能限制数组的最长长度，使用需要谨慎。- jdk1.8版本是通过
ReentrantLock锁实现的，jdk11就已经改成了synchronized锁。
