CopyOnWriteArrayList 是 Java 集合框架的一员，同时它也是 Java 并发框架中的一个数据结构。可以把它理解为线程安全版本的 java.util.ArrayList 。
源码分析
继承关系
CopyOnWriteArrayList 继承了四个接口：
-
List：集合框架中的列表接口。 -
Cloneable：复制能力接口。 -
Serializable：序列化接口。 -
RandomAccess：随机访问接口。
前三个接口十分常见，最后的 RandomAccess 接口表示具有 List 的实现具有快速随机访问的特性。该接口的主要目的是允许泛型算法在应用于随机或顺序访问列表时改变其行为，以提供良好的性能。
属性
CopyOnWriteArrayList 中的属性包括：
/** 保护所有变量的锁 */
final transient ReentrantLock lock = new ReentrantLock();
/** 内部的数据结构，只能通过getArray/setArray访问。 */
private transient volatile Object[] array;
final Object[] getArray() {
return array;
}
final void setArray(Object[] a) {
array = a;
}
从属性就可以看出两个重要特性：
-
CopyOnWriteArrayList 中的数据是线程安全的。 -
CopyOnWriteArrayList 的底层数据结构是数组。
构造方法
// 创建一个空列表
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);
}
// copy 给定的数组创建列表
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
构造方法中最后都调用了 setArray() 方法，将数组保存到了属性 array 中。
内部类
CopyOnWriteArrayList 有三个内部类：COWIterator 、COWSubList 、COWSubListIterator 。
COWIterator
static final class COWIterator<E> implements ListIterator<E> {
/** array 快照 */
private final Object[] snapshot;
/** 后续调用next返回的元素的索引。 */
private int cursor;
private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
snapshot = elements;
}
public boolean hasNext() {
return cursor < snapshot.length;
}
public boolean hasPrevious() {
return cursor > 0;
}
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}
public E previous() {
if (! hasPrevious())
throw new NoSuchElementException();
return (E) snapshot[--cursor];
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor-1;
}
...
// 遍历剩余的内容
@Override
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
Object[] elements = snapshot;
final int size = elements.length;
for (int i = cursor; i < size; i++) {
@SuppressWarnings("unchecked") E e = (E) elements[i];
action.accept(e);
}
cursor = size;
}
}
从代码上看，COWIterator 就是一个自定义迭代器，内部使用 snapshot 和 cursor 来保存外部数据结构的快照，并用 cursor 来记录索引位置。
COWSubList
CopyOnWriteArrayList 中代表子列表的类型，内部的操作方法的线程安全也都是通过外部 CopyOnWriteArrayList 的 lock 进行的：
private static class COWSubList<E> extends AbstractList<E> mplements RandomAccess {
private final CopyOnWriteArrayList<E> l;
private final int offset;
private int size;
private Object[] expectedArray;
// 仅在持有 list 锁的情况可以调用
COWSubList(CopyOnWriteArrayList<E> list, int fromIndex, int toIndex) {
l = list;
expectedArray = l.getArray();
offset = fromIndex;
size = toIndex - fromIndex;
}
// 其他操作方法基本都是一个思路，这里只以 set 为例
public E set(int index, E element) {
final ReentrantLock lock = l.lock;
lock.lock();
try {
rangeCheck(index);
checkForComodification();
E x = l.set(index+offset, element);
expectedArray = l.getArray();
return x;
} finally {
lock.unlock();
}
}
...
}
COWSubListIterator
COWSubList 的迭代器：
private static class COWSubListIterator<E> implements ListIterator<E> {
private final ListIterator<E> it;
private final int offset;
private final int size;
COWSubListIterator(List<E> l, int index, int offset, int size) {
this.offset = offset;
this.size = size;
it = l.listIterator(index+offset);
}
// 这些方法的实现和COWIterator一样，只是操作对象换成了 it
public boolean hasNext()
public E next()
public boolean hasPrevious()
public E previous()
public int nextIndex()
public int previousIndex()
// 其他操作方法都不支持，这里以 remove 为例，其他省略
public void remove() {
throw new UnsupportedOperationException();
}
...
@Override
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
int s = size;
ListIterator<E> i = it;
while (nextIndex() < s) {
action.accept(i.next());
}
}
}
核心逻辑
CopyOnWriteArrayList 是一个 ArrayList 的线程安全版本，那么也就需要从两个方面分析，一是数组扩容机制，二是如何保证线程安全。
以 add 方法为例，从上述两个方面分析一下：
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();
}
}
-
线程安全方面，所有涉及数组内容变化的操作都使用了一个 ReentrantLock 来保证，执行方法时，首先加锁，然后再执行操作数组的逻辑，最后解锁。 -
扩容机制是通过新建了一个容量加一的数组，再把原来的内容复制到新数组中，最后一个位置存储新增加的数据，这里扩容逻辑和 ArrayList 是一样的。
CopyOnWriteArrayList 提供了 addIfAbsent 方法组，这个方法与 add 的区别是：如果数组中不存在，则添加；否则，不添加，直接返回，可以保证多线程环境下不会重复添加元素。
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) {
// Optimize for lost race to another addXXX operation
int common = Math.min(snapshot.length, len);
for (int i = 0; i < common; i++)
// 这里的 eq 方法比较两个元素是否相同
if (current[i] != snapshot[i] && eq(e, current[i]))
return false;
if (indexOf(e, current, common, len) >= 0)
return false;
}
Object[] newElements = Arrays.copyOf(current, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
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();
}
}
其他方法基本也都是先加锁，再执行逻辑，最后解锁的思路，这里不再介绍。
总结
CopyOnWriteArrayList 因为需要执行加解锁和复制整个数组的操作，所以在更新列表内容时，操作的实时性不好，所以这个数据结构适合用于读多写少的场景。
最后，ArrayList 有线程安全的版本的 Vector ，Vector 的 add 、remove 等方法都使用了synchronized 关键字来修饰，CopyOnWriteArrayList 使用的是 ReentrantLock ，本质上是 synchronized 关键字和 ReentrantLock 的区别，另一方面，Vector 已标记为弃用，所以这里也推荐使用 CopyOnWriteArrayList 替代 Vector。
原文始发于微信公众号（八千里路山与海）：Java 多线程并发【14】CopyOnWriteArrayList
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由半码博客整理，本文链接：https://www.bmabk.com/index.php/post/85087.html
