CopyOnWriteArrayList
CopyOnWriteArrayList 源码分析
写时复制(Copy-On-Write)的线程安全 List:读完全无锁,写加锁后把整个底层数组复制一份、改新数组、再用 volatile 写把引用换过去。老数组从不被修改,所以读线程手里的快照永远安全。代价是每次写 O(n) 拷贝,只适合读多写极少的场景(监听器列表、白名单、配置项)。
// 基于 JDK 25 (本地 D:/1ForCode/JAVA_Source), java.util.concurrent.CopyOnWriteArrayList
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final Object[] EMPTY_ELEMENTDATA = {};
final transient Object lock = new Object(); // 写锁。JDK 源码注释：能用内置监视器就不用 ReentrantLock(早期版本确实是 ReentrantLock)
private transient volatile Object[] array; // volatile 是整个类的命门：写线程换引用后读线程立即可见
final Object[] getArray() {
return array;
}
final void setArray(Object[] a) { // 唯一的写入口，一次 volatile 写 = 一次"发布"
array = a;
}
// ...
public E get(int index) { // 读路径全部就这一行：无锁、无 CAS、无阻塞
return elementAt(getArray(), index);
}
// ...
public E set(int index, E element) {
synchronized (lock) {
Object[] es = getArray();
E oldValue = elementAt(es, index);
if (oldValue != element) { // 注意是 == 引用比较，不是 equals
es = es.clone();
es[index] = element;
}
// Ensure volatile write semantics even when oldvalue == element
setArray(es); // 值没变也要做 volatile 写，维持 set() 的 happens-before 承诺
return oldValue;
}
}
public boolean add(E e) {
synchronized (lock) { // 写写互斥；读不参与这把锁
Object[] es = getArray();
int len = es.length;
es = Arrays.copyOf(es, len + 1); // O(n) 全量拷贝，COW 代价的来源
es[len] = e;
setArray(es); // 新数组填好后才发布，读线程看到的要么全旧要么全新
return true;
}
}
}// 基于 JDK 25 (本地 D:/1ForCode/JAVA_Source), java.util.concurrent.CopyOnWriteArrayList
public E remove(int index) {
synchronized (lock) {
Object[] es = getArray();
int len = es.length;
E oldValue = elementAt(es, index);
int numMoved = len - index - 1;
Object[] newElements;
if (numMoved == 0) // 删尾巴：一次 copyOf 就够(len==1 删成空表也走这里)
newElements = Arrays.copyOf(es, len - 1);
else if (len == 1)
newElements = EMPTY_ELEMENTDATA; // 想复用共享空数组，但 index 合法时 len==1 必有 numMoved==0，实际到不了这个分支
else {
newElements = new Object[len - 1]; // 删中间：两段 arraycopy 跳过被删位
System.arraycopy(es, 0, newElements, 0, index);
System.arraycopy(es, index + 1, newElements, index,
numMoved);
}
setArray(newElements);
return oldValue;
}
}
// ...
public boolean addIfAbsent(E e) {
Object[] snapshot = getArray(); // 先无锁查一遍：元素已存在就根本不进锁
return indexOfRange(e, snapshot, 0, snapshot.length) < 0
&& addIfAbsent(e, snapshot);
}
private boolean addIfAbsent(E e, Object[] snapshot) {
synchronized (lock) {
Object[] current = getArray();
int len = current.length;
if (snapshot != current) { // 锁外检查到进锁之间数组被换过 → 必须重查
// Optimize for lost race to another addXXX operation
int common = Math.min(snapshot.length, len);
for (int i = 0; i < common; i++) // 只精查"和快照不一样"的位置，快照里已确认没有 e
if (current[i] != snapshot[i]
&& Objects.equals(e, current[i]))
return false;
if (indexOfRange(e, current, common, len) >= 0)
return false;
}
Object[] newElements = Arrays.copyOf(current, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
}
}// 基于 JDK 25 (本地 D:/1ForCode/JAVA_Source), java.util.concurrent.CopyOnWriteArrayList
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0); // 把"创建这一刻"的数组引用交给迭代器
}
// ... listIterator()/spliterator() 同理，都只是把当刻快照塞给各自实现
static final class COWIterator<E> implements ListIterator<E> {
/** Snapshot of the array */
private final Object[] snapshot; // final 快照：之后 list 怎么写都换不掉它
/** Index of element to be returned by subsequent call to next. */
private int cursor;
COWIterator(Object[] es, int initialCursor) {
cursor = initialCursor;
snapshot = es;
}
public boolean hasNext() {
return cursor < snapshot.length; // 只看快照长度，永远不会 ConcurrentModificationException
}
@SuppressWarnings("unchecked")
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}
// ...
public void remove() {
throw new UnsupportedOperationException(); // 快照是"过去"，在过去上删改没有意义，索性禁止
}
// ... set(E)/add(E) 同样一律抛 UnsupportedOperationException
}原理串讲
一次 add(e) 的完整链路:进 synchronized (lock) 拿到写锁,getArray() 读出当前数组,Arrays.copyOf 复制出长度 +1 的新数组并在尾部放入 e,最后 setArray(es) 一次 volatile 写把 array 引用指向新数组。
全程老数组一个字节都没动。与此同时另一个线程调 get(index),它只执行 elementAt(getArray(), index):getArray() 这次 volatile 读要么拿到旧数组要么拿到新数组,两者都是完整一致的,绝不会读到”改了一半”的状态。
这就是 COW 的原子性来源——用”换引用”这个天然原子的动作替代”改内容”这个非原子的动作。
为什么读可以完全不加锁?因为读写根本不共享可变状态:写线程改的是自己的私有副本,唯一的交汇点是 array 这个引用,而 volatile 保证了两件事——写线程 setArray 之前对新数组的所有填充操作 happens-before 读线程的 getArray()(可见性),以及引用赋值不会与数组填充重排(有序性)。
没有 volatile,读线程可能拿到新引用却看到未初始化的数组内容。
为什么 set() 在 oldValue <mark> element 时也要执行 setArray(es)(把原数组原样写回)?源码注释写得很直白:Ensure volatile write semantics even when oldvalue </mark> element。
set() 对外承诺自己是一次 volatile 写,外部代码可能依赖它建立 happens-before 边(比如线程 A 先写普通变量再 list.set(...),线程 B list.get(...) 后读那个普通变量)。
如果值相同就跳过写,这条内存语义链就断了——正确性不能依赖”值恰好变没变”。
addIfAbsent 展示了另一层优化:先在锁外用当前快照查一遍,元素已存在就直接返回,完全不碰锁;进锁后若发现数组已被别的写线程换过(snapshot != current),也不是傻傻地全表重查——快照里已确认没有 e,所以只需精查 current 与 snapshot 不同的那些位置。这是”乐观检查 + 锁内校验”的经典写法。
迭代器的弱一致性是同一机制的自然推论:iterator() 把当刻数组引用存进 COWIterator.snapshot(final),之后所有写都发布到新数组,快照永远指向旧的。
遍历期间任凭别人增删,hasNext/next 只面对一个不可变数组,所以永不抛 ConcurrentModificationException;代价是看不到遍历开始后的任何更新,且 remove/set/add 直接抛 UnsupportedOperationException——快照上的修改无法反映回真实列表,与其给出错误语义不如禁止。
设计取舍
- 读零开销 vs 写 O(n):每次写全量拷贝,写的瞬间内存里同时存在两份数组。大列表 + 频繁写会制造大量朝生夕死的大对象,GC 压力显著,这种场景该换 ConcurrentHashMap 或加锁的普通 List。
- 快照迭代(fail-safe) vs ArrayList 的 fail-fast:COW 用”读旧数据”换”永不 CME”,适合遍历远多于修改的监听器广播场景。
- 只保证最终一致:
get/iterator读到的可能是落后于最新写的旧值,size()和随后的get之间也没有原子性。需要强一致读的场景不适用。 - 复合操作要靠专门方法:先
contains再add在并发下会重复添加,源码为此提供了锁内原子的addIfAbsent/addAllAbsent。 - 写锁用
synchronized (lock)而非 ReentrantLock:写路径本就是低频短临界区,用不上可中断/超时/公平这些高级能力,内置监视器更省(现代 JVM 对 synchronized 的优化也已足够好)。