前面的文章解析了ArrayList常见的面试点，但是有一个点没有提及就是并发安全的问题。面试中也有可能会问到ArrayList为什么线程不安全，有没有线程安全的解决方案，那么这篇文章就来看看线程安全的ArrayList版本。
Vector
Vector也继承自AbstractList，数据结构和ArrayList很相似，但是它相对于ArrayList是一个线程安全的集合。但是，我们平时开发却很少看到Vector，我们来看看他的线程安全怎么控制的：
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
我们可以看到，Vector堆线程安全的控制很简单粗暴，就是加了一把synchronized锁，即便是读操作也加了一把锁。虽然线程是安全了，但是这效率可想而知，所以我们一般开发过程中很少看到用Vector的场景地方。
Collections.synchronizedCollection(Collection<T> c)
Collections工具类里有很多关于集合的工具方法，其中就有synchronizedCollection(Collection<T> c)的方法。此方法的作用就是构造一个线程安全的集合，例如传入一个ArrayList，将返回一个线程安全的ArrayList->SynchronizedList，
在这里插入图片描述
在这里插入图片描述
我们可以看到，其实它和Voctor类似，都是在方法里上了一把synchronized锁，所以在并发环境下效率并不是很高。
那么JDK有没有给我们提供一个效率相对较高而且是线程安全的List呢？答案是有的，我们就一起来看看这个叫做写时复制版的List,它就是CopyOnWriteArrayList。
CopyOnWriteArrayList
在这里插入图片描述
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 8673264195747942595L;
// 每个CopyOnWriteArrayList对象都持有一把显式锁
final transient ReentrantLock lock = new ReentrantLock();
// 实际存储数据的对象数组,volatile保证了多线程下数据可见性
private transient volatile Object[] array;
final Object[] getArray() {
return array;
}
final void setArray(Object[] a) {
array = a;
}
// 无参构造,默认长度为0的数组
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
顾名思义，CopyOnWrite写时复制就是在写数据的时候将元数据复制一份出来做改动，写完以后将新数据替换。这样的思路是可以达到线程安全的效果，而读操作没有限制，所以在效率上相对于全局上锁要高。我们可以看到，CopyOnWriteArrayList的类定义和ArrayList相差不大，值得注意的是它和ArrayList在数组的初始化和扩容机制有很大差别，我们来看看具体的方法源码吧：
构造
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
public CopyOnWriteArrayList(E[] toCopyIn) {
// 将传入的数组复制一份,然后将array引用指向新数组
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
可以看到它和ArrayList有点不同，它的构造相对简单，如果是无参构造就将创造一个length为0的空数组，如果是传入数组构造就复制一份数组，然后指向它的array属性，其中array属性就是CopyOnWriteArrayList存储数据的数组，和ArrayList里的element数组功能一样。
添加元素 add(E e)
// 添加元素
public boolean add(E e) {
// 获取当前对象所持有的显式锁
final ReentrantLock lock = this.lock;
// 上锁
lock.lock();
try {
// 获取存储数据的数组对象
Object[] elements = getArray();
// 获取数组长度/size(在CopyOnWriteArrayList中,size和数组的length是相等的)
int len = elements.length;
// 复制一份新的数组,新数组的长度是原数组长度+1，他的扩容并不是和ArrayList一样
Object[] newElements = Arrays.copyOf(elements, len + 1);
// 将新数组的最后一位放入元素
newElements[len] = e;
// 将array数组替换为新数组，完成添加
setArray(newElements);
return true;
} finally {
// 释放锁
lock.unlock();
}
}
从add方法就可以看出它和Voctor全局上锁的方式不一样,它使用的是Lock显示锁。lock的好处是可以更加灵活的空值锁的粒度。
也可以看出，CopyOnWriteArrayList对写操作的设计思想就是在写入的时候进行原数组的复制，在复制出的新数组里面进行写入，最后 将复制出来的这个数组引用置回CopyOnWriteArrayList的array属性。
指定位置添加元素 add(int i ,E e)
// 在指定位置插入元素
public void add(int index, E element) {
final ReentrantLock lock = this.lock;
// 上锁
lock.lock();
try {
// 获取原来的数组对象
Object[] elements = getArray();
// 获取原来的数组长度
int len = elements.length;
// 检查插入的位置是否越界
if (index > len || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+len);
// 声明一个新数组
Object[] newElements;
// 偏移量=老数组长度-index
int numMoved = len - index;
// 如果numMoved==0,说明是要在数组尾部添加元素，那么直接复制一份老数组到新数组中，长度+1
if (numMoved == 0)
newElements = Arrays.copyOf(elements, len + 1);
else {
// 否则，在老数组的内部进行插入，此时就要有两轮复制操作，一轮从0复制到index，第二轮从index复制到新数组末尾
newElements = new Object[len + 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index, newElements, index + 1,
numMoved);
}
// 将元素加入到index位置
newElements[index] = element;
// 将array数组对象引用修改为新数组
setArray(newElements);
} finally {
lock.unlock();
}
}
看到这里有个疑问，在ArrayList里的添加里会去计算数组的容量是否达到阈值然后进行1.5倍的扩容。但是CopyOnWriteArrayList却并没有进行1.5倍的扩容，它仅仅是new了一个新数组，然后新数组长度是老数组长度+1，也就是说数组长度length和集合的size一样大，没有留有余地：
newElements = new Object[len + 1];
为什么CopyOnWriteArrayList的扩容没有成倍或半被扩容呢？
这和CopyOnWriteArrayList设计的目的息息相关，CopyOnWriteArrayList设计的目的就是适合读多写少的业务场景保证线程安全，如果预留太多空闲位置，那么在并发环境需要频繁的数组复制，带来的消耗更大。
替换元素 set(int index ,E e)
// 替换指定位置上的元素
public E set(int index, E element) {
final ReentrantLock lock = this.lock;
// 上锁
lock.lock();
try {
// 获取老数组
Object[] elements = getArray();
// 获取老数组上index位置的元素
E oldValue = get(elements, index);
// 如果新替换的元素和index上的元素是同一个对象，那么久不做处理，返回老数组即可
// 如果这俩元素不是同一个对象,就替换
if (oldValue != element) {
// 获取老数组的长度以便复制
int len = elements.length;
// 复制一个和老数组一样长的新数组
Object[] newElements = Arrays.copyOf(elements, len);
// 然后替换掉新数组中index位置的元素
newElements[index] = element;
// 指向array数组对象，完事儿
setArray(newElements);
} else {
// Not quite a no-op; ensures volatile write semantics
setArray(elements);
}
return oldValue;
} finally {
// 释放锁
lock.unlock();
}
}
移除指定位置元素 remove(int index)
// 移除指定位置上的元素
public E remove(int index) {
final ReentrantLock lock = this.lock;
// 上锁
lock.lock();
try {
// 获取原数组
Object[] elements = getArray();
// 获取原数组长度
int len = elements.length;
// 获取出原数组中index位置的元素
E oldValue = get(elements, index);
//是否移除的是数组尾部
int numMoved = len - index - 1;
if (numMoved == 0)
// 如果是数组尾部,直接复制一份新数组，长度-1即可
setArray(Arrays.copyOf(elements, len - 1));
else {
// 如果在数组当中，和添加一样，需要两轮复制操作，一部分从0-index，一部分从index-新数组末尾
Object[] newElements = new Object[len - 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
// 引用指向array数组对象，完事儿
setArray(newElements);
}
return oldValue;
} finally {
lock.unlock();
}
}
移除指定元素 remove(object o)
// 删除指定元素
public boolean remove(Object o) {
// 首先获取集合的数组
Object[] snapshot = getArray();
// 计算出元素所在的数组下标位置
int index = indexOf(o, snapshot, 0, snapshot.length);
// 调用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;
// 如果此时数组和我们传入的数组不相等，说明此时有另外线程修改了数组，此时就需要重新搜索元素所在的下标
if (snapshot != current) findIndex: {
// 如果另一个线程将数组的长度修改了，那么需要重新查找元素
int prefix = Math.min(index, len);
for (int i = 0; i < prefix; i++) {
if (current[i] != snapshot[i] && eq(o, current[i])) {
index = i;
break findIndex;
}
}
// 如果事先要找的元素下标超过了目前数组长度，则返回false
if (index >= len)
return false;
// 如果根据计算出来的index查到元素就返回
if (current[index] == o)
break findIndex;
// 查询不到元素则返回false
index = indexOf(o, current, index, len);
if (index < 0)
return false;
}
// 和remove(int i)方法一样，两轮复制将新数组替换老数组
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();
}
}
这个通用的remove()方法比较复杂，需要传入此位置对象和此位置的index，因为存在并发问题，所以在remove方法里会二次判断数组是否被修改。
清空集合 clear()
// 清空集合
public void clear() {
final ReentrantLock lock = this.lock;
// 上锁
lock.lock();
try {
// 直接将array数组对象置为一个length=0的新数组
setArray(new Object[0]);
} finally {
lock.unlock();
}
}
清空集合十分的简单粗暴，直接将array属性指向一个新的空数组。
总而言之，对CopyOnWriteArrayList的写操作都会上锁，然后复制新数组。那么我们来看看读操作：
获取指定位置的元素 get(int index)
// 获取指定位置上的元素
public E get(int index) {
return get(getArray(), index);
}
private E get(Object[] a, int index) {
return (E) a[index];
}
读取操作并没有上锁，所以相对于前面两种线程安全集合，CopyOnWriteArrayList读的效率相当高。
获取元素第一次出现的index indexOf(object o)
public int indexOf(Object o) {
Object[] elements = getArray();
return indexOf(o, elements, 0, elements.length);
}
// 获取元素在数组中第一次出现的索引
private static int indexOf(Object o, Object[] elements,
int index, int fence) {
// 如果传入的元素时null，那么就便利数组，找出null
if (o == null) {
for (int i = index; i < fence; i++)
if (elements[i] == null)
return i;
} else {
// 如果不是null，就遍历数组一次比较equals
for (int i = index; i < fence; i++)
if (o.equals(elements[i]))
return i;
}
// 否则返回-1
return -1;
}
总结一下CopyOnWriteArrayList和ArrayList的区别吧：
ArrayList：
- 线程不安全，读取效率最高
- 支持指定容量构造
- 扩容是1.5倍增量
CopyOnWriteArrayList：
- 线程安全，读取效率也高
- 不支持指定容量构造
- 没有扩容概念，或者说扩容就是length+1
- 数组的length和集合的size相等
- 数据处理逻辑更复杂，数组的复制操作更频繁易导致GC，适合读多写少业务
- 读写分离模式追求数据最终一致性
