1、初探CopyOnWriteArrayList
第一眼看到这个类的时候,英文好的可能已经发现了,这个类翻译过来:使用写时复制策略的ArrayList。这个类出现其实是为了解决并发情况下,ArrayList线程不安全的问题。也可以这么说,CopyOnWriteArrayList是一个线程安全的ArrayList,因为他和ArrayList存储原理差不多,且都实现了List接口。他的基本原理也很简单,对CopyOnWriteArrayList进行的修改操作,是在底层的一个复制的数组上进行的。我们来看看CopyOnWriteArrayList的类图,让我们更加深入了解吧。
从这个类图我们可以看出,CopyOnWriteArrayList内部维护了两个变量,一个是lock,是ReentrantLock独占锁的对象,这个lock是用来保证同时只有一个线程操作我们的array数组。这里我们只关注他是一个独占锁就可以了。另一个是array,它是一个Object数组,用来存放具体的数组的,且用了volatile修饰,保证了这个数组内存可见性。
那如果让我们自己做一个写时复制的线程安全的ArrayList,那么该怎样做呢?我们要考虑写什么呢?
- 什么时候初始化array,初始化array元素个数是多少,array是有限大小的吗?
- 如何保证线程安全,比如多个线程进行读写的时候如何保证保证线程安全?
- 如何保证使用迭代器时,数据的一致性
下面我们来看看,他的源码是如何写的吧
2、CopyOnWriteArrayList源码探究
2.1初始化
探究源码的第一步,也是较为简单的一步,就是看看这个类如何初始化的。简而言之就是直接看他的构造器。代码如下,我自己做了很多注释,应该能够一下子就看懂的:
//无参构造器其实就是设置array的值
//给array一个长度为0的Object数组
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
//传入的是一个集合
public CopyOnWriteArrayList(Collection<? extends E> c) {
Object[] elements;
//如果传入的这个集合是CopyOnWriteArrayList类型的
if (c.getClass() == CopyOnWriteArrayList.class)
//直接使用本类的getArray方法,转化成为数组
//传入elements
elements = ((CopyOnWriteArrayList<?>)c).getArray();
else {
//直接使用集合的toArray方法
elements = c.toArray();
// c.toArray might (incorrectly) not return Object[]
// 集合的toArray方法返回的可能不是Object数组,所以这里要转换一下
if (elements.getClass() != Object[].class)
elements = Arrays.copyOf(elements, elements.length, Object[].class);
}
//将转换好的数组,传入array
setArray(elements);
}
//传入一个数组,而我们要做的就是把这个数组复制一遍
//然后副本传入array
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
其实上面的构造器,都是为了将传入的内容变成Object数组,然后设置到array里面。
2.2添加元素
要想知道他是怎么添加元素的,我们先来看看他有哪些方法可以添加元素。
public boolean add(E e) ;
public void add(int index, E element) ;
public boolean addIfAbsent(E e) ;
private boolean addIfAbsent(E e, Object[] snapshot) ;
public int addAllAbsent(Collection<? extends E> c) ;
看上去好像有很多可以添加元素的方法,但其实它的原理大同小异,这里我着重讲解一下第一个方法,add(E e)。知道了这个方法,其他的方法就会一通百通。好了,我们来看一下他的源码(注释应该很到位了):
public boolean add(E e) {
//首先获取独占锁,保证只有一个线程执行接下来的代码
final ReentrantLock lock = this.lock;
//加锁
lock.lock();
try {
//获取当前的array,
Object[] elements = getArray();
int len = elements.length;
//复制原来的数组到新的数组,并且新数组的长度比原来的大1
Object[] newElements = Arrays.copyOf(elements, len + 1);
//把要添加的元素,加入到新数组的末尾
newElements[len] = e;
//然后把新的数组设置到array里面
setArray(newElements);
return true;
} finally {
//释放锁
lock.unlock();
}
}
其实上面讲述的方法,就把array数组拷贝下来,然后扩容之后,把新的元素赋值给新数组的最后一个元素,然后把新数组设置到array。这整个过程还要保证只有一个线程执行。所以使用了独占锁ReentrantLock。
2.3获取指定位置元素
这里获取指定的元素方法,代码相对比较简单,但是会有一个问题。那么我们下面看看源码吧
private E get(Object[] a, int index) {
return (E) a[index];
}
final Object[] getArray() {
return array;
}
public E get(int index) {
return get(getArray(), index);
}
上面的代码可以说是非常简单了,但是会有问题。假如一个线程调用get方法获得元素的时候,这里就会有两个步骤,第一步首先获得array数组,第二步获得通过下标访问数组。就是这两步操作,但是在整个过程中没有相应的加锁同步。大家应该都想到了吧,当第一步执行完了以后,另外一个线程如果修改了这个数据,又或者直接删除了呢?那么当前执行的线程拿到的可能就是脏数据,而且是根本不期望的数据。这其实就是写时复制策略产生的弱一致性问题。
2.4修改指定元素
这里修改使用的是set方法,输入元素下标和元素的值,就可以修改。如果输入的下标不存在,就会产生一个IndexOutOfBoundsException异常。
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) {
//设置新的值,代替老的值
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
setArray(elements);
}
//返回老的值
return oldValue;
} finally {
//释放锁
lock.unlock();
}
}
这里着重说一下,为什么新的值和老的值相等的时候,还是要设置一下array数组。这里跟volatile的内存意义有关了,详情可以去看一下我的第七篇博客。
2.5删除元素
话不多说,删除元素也有很多方法,原理都一样,这里介绍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 {
Object[] newElements = new Object[len - 1];
//这里分了两次复制
//第一次复制下标为0后的index个元素到新数组
System.arraycopy(elements, 0, newElements, 0, index);
//第二次复制下标为index后numMoved个元素到新数组
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
//然后设置新的array
setArray(newElements);
}
//返回老的值
return oldValue;
} finally {
//释放锁
lock.unlock();
}
}
如上代码其实和新增元素的代码类似,首先获取独占锁以保证删除数据期间其他线程不能对array做修改,然后复制元素到新的数组,返回老的值,最后释放锁。
2.6使用迭代器(弱一致性)
在讲述迭代器的弱一致性之前,我们先来看看这个迭代器如何使用。我们先来举个例子,看看这个迭代器如何使用:
public class COWListDemo {
public static void main(String[] args) {
//创建CopyOnWriteArrayList对象
CopyOnWriteArrayList<String> arrayList = new CopyOnWriteArrayList<>();
//添加元素
arrayList.add("张三");
arrayList.add("李四");
//通过CopyOnWriteArrayList对象,获得迭代器
Iterator<String> itr = arrayList.iterator();
//判断迭代器有没有下一个元素
while(itr.hasNext()){
//输出下一个元素
//并且迭代器里面的指针会指向下一个元素
System.out.println(itr.next());
}
}
}
上面这个例子简单的使用了一下迭代器,下面我们来说一下什么叫迭代器的弱一致性。弱一致性:当我们获得了这个list的迭代器后,其他线程对list进行修改,是不会影响的。也就是说我们获得了的迭代器,其实是那一瞬间的迭代器,不会它里面的元素是不会因为其他线程的修改而改变。
我们来看看源码就知道了:
public Iterator<E> iterator() {
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;
}
public boolean hasNext() {
return cursor < snapshot.length;
}
public boolean hasPrevious() {
return cursor > 0;
}
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}
}
如上代码,当调用iterator()方法获取迭代器,实际上会返回一个COWIterator对象,COWIterator对象其中的snapshot,保存了当前list的内容,cursor是迭代器遍历的下标。这里我们称snapshot其实是array的一个快照。
那么为什么说snapshot其实是array的一个快照呢?很多人没有想明白,明明是把array的引用传递给了snapshot,两个变量其实用的是同一个数组啊,如果其他线程修改了array,那么迭代器里面的内容也会随之改变。但是大家都忘记了一点,就是对array进行增删改查操作时,我们都是用一个新的数组的引用,直接覆盖老的,也就是说,修改了以后,迭代器里面的snapshot仍然引用的上一个array。这也就说明了,使用迭代器元素时,其他线程对改list进行增删改查不可见,因为他们已经操作的是两个数组了,这其实就是弱一致性。
如果你还不明白我这里有一个例子,看完你就会恍然大悟了:
public class COWIList {
//初始化list,且要保证内存可见性
private static volatile CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
public static void main(String[] args) throws InterruptedException {
//添加元素
list.add("one");
list.add("two");
list.add("three");
list.add("five");
list.add("six");
list.add("seven");
Thread threadOne = new Thread(new Runnable() {
@Override
public void run() {
//修改元素
list.set(1,"strange");
//删除元素
list.remove(2);
list.remove(3);
}
});
//先获得迭代器
Iterator<String> it = list.iterator();
//然后启动线程
threadOne.start();
//等待子线程完成
threadOne.join();
//使用迭代器遍历元素
while(it.hasNext()){
System.out.println(it.next());
}
}
}
得到的结果如下:
3、总结
CopyOnWriteArrayList使用写时复制的策略来保证list的一致性,但是获取-修改-写入三步却不是原子性的,所以在增删改的过程中都使用了独占锁,来保证某个时间只有一个线程对其进行修改。另外CopyOnWriteArrayList还提供了弱一致性的迭代器,其他线程的修改对迭代器是不可见的,迭代器内部维护的snapshot,其实是array的快照。
好了,CopyOnWriteArrayList就分析到这里,喜欢的话就给我这个网络乞丐点个赞吧!!