当前位置：首页 > news >正文

CopyOnWriteArrayList和CopyOnWriteArraySet ：并发安全的写时复制机制

news 2025/6/10 9:31:48

CopyOnWriteArrayList

对 CopyOnWriteArrayList 结构和其核心算法实现的详细解析，重点突出其有意思的并发和数据一致性实现机制，而对于只是简单加锁的部分会简要带过。

基本结构

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

实现了 List、RandomAccess 等接口，支持序列化和克隆。
泛型容器，元素类型为 E。

内部字段

private transient volatile Object[] array;
final transient Object lock = new Object();

array：底层存储元素的数组，volatile 保证可见性（类似双重检查锁，为什么synchronized 修改还需要volatile？因为赋值和初始化可能会被重排序）。
lock：用于所有变更操作的锁。

主要实现思路

核心思想

写时复制（Copy-On-Write）：每次修改（add/set/remove等）都复制底层数组，读操作无锁直接读取。
非常适合“读多写少”的场景，读操作无需锁定，写操作开销大但线程安全。

关键算法和代码细节

读操作（无锁）

例如 get(int index)：

public E get(int index) {return elementAt(getArray(), index);
}

读取时直接访问 volatile 数组，无需加锁，保证了高效读性能。

迭代器 snapshot 机制

public Iterator<E> iterator() {return new COWIterator<E>(getArray(), 0);
}

迭代器构造时直接拷贝一份当前数组快照，后续遍历不会受到并发修改影响。不会抛出 ConcurrentModificationException。

写操作（加锁+数组复制）

以 add(E e) 为例：

public boolean add(E e) {synchronized (lock) {Object[] es = getArray();int len = es.length;es = Arrays.copyOf(es, len + 1);es[len] = e;setArray(es);return true;}
}

先加锁，拷贝老数组，扩容，插入新元素，然后 setArray 设置新数组。
其它写操作（set、remove、addAll等）都用类似方式：加锁 + 拷贝 + setArray。

addIfAbsent(E e)：避免重复插入

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 operationint common = Math.min(snapshot.length, len);for (int i = 0; i < common; i++)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;}}

先无锁判断再加锁二次确认，减少不必要加锁。

批量操作与 Predicate

removeIf(Predicate)

public boolean removeIf(Predicate<? super E> filter) {Objects.requireNonNull(filter);return bulkRemove(filter);
}
private boolean bulkRemove(Predicate<? super E> filter) {synchronized (lock) {return bulkRemove(filter, 0, getArray().length);}
}
boolean bulkRemove(Predicate<? super E> filter, int i, int end) {// 先遍历定位需删除元素，使用low-level bit操作记录哪些要删除// 然后只拷贝保留的元素，最后setArray// ...省略部分代码...
}

用 long[] deathRow 作为位图，定位要删除的元素，有效避免多次拷贝。
只有真正有元素需要删除时才会生成新数组，减少开销。

子列表（subList）的一致性校验

内部类 COWSubList 持有期望的 array 引用。
每次操作前都检查 expectedArray == getArray()，如果不等则说明底层数组被外部修改，抛出 ConcurrentModificationException，保证子列表操作的一致性和安全性。

reversed() 反转视图（JDK 21+）

返回一个新的视图类 Reversed，所有操作反向映射到原数组，无需新建拷贝。
反转视图的所有操作也都能正确同步到底层 CopyOnWriteArrayList。

总结

CopyOnWriteArrayList 的“写时复制”思想，提高了读多写少场景下的并发效率。
读操作完全无锁，写操作加锁但只锁定自身，且通过拷贝数组避免了读写冲突。
迭代器和 subList 都是快照机制，保证并发安全、无异常。
对于只加锁的部分（如 remove/add），核心逻辑就是加锁+拷贝+setArray，不再赘述。
批量操作和反转视图等则有更多值得品味的算法细节。

CopyOnWriteArraySet

通过内部维护一个 CopyOnWriteArrayList 来实现 Set 的功能。以下是它如何利用 CopyOnWriteArrayList 的一些关键点：

内部存储：CopyOnWriteArraySet 的所有元素都存储在其内部的 CopyOnWriteArrayList 中。这个列表是线程安全的，并且所有写操作都会创建一个新的数组副本。
写操作：
- add(E e)：调用 al.addIfAbsent(e)，确保元素不存在时才添加。
- remove(Object o)：调用 al.remove(o)，从列表中移除元素。
- clear()：调用 al.clear()，清空列表。
读操作：
- iterator()：调用 al.iterator()，返回一个快照迭代器。
- isEmpty()：调用 al.isEmpty()，检查列表是否为空。
- toArray()：调用 al.toArray()，返回列表的数组表示。
- size()：调用 al.size()，返回列表的大小。
其他操作：
- contains(Object o)：调用 al.contains(o)，检查列表是否包含元素。
- forEach(Consumer<? super E> action)：调用 al.forEach(action)，对每个元素执行操作。
- spliterator()：返回一个快照 spliterator，提供列表的元素。