CopyOnWriteArrayList 源码解析
CopyOnWriteArrayList为线程安全的ArrayList,这节分析下CopyOnWriteArrayList的源码,基于JDK1.8。
类结构
CopyOnWriteArrayList类关系图:
CopyOnWriteArrayList实现了List接口的所有方法,主要包含如下两个成员变量:
// 可重入锁,用于对写操作加锁 final transient ReentrantLock lock = new ReentrantLock(); // Object类型数组,存放数据,volatile修饰,目的是一个线程对这个字段的修改另外一个线程立即可见 private transient volatile Object[] array; 复制代码
CopyOnWriteArrayList中并没有和容量有关的属性或者常量,下面通过对一些常用方法的源码解析,就可以知道原因。
方法解析
构造函数
CopyOnWriteArrayList()
空参构造函数:
public CopyOnWriteArrayList() { setArray(new Object[0]); } final void setArray(Object[] a) { array = a; } 复制代码
无参构造函数直接创建了一个长度为0的Object数组。
CopyOnWriteArrayList(Collection<? extends E> c)
:
public CopyOnWriteArrayList(Collection<? extends E> c) { Object[] elements; if (c.getClass() == CopyOnWriteArrayList.class) // 如果集合类型就是CopyOnWriteArrayList,则直接将其array赋值给当前CopyOnWriteArrayList elements = ((CopyOnWriteArrayList<?>)c).getArray(); else { // 如果不是CopyOnWriteArrayList类型,则将集合转换为数组 elements = c.toArray(); // 就如ArrayList源码分析所述那样,c.toArray()返回类型不一定是Object[].class,所以需要转换 if (elements.getClass() != Object[].class) elements = Arrays.copyOf(elements, elements.length, Object[].class); } // 设置array值 setArray(elements); } 复制代码
CopyOnWriteArrayList(E[] toCopyIn)
:
public CopyOnWriteArrayList(E[] toCopyIn) { // 入参为数组,拷贝一份赋值给array setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class)); } 复制代码
add(E e)
add(E e)
往CopyOnWriteArrayList末尾添加元素:
public boolean add(E e) { // 获取可重入锁 final ReentrantLock lock = this.lock; // 上锁,同一时间内只能有一个线程进入 lock.lock(); try { // 获取当前array属性值 Object[] elements = getArray(); // 获取当前array数组长度 int len = elements.length; // 复制一份新数组,新数组长度为当前array数组长度+1 Object[] newElements = Arrays.copyOf(elements, len + 1); // 在新数组末尾添加元素 newElements[len] = e; // 新数组赋值给array属性 setArray(newElements); return true; } finally { // 锁释放 lock.unlock(); } } final Object[] getArray() { return array; } 复制代码
可以看到,add操作通过ReentrantLock来确保线程安全。通过add方法,我们也可以看出CopyOnWriteArrayList修改操作的基本思想为:复制一份新的数组,新数组长度刚好能够容纳下需要添加的元素;在新数组里进行操作;最后将新数组赋值给array属性,替换旧数组。这种思想也称为“写时复制”,所以称为CopyOnWriteArrayList。
此外,我们可以看到CopyOnWriteArrayList中并没有类似于ArrayList的grow方法扩容的操作。
add(int index, E element)
add(int index, E element)
指定下标添加指定元素:
public void add(int index, E element) { // 获取可重入锁 final ReentrantLock lock = this.lock; // 上锁,同一时间内只能有一个线程进入 lock.lock(); try { // 获取当前array属性值 Object[] elements = getArray(); // 获取当前array数组长度 int len = elements.length; // 下标检查 if (index > len || index < 0) throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len); Object[] newElements; int numMoved = len - index; if (numMoved == 0) // numMoved为0,说明是在末尾添加,过程和add(E e)方法一致 newElements = Arrays.copyOf(elements, len + 1); else { // 否则创建一个新数组,数组长度为旧数组长度值+1 newElements = new Object[len + 1]; // 分两次复制,分别将index之前和index+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(); } } 复制代码
set(int index, E element)
set(int index, E element)
设置指定位置的值:
public E set(int index, E element) { // 获取可重入锁 final ReentrantLock lock = this.lock; // 上锁,同一时间内只能有一个线程进入 lock.lock(); try { // 获取当前array属性值 Object[] elements = getArray(); // 获取当前array指定index下标值 E oldValue = get(elements, index); if (oldValue != element) { // 如果新值和旧值不相等 int len = elements.length; // 复制一份新数组,长度和旧数组一致 Object[] newElements = Arrays.copyOf(elements, len); // 修改新数组index下标值 newElements[index] = element; // 新数组赋值给array属性,替换旧数组 setArray(newElements); } else { // 即使新值和旧值一致,为了确保volatile语义,需要重新设置array setArray(elements); } return oldValue; } finally { // 释放锁 lock.unlock(); } } private E get(Object[] a, int index) { return (E) a[index]; } 复制代码
remove(int index)
remove(int index)
删除指定下标元素:
public E remove(int index) { // 获取可重入锁 final ReentrantLock lock = this.lock; // 上锁,同一时间内只能有一个线程进入 try { // 获取当前array属性值 Object[] elements = getArray(); // 获取当前array长度 int len = elements.length; // 获取旧值 E oldValue = get(elements, index); int numMoved = len - index - 1; if (numMoved == 0) // 如果删除的是最后一个元素,则将当前array设置为新数组 // 新数组长度为旧数组长度-1,这样刚好截去了最后一个元素 setArray(Arrays.copyOf(elements, len - 1)); else { // 分段复制,将index前的元素和index+1后的元素复制到新数组 // 新数组长度为旧数组长度-1 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(); } } 复制代码
可以看到,CopyOnWriteArrayList中的增删改操作都是在新数组中进行的,并且通过加锁的方式确保同一时刻只能有一个线程进行操作,操作完后赋值给array属性,替换旧数组,旧数组失去了引用,最终由GC回收。
get(int index)
public E get(int index) { return get(getArray(), index); } final Object[] getArray() { return array; } 复制代码
可以看到,get(int index)
操作是分两步进行的:
通过
getArray()
获取array属性值;获取array数组index下标值。
这个过程并没有加锁,所以在并发环境下可能出现如下情况:
线程1调用
get(int index)
方法获取值,内部通过getArray()
方法获取到了array属性值;线程2调用CopyOnWriteArrayList的增删改方法,内部通过
setArray
方法修改了array属性的值;线程1还是从旧的array数组中取值。
所以get
方法是弱一致性的。
size()
public int size() { return getArray().length; } 复制代码
size()
方法返回当前array属性长度,因为CopyOnWriteArrayList中的array数组每次复制都刚好能够容纳下所有元素,并不像ArrayList那样会预留一定的空间。所以CopyOnWriteArrayList中并没有size属性,元素的个数和数组的长度是相等的。
迭代器
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; } ...... } 复制代码
可以看到,迭代器也是弱一致性的,并没有在锁中进行。如果其他线程没有对CopyOnWriteArrayList进行增删改的操作,那么snapshot还是创建迭代器时获取的array,但是如果其他线程对CopyOnWriteArrayList进行了增删改的操作,旧的数组会被新的数组给替换掉,但是snapshot还是原来旧的数组的引用:
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>(); list.add("hello"); Iterator<String> iterator = list.iterator(); list.add("world"); while (iterator.hasNext()){ System.out.println(iterator.next()); } 复制代码
输出结果仅为hello。
总结
CopyOnWriteArrayList体现了写时复制的思想,增删改操作都是在复制的新数组中进行的;
CopyOnWriteArrayList的取值方法是弱一致性的,无法确保实时取到最新的数据;
CopyOnWriteArrayList的增删改方法通过可重入锁确保线程安全;
CopyOnWriteArrayList线程安全体现在多线程增删改不会抛出
java.util.ConcurrentModificationException
异常,并不能确保数据的强一致性;同一时刻只能有一个线程对CopyOnWriteArrayList进行增删改操作,而读操作没有限制,并且 CopyOnWriteArrayList增删改操作都需要复制一份新数组,增加了内存消耗,所以CopyOnWriteArrayList适合读多写少的情况。
作者:Dynasty
链接:https://juejin.cn/post/7014776505880281119