关于实现一个线程安全的List，我们需要考虑的点有：
- 何时初始化List，初始化的时候大小要设置多小，我们的List能不能实现扩容
- 如何保证线程安全，能够良好的在多线程的环境下运作(关键)
- 能不能实现可迭代接口使用迭代器进行遍历呢？数据一致性又要怎么处理
最简单无脑的方式就是学习HashTable的那一套，给所有的方法都加上synchronized不就行了
这样的话直接封锁粒度拉满，当然性能也直接拉闸，一般来说也没有必要这样做
Doug Lea大神就在JUC并发包里写上了一个叫做CopyOnWriteArrayList这种的集合，这个集合的修改操作都是在底层的一个复制的快照上进行的，也就是使用了写时复制策略，接下来我们看看他是怎么设计的
1. 初始化
成员变量相关
final transient ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array;
final Object[] getArray() {
return array;
}
final void setArray(Object[] a) {
array = a;
}可见使用了独占锁ReentrantLock，并且底层数据结构和ArrayList一样使用的Object数组
构造方法
首先看一下无参构造方法
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}很简单的逻辑，就是饿汉式的new了一个长度为0的Object数组
再看一下带参构造
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
public CopyOnWriteArrayList(Collection<? extends E> c) {
Object[] elements;
if (c.getClass() == CopyOnWriteArrayList.class)
elements = ((CopyOnWriteArrayList<?>)c).getArray();
else {
elements = c.toArray();
if (c.getClass() != ArrayList.class)
elements = Arrays.copyOf(elements, elements.length, Object[].class);
}
setArray(elements);
}传入数组则构造一个这个数组的副本，传入集合则同样将集合里面的元素复制到这个List中
2. 主要方法源码
2.1 add方法
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock(); //操作前先加锁
try {
Object[] elements = getArray(); //拿到array
int len = elements.length;
//创建一个新array，大小为原来的+1
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e; //将新的元素插入新array
setArray(newElements); //使用新array代替旧array
return true;
} finally {
lock.unlock(); //释放锁
}
}思路非常的简单，使用了独占锁将整个add操作定义为了一个原子操作来保证安全，并且每添加一个元素就会创建一个新的数组副本，将新元素插入副本中，再用副本替换原来的本体完成添加操作
2.2 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 {
//new了一个大小为原来减1的数组，并且以被删除的位置分两边来进行数组复制操作
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方法类似的逻辑，首先获取独占锁防止删除期间其他线程的修改，然后获取数组中要被删除的元素，并把剩余的元素复制到新的数组，使用新数组代替原来的数组，最后释放锁
2.3 get方法
public E get(int index) {
return get(getArray(), index);
}
private E get(Object[] a, int index) {
return (E) a[index];
}get方法没有加锁，只是单纯的按照索引来获取值，那么这样就会存在一致性问题了，例如下面的例子
假设某时array包含元素 a，b，c
线程A执行get(2)获取2号元素，线程B执行remove(2)删除2号元素，且在B获取锁之前A已经开始执行
则结果就会像下图这样
虽然线程B已经删除了index处的元素，但是线程A还是会返回index处的元素，这也是写复制策略常发生的弱一致性问题
2.4 set方法
使用set方法可以修改list中指定元素的值
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) {
//如果不是一致的，则还是new一个副本，再将元素写入，最后替换旧的
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
// 上面是原文注释，为了保证volatile语义，还是要设置array
setArray(elements);
}
return oldValue;
} finally {
lock.unlock();
}
}3. 迭代器下的情况
CopyOnWriteArraylist实现了迭代器，看一下是怎么定义的
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
static final class COWIterator<E> implements ListIterator<E> {
//拿个快照副本
private final Object[] snapshot;
//数组下标
private int cursor;
//构造函数
private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
snapshot = elements;
}
//判断是否遍历结束
public boolean hasNext() {
return cursor < snapshot.length;
}
//获取元素
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}
}因此当调用iterator()方法时会返回一个COWIterator对象，这个对象的snapshot变量保存了当前list的内容，这样的话每次我们只要获取到迭代器之后，其他线程对原来list的增删改和上面一样都不可见了，这也是弱一致性带来的结果
下面看一个例子
public class TestArrayList {
private static volatile CopyOnWriteArrayList<String> arrayList = new CopyOnWriteArrayList<>();
public static void main(String[] args) throws InterruptedException {
arrayList.add("hello");
arrayList.add("world");
arrayList.add("welcome");
arrayList.add("to");
arrayList.add("ecust");
Thread threadOne = new Thread(new Runnable() {
@Override
public void run() {
arrayList.set(1, "earth");
arrayList.remove(2);
arrayList.remove(3);
}
});
Iterator<String> itr = arrayList.iterator();
threadOne.start();
threadOne.join();
while (itr.hasNext()) {
System.out.println(itr.next());
}
}
}
输出：
hello
world
welcome
to
ecust可见线程对原List对删除和set操作并没有影响到我们使用迭代器读取，是不是有一点MySQL里面可重复读隔离级别的味道呢~？
4. 总结
CopyOnWriteArrayList使用了写时复制的思想来保证list的一致性，并且对于获取、修改、写入这三个操作使用独占锁来保证这三个完整操作的原子性，保证某个时间段只有一个线程才可以修改它。另外它还提供了弱一致性的迭代器，保证获取到迭代器之后，其他线程对list的修改是不可见的
小补充
除了CopyOnWriteArrayList之外，还有一个CopyOnWriteArraySet，我们稍微看一下这是什么
public class CopyOnWriteArraySet<E> extends AbstractSet<E>
implements java.io.Serializable {
private final CopyOnWriteArrayList<E> al;
public CopyOnWriteArraySet() {
al = new CopyOnWriteArrayList<E>();
}
public boolean remove(Object o) {
return al.remove(o);
}
public boolean add(E e) {
return al.addIfAbsent(e);
}
}可以看见它就是基于CopyOnWriteArrayList来实现的，有点HashSet和HashMap之间关系的味道了