跳到主要内容

前言

我们经常使用ArrayList,他是List的一个实现类,但是他并不是线程安全的,因为在进行扩容的时候,会造成线程安全问题,我们想要使用线程安全的List一般有三种方式:使用Vector类使用Collections.synchronizedList()方法使用CopyOnWriteArrayList类

我们看Vector的源码可以看到,他的很多方法都是加了synchronized关键字,从而达到线程安全的,我们可以把Vector和ArrayList的关系类比成HashMap和HashTable的关系,因为是使用synchronized保证线程安全的,所以他的效率就不是很高,所以CopyOnWriteArrayList应运而生了,今天我们就来学习一下CopyOnWriteArrayList的实现原理以及到底是怎么保证线程安全的。

CopyOnWriteArrayList

CopyOnWriteArrayList是Java并发中使用COW机制的其中一个集合类,还有一个类叫做CopyOnWriteArraySet,本篇文章主要讲解CopyOnWriteArrayList

COW是什么?

Copy-On-Write简称为COW,直译为写时复制。我们用大白话理解,就是我们需要添加元素的时候,我们不直接添加,而是复制一份新的容器,然后向新的容器中添加元素,添加完成后,我们将旧容器的引用指向新容器的地址,其实就是一种读写分离的思想,读和写是不同的容器,一般我们使用COW会用在读多写少的情况下,因为我们读的时候不会给容器加锁,而写的时候会加锁

image.png

我们先看CopyOnWriteArrayList的类图,我们可以看到它分别实现了List、Cloneable、Serializable、RandomAccess接口,所以它支持列表的基本操作、并且可以克隆、也能序列化、同样也支持随机访问

成员属性

    //序列化ID
private static final long serialVersionUID = 8673264195747942595L;
//可重入锁,在添加元素的时候加锁
final transient ReentrantLock lock = new ReentrantLock();
//真实存储元素的数组
private transient volatile Object[] array;
//native方法UNSAFE类
private static final sun.misc.Unsafe UNSAFE;
//加锁偏移量
private static final long lockOffset;

构造函数

    //空参构造
public CopyOnWriteArrayList() {
//创建数组的方法
setArray(new Object[0]);
}
//将集合c的元素添加到容器中
public CopyOnWriteArrayList(Collection<? extends E> c) {
//创建一个引用
Object[] elements;
//判断c的Class是否与当前容器Class相同
if (c.getClass() == CopyOnWriteArrayList.class)
//相同直接给element赋值
elements = ((CopyOnWriteArrayList<?>)c).getArray();
else {
//不相同,将c转换为数组
elements = c.toArray();
if (elements.getClass() != Object[].class)
//给element赋值
elements = Arrays.copyOf(elements, elements.length, Object[].class);
}
//更改容器数组引用
setArray(elements);
}
//将toCopyIn数组中的元素覆盖为容器
public CopyOnWriteArrayList(E[] toCopyIn) {
//更改容器数组引用
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
final void setArray(Object[] a) {
//把容器真正存储元素的数组指向数组a
array = a;
}

添加

    //添加元素e
public boolean add(E e) {
//获取可重入锁
final ReentrantLock lock = this.lock;
//加锁
lock.lock();
try {
//获得容器数组
Object[] elements = getArray();
//拿到容器数组长度
int len = elements.length;
//赋值一份比当前数组长度 + 1的数组
Object[] newElements = Arrays.copyOf(elements, len + 1);
//将数组最后一个位置设置为e
newElements[len] = e;
//修改容器数组引用为新的数组
setArray(newElements);
return true;
} finally {
//释放锁
lock.unlock();
}
}
//将元素element添加到索引为index的位置
public void add(int index, E element) {
//获取可重入锁
final ReentrantLock lock = this.lock;
//加锁
lock.lock();
try {
//获取容器数组
Object[] elements = getArray();
//获取数组长度
int len = elements.length;
//如果index大于数组长度或者小于0那么直接抛出异常
if (index > len || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+len);
//创建一个新的数组引用
Object[] newElements;
//计算需要移动元素的个数
int numMoved = len - index;
if (numMoved == 0)
//如果numMoved等于0,证明要添加到数组尾部,复制一份长度+1的数组
newElements = Arrays.copyOf(elements, len + 1);
else {
//创建一个长度为len + 1的数组
newElements = new Object[len + 1];
//将elements数组中从0开始的复制到newElements数组的0到index位置
System.arraycopy(elements, 0, newElements, 0, index);
//将elements数组中从index开始的复制到newElements数组的index + 1到numMoved位置
System.arraycopy(elements, index, newElements, index + 1,
numMoved);
}
//将newElements数组index位置的元素置为element
newElements[index] = element;
//将容器数组的引用修改为newElements
setArray(newElements);
} finally {
//释放锁
lock.unlock();
}
}

删除

    //删除索引为index的元素
public E remove(int index) {
//获取可重入锁
final ReentrantLock lock = this.lock;
//加锁
lock.lock();
try {
//获得容器数组
Object[] elements = getArray();
//获得容器数组长度
int len = elements.length;
//拿到elements数组索引为index的元素
E oldValue = get(elements, index);
//求得偏移量
int numMoved = len - index - 1;
//如果偏移量为0,证明index为数组最后一个元素
if (numMoved == 0)
//复制一份len - 1长度的数组
setArray(Arrays.copyOf(elements, len - 1));
else {
//创建一个长度为len - 1的数组
Object[] newElements = new Object[len - 1];
//将elements从0开始复制到newElements从0开始到index位置
System.arraycopy(elements, 0, newElements, 0, index);
//将element从index + 1开始复制到newElements从index到numMoved位置
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
//修改容器数组引用为newElements
setArray(newElements);
}
//返回删除的元素
return oldValue;
} finally {
//释放锁
lock.unlock();
}
}
//删除第一次值为o的元素
public boolean remove(Object o) {
//拿到容器数组
Object[] snapshot = getArray();
//找到第一个值为o的元素索引index
int index = indexOf(o, snapshot, 0, snapshot.length);
//如果index < 0 删除失败,否则调用下面那个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;
//如果需要删除数组和当前容器的数组不是一个数组
//这里是Java标签语法,很多人可能没见过,我也没见过
//Java标签语法作用是为了跳出多重嵌套循环能直接跳到标签位置
if (snapshot != current) findIndex: {
int prefix = Math.min(index, len);
for (int i = 0; i < prefix; i++) {
//如果o与current[i]相等,那么直接跳出循环
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 = indexOf(o, current, index, len);
if (index < 0)
return false;
}
//利用数组拷贝覆盖index位置的元素
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();
}
}
//删除一个范围的元素(fromIndex,toIndex)
void removeRange(int fromIndex, int toIndex) {
//拿到可重入锁
final ReentrantLock lock = this.lock;
//加锁
lock.lock();
try {
//获得容器数组
Object[] elements = getArray();
//获得数组长度
int len = elements.length;
//判断范围索引是否越界
if (fromIndex < 0 || toIndex > len || toIndex < fromIndex)
throw new IndexOutOfBoundsException();
//计算新数组的长度
int newlen = len - (toIndex - fromIndex);

int numMoved = len - toIndex;
if (numMoved == 0)
setArray(Arrays.copyOf(elements, newlen));
else {
//通过数组拷贝覆盖元素
Object[] newElements = new Object[newlen];
System.arraycopy(elements, 0, newElements, 0, fromIndex);
System.arraycopy(elements, toIndex, newElements,
fromIndex, numMoved);
//设置容器数组引用
setArray(newElements);
}
} finally {
//释放锁
lock.unlock();
}
}

获取

    //获得索引为index的元素
public E get(int index) {
//调用真正的get方法
return get(getArray(), index);
}
//真正的get方法
private E get(Object[] a, int index) {
//直接返回对应索引的元素
return (E) a[index];
}

小结

CopyOnWriteArrayList的缺陷和使用场景

通过前面我们可以看到CopyOnWriteArrayList进行添加元素以及删除元素的时候,都是通过拷贝数组进行实现的,会消耗大量内存,如果原来的数组内容多,可能会导致性能有所下降,并且也不能用于实时的这种场景,因为我们添加元素需要时间,虽然CopyOnWriteArrayList能做到最终数据一致性,但是没办法满足实时性。

我们前面说过,CopyOnWriteArrayList适合读多写少的场景,但是我们知道他在写的时候是通过复制数组来实现的,所以在大数据量的情况下,也并不可取

虽然CopyOnWriteArrayList有这么多不好,但是相较于Vector他的并发性能还是很好的,Vector为了保证线程安全是通过synchronized关键字来实现的,而CopyOnWriteArrayList只有在写和删除等操作才会加锁,而读的时候是不会进行加锁的