CopyOnWriteArrayList 是一种写时复制的 ArrayList，在写操作时加锁，拷贝原数组成员，在拷贝的数组上进行修改，并重置数组。
该类对于读写可以并发执行，如果写线程还未重置数组，读到的是旧数据；如果已经重置，读到的是新数据。
1 基本属性和方法
写时使用 ReentrantLock 加锁。内部数组 array 存储数据，用 volatile 修饰，保证可见性，可以直接获取相应位置的对象。
getArray 返回数组本身，toArray 返回复制的数组。
//用于写时加锁
final transient ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array;
// getArray是返回数组array本身
final Object[] getArray() {
return array;
}
final void setArray(Object[] a) {
array = a;
}
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
//两个toArray返回的均是复制的数组
public Object[] toArray() {
Object[] elements = getArray();
return Arrays.copyOf(elements, elements.length);
}
public <T> T[] toArray(T a[]) {
Object[] elements = getArray();
int len = elements.length;
if (a.length < len)
return (T[]) Arrays.copyOf(elements, len, a.getClass());
else {
System.arraycopy(elements, 0, a, 0, len);
if (a.length > len)
a[len] = null;
return a;
}
}
2 读
在上节讲到的 array 使用 volatile 修饰，可以在相应索引处直接获取对象。
private E get(Object[] a, int index) {
return (E) a[index];
}
public E get(int index) {
return get(getArray(), index);
}
3 写
这里的写包括添加，删除，修改等操作，其步骤如下：在整个过程中加锁，首先获取原数组的一个拷贝，在拷贝上做一些修改，然后用修改后的数组替代原数组。
由于所有写操作都加了锁，至多允许一个写执行。在写的时候，存在两个数组，一个是数组 array，一个是拷贝的数组。在写的最后setArray未完成时，读线程读到的是旧数组 array。不能保证数据的实时一致性，只能保证最终一致性。
3.1 add
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
//拷贝长度大于elements，在后面多余的是null
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
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;
//注意到增加操作后的数组大小为len+1，有效索引为0-len
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];
//从0开始index个，即elements的0-(index-1)拷贝到newElements
System.arraycopy(elements, 0, newElements, 0, index);
//从index开始numMoved个，即elements的index-(len-1)拷贝到newElements的(index+1)-len
//此时newElements[index]正好空着
System.arraycopy(elements, index, newElements, index + 1,
numMoved);
}
newElements[index] = element;
setArray(newElements);
} finally {
lock.unlock();
}
}
3.2 remove
remove 有三种重载，public 的有两种。直接给索引的删除比较容易，和前面的 add 比较相似；给对象删除的方法，会先查找索引再执行删除，由于未加锁，删除时数组可能已经变化，可能需要再次查找索引。
在if (current[i] != snapshot[i] && eq(o, current[i]))中，如果第一个条件不满足，则第二个条件一定不满足，这是因为在第二个remove方法中先使用 indexOf 方法来获得相应的索引，则snapshot在[0,index-1]之前的项一定不能equals对象o。如果第一个条件不满足，即current[i]==snapshot[i]，那么这些项一定无法equals对象o。
这种写法概括为if(a&&b)，其中 a 不满足，则 b 一定不满足，即 a 是必要，b是充分。其实可以省略 a 写为 if(b)，之所以在 b 前面加上 a 的判断，通常是对 a 的判断较为容易，对 b 的判断较复杂，利用 && 的短路性质尽量能够不去判断 b。
个人感觉第二种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];
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();
//indexOf未加锁
int index = indexOf(o, snapshot, 0, snapshot.length);
//如果索引无效，返回false，否则执行下面的remove
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;
//如果数组已经发生了变化，会判断索引是否失效
//这里findIndex是一个标签
//用于控制下面的代码块，break 会退出所在的代码块
if (snapshot != current) findIndex: {
int prefix = Math.min(index, len);
for (int i = 0; i < prefix; i++) {
//该判断为if(a&&b)，其中a不满足，则b一定不满足。
//写a是利用&&的短路性质，尽量早结束不判断b
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失效，从index向后进行查找
index = indexOf(o, current, index, len);
if (index < 0)
return false;
}//findIndex代码块结束的位置
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 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;
}
3.3 set/clear
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();
}
}
public void clear() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
setArray(new Object[0]);
} finally {
lock.unlock();
}
}
4 迭代器
调用 iterator 方法获取迭代器，将当前数组作为一个快照。在迭代器执行迭代的时候，对该快照数组进行迭代，迭代器只允许遍历，不允许修改。
ArrayList允许迭代器执行修改，在生成迭代器之后的迭代过程中，只能通过迭代器进行修改，如果不通过迭代器修改，迭代器在迭代时因为 modCount != expectedModCount 而抛出异常 ConcurrentModificationException。这称为快速失败。
CopyOnWriteArrayList 不允许迭代器执行修改，在迭代器生成的时候数组就已经确定下来了，迭代的过程中其他的修改都不会影响迭代器。这称为安全失败。
//CopyOnWriteArrayList中获取迭代器的方法，获取当前数组
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
static final class COWIterator<E> implements ListIterator<E> {
/** Snapshot of the array */
private final Object[] snapshot;
/** Index of element to be returned by subsequent call to 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;
}
@SuppressWarnings("unchecked")
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];
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor-1;
}
//不支持
public void remove() {
throw new UnsupportedOperationException();
}
//不支持
public void set(E e) {
throw new UnsupportedOperationException();
}
//不支持
public void add(E e) {
throw new UnsupportedOperationException();
}
@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;
}
}
5 copyOnWriteArraySet
通过copyOnWriteArrayList实现相应操作，为了确保不重复，该类的 add 调用了copyOnWriteArrayList 的 addIfAbsent。
public class CopyOnWriteArraySet<E> extends AbstractSet<E>
implements java.io.Serializable {
private static final long serialVersionUID = 5457747651344034263L;
private final CopyOnWriteArrayList<E> al;
/**
* Creates an empty set.
*/
public CopyOnWriteArraySet() {
al = new CopyOnWriteArrayList<E>();
}
public boolean add(E e) {
return al.addIfAbsent(e);
}
...
}
//copyOnWriteArrayList的方法
public boolean addIfAbsent(E e) {
Object[] snapshot = getArray();
return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
addIfAbsent(e, snapshot);
}
//和remove的逻辑类似，不再详述
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++)
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();
}
}