CopyOnWriteArrayList 是 ArrayList 的线程安全版本。用一句话概括它的特点就是:所有的修改操作都是基于副本来进行的。
在 java.util.concurrent
下,有很多线程安全的容器,大致可以分成三类 Concurrent*
、 CopyOnWrite*
、 Blocking*
这三类的容器都可以在并发环境下使用,但是实现的方式却不一样。
Concurrent* 容器是基于无锁技术实现,性能很好,ConcurrentHashMap 就是典型代表;CopyOnWrie* 容器则是基于拷贝来实现的,所以对于内存有很大的开销,CopyOnWriteArrayList 就属于这一类;Blocking* 容器则使用 锁技术实现了阻塞技术,在某些场景下非常有用。
CopyOnWriteArrayList 的核心操作如下,就是通过不断的拷贝数组来更新容器:
CopyOnWriteArrayList 的成员变量如下:
final transient Object lock = new Object(); private transient volatile Object[] array; 复制代码
变量的数量很少,仅仅包含一个锁对象和一个用来放元素数组。因为 CopyOnWriteArrayList 保证线程安全的方式很简单,不断的通过备份元素来保证数据不会被修改。
和其他线程安全的容器思路不一样,这个容器从空间的角度来解决线程安全的问题。所有对容器的修改是基于副本进行的,修改的过程中也通过锁对象锁来保证并发安全,从这个角度来说,CopyOnWriteArrayList 的并发度也不会太高。所以一句话概括就是使用 synchronized + Array.copyOf 来实现线程安全。
迭代器是基于副本进行的,即使原数组被改变,副本也不会被影响。也就不会抛出 ConcurrentModificationException 异常。但是这样也会让最新的修改无法及时体现出来。
get 方法直接读取数组就行,不需要上锁,多个线程同时读也就不会有并发的问题产生。
public E get(int index) { return elementAt(getArray(), index); } static <E> E elementAt(Object[] a, int index) { return (E) a[index]; } 复制代码
下来来看一下 add 方法,代码很短:
// CopyOnWriteArrayList.add() public boolean add(E e) { synchronized (lock) { Object[] es = getArray(); int len = es.length; // 复制原数组,并且长度加一 es = Arrays.copyOf(es, len + 1); es[len] = e; // 指向新的数组 setArray(es); return true; } } 复制代码
也就是是说,每次添加元素的时候,都会把原数组复制一次,并把复制后的数组长度加 1,然后把元素添加进数组,最后用新数组去替代旧数组,完成添加。这样 CopyOnWriteArrayList 根本就不需要扩容,因为每次添加元素都是一个扩容的过程。
// CopyOnWriteArrayList.remove() public E remove(int index) { synchronized (lock) { Object[] es = getArray(); int len = es.length; E oldValue = elementAt(es, index); // 计算需要移动的元素 int numMoved = len - index - 1; Object[] newElements; // 如果删除的是最后一个元素,则不需要移动 if (numMoved == 0) newElements = Arrays.copyOf(es, len - 1); else { newElements = new Object[len - 1]; // 删除的是中间元素,则需要分两次复制 System.arraycopy(es, 0, newElements, 0, index); System.arraycopy(es, index + 1, newElements, index, numMoved); } // 指向新的数组 setArray(newElements); return oldValue; } } 复制代码
删除元素的情况就要复杂一些。删除的时候如果是删除中间的元素,需要后面元素进行移动。然后新数组的长度也会减 1,这就相当于缩容过程。
CopyOnWriteArrayList 的迭代器的实现也很不复杂:
# COWIterator 构造函数 COWIterator(Object[] es, int initialCursor) { cursor = initialCursor; // 容器元素的副本 snapshot = es; } 复制代码
可以看到,构造迭代器的时候,直接把整个元素的副本都传进来了,后续的操作都会在这个副本上进行,甚至都需要上锁。所以是 fail-safe 的。
在 CopyOnWriteArrayList 中,有两种数组拷贝方式 Arrays.copyOf
和 System.arraycopy
。这两种方式有什么区别吗?实际上是没有的,来看一下 Arrays.copyOf 的源码:
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] : (T[]) Array.newInstance(newType.getComponentType(), newLength); System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength)); return copy; } 复制代码
没错,Arrays.copyOf 调用了 System.arraycopy 来实现数组拷贝。
通过上面的分析可知,CopyOnWriteArrayList 的读效率很高,但是写的效率很低,所以比较适合读多写少的场景。
另外需要说一句,CopyOnWriteArraySet 使用 CopyOnWriteArrayList 实现。Set 一如继往喜欢使用现成的类来实现。
原文