线程安全的List：CopyOnWriteArrayList
并发包中的并发List只有CopyOnWriteArrayList。CopyOnWriteArrayList是一个线程安全的ArrayList，对于CopyOnWriteArrayList的操作都是在底层的一个复制的数组上进行的。另外，同在并发包中的CopyOnWriteArraySet的底层实现也是CopyOnWriteArrayList。
增
add(E e)
从（1）处可以发现CopyOnWriteArrayList使用ReetrantLock作为线程安全的锁工具，对于add操作，由于独占锁的特性，同一时刻只允许一个线程对array进行修改操作。
（2）处获取数组快照，在add方法，由于独占锁的存在，不会有其它线程对array进行修改操作，所以array就是List准确的底层数组。
（3）处，根据获取到的数组新建一个容量比原数组大一的新数组，并把新增元素放到新数组的最后。
从以上代码可以得到CopyOnWriteArrayList的核心思想正如语义，在写操作的时候，新建一个数组，并把原数组的内容copy到新的数组中。
public boolean add(E e) {
// (1)ReentrantLock默认为非公平锁，
// 作为独占锁同时只允许一个线程对lock()修饰的代码块进行操作
// （在本类中基本是对array的修改操作）
final ReentrantLock lock = this.lock;
lock.lock();
try {
// （2）获取array快照
Object[] elements = getArray();
int len = elements.length;
// （3）拷贝array快照到新建数组，新建数组的大小为原数组的size+1
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
// (4)释放独占锁，可以竞争
lock.unlock();
}
}
// 获取array快照
final Object[] getArray() {
return array;
}
addIfAbsent(E e)
这个方法也是CopyOnWriteArraySet的核心方法。
public boolean addIfAbsent(E e) {
// （0）这里获取的是快照，因为没有加锁，可能有其它线程有写操作
Object[] snapshot = getArray();
return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
addIfAbsent(e, snapshot);
}
private boolean addIfAbsent(E e, Object[] snapshot) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] current = getArray();
int len = current.length;
// （1）检查array是否已经变化，在之前的检查时，有其它线程进行了写操作
if (snapshot != current) {
// Optimize for lost race to another addXXX operation
// （2）取小的那个长度，进行遍历对比。
int common = Math.min(snapshot.length, len);
for (int i = 0; i < common; i++)
// (3) 遍历对应时，当某个位置元素不相等，且 current[i]与
// 当前需要添加的元素相等, 意味着其它线程新增该元素成功。
// 当前线程失败。
if (current[i] != snapshot[i] && eq(e, current[i]))
return false;
// （4）在current中比快照数组长的部分找到目标元素，新增失败
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();
}
}
正如方法语义：缺少时插入，方法先查询待新增元素在当前array中的索引是否大于0，如果大于0证明已经存在该元素，返回false，新增失败。这里要注意的是addIfAbsent()分为两步，首先在addIfAbsent(E e)方法中主要做的是检查该元素是否已存在，如果不存在就调用addIfAbsent(E e, Object[] snapshot)进行真正的新增操作。而传入的snapshot在（0）处获取，由于检查时并没有进行加锁操作，这意味着snapshot正如其名 ，是快照，在当前线程A检查的同时，可能有其它线程B已经进行了新增操作将目标元素新增进List。
下图展示了当在List[1,2,3,4]中新增5时，出现代码标记中（3）（4）情况的可能例子。如果以下两种情况都未发生，那么CopyOnWriteArrayList就要做它的老本行了，新建数组，拷贝元素。
这里需要注意的是拷贝的是current数组而不是snapshot快照数组。出现（3）情况可能又有另一线程C删除了元素4。
遍历对应时，当某个位置元素不相等，且 current[i]与当前需要添加的元素相等,
（4）在current中比快照数组长的部分找到目标元素
删 remove()
remove(int index) 索引删
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();
}
}
看过add的代码，remove(int index) 就代码设计而言没有太大差别，在这边主要区分了两种情况，①删除的元素是中间元素；②删除的元素是结尾元素。
①删除的元素是中间元素
②删除的元素是结尾元素。
获取大小
public int size() {
return getArray().length;
}
在获取size时，仅仅是获取array快照，并获取它的长度。并非加锁操作，所以这个size在并发情况下并不正确，只能在某种程度上反映这个list的大致大小。
弱一致性的迭代器
public ListIterator<E> listIterator() {
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;
}
...
}
可以看到当我们获取CopyOnWriteArrayList的迭代器的时候，无锁获取array，并把array和0作为构造函数入参传给迭代器。显然，这个迭代器同size()方法一样，并不能准确的反应CopyOnWriteArrayList实时的准确情况。
网友评论