1. 为什么需要 CopyOnWriteArrayList
ArrayList 的内部实现是一个数组, 并且是动态扩容的, 当插入数据时, 先判断数组是否需要扩容, 如果需要扩容, 则先扩容, 再插入数据, 也就说插入由三步组成
1) 检查是否需要扩容
2) 扩容/不扩容
3) 数据加入到数组
代码如下
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
这里如果出现并发操作, 会有两个问题
1) 如果同时进行扩容, 则有可能出现连续进行两次扩容的问题, 而实际只需要一次
2) 如果同时对数组进行赋值, 则有可能第一个赋值元素被覆盖, 因为可能两个线程拿到的 size 是一样的, 他们都填到数组的同一个槽里
再看另一个 add 操作
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
这种情况下, add 分为四步
1) 检查是否需要扩容
2) 扩容
3) 移动数据
4) 插入数据
如果此时有并发的读取和插入操作, 则有可能出现读取到的值为 null 的情况, 例如 list.get(3) 跟 list.add(3, "new") 同时发生, 本来 list.get(3) 应该拿到 "old" 或者 "new", 现在却拿到了 null, 这是因为在取值的过程中正好发生了移动数据, 但是数据又还没被插入到移动的空槽里
2. 如何解决这些问题?
一种最简单的方式是对 ArrayList 的所有行为全部加锁, 例如 Collections.synchronizedList(list) 方法, 他会包装 list, 并对所有操作加锁
但是这种方式会 block 所有操作, 读, 写 都是串行的, 会影响效率
3. CopyOnWriteArrayList 如何解决这些问题
cowlist 的写操作全都加锁, 并且在加锁后会将底层数组复制一份再进行写操作, 当写操作完成以后, 整个替换底层数组
1) 使用锁, 即解决了并发写的问题
2) 读操作不加锁, 效率更高, 读写不冲突
3) 写操作使用副本控制, 解决读操作会读到 null 问题, 因为底层数据不会出现有空槽的中间状态