java8集合框架(九)-List的实现类(CopyOnWriteArrayList)

java8集合框架(九)-List的实现类(CopyOnWriteArrayList)

第七篇分析了ArrayList的源码。本篇分析的CopyOnWriteArrayList也同样基于数组实现,只是后者是线程安全版本,为并发而生,可以有效避免在多线程环境发生修改导致的ConcurrentModificationException。其内部机制是怎样的呢?

Note:本篇源码分析基于jdk1.8版本

CopyOnWriteArrayList

CopyOnWriteArrayList的核心数据结构是数组。为实现线程安全,任何”破坏性”操作都会拷贝生成新的数组。名字叫做CopyOnWrite意思就是在写操作时执行拷贝。值得注意的是,CopyOnWriteArrayListiterator不支持removeaddset方法。调用它们会产生UnsupportedOperationException。可接受null

数据结构

CopyOnWriteArrayList的核心数据结构是数组。实现了RandomAccess支持随机访问。

1
2
3
4
//元素存放的数组
private transient volatile Object[] array;
//破坏操作需要的锁
final transient ReentrantLock lock = new ReentrantLock();

初始化

1
2
3
4
5
6
7
8
//默认数组长度为0
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

说明:ArrayList默认大小是10,而CopyOnWriteArrayList默认大小是0。setArray每次将array指向新数组。

增删改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
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);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
public void add(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
//range检查
if (index > len || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+len);
Object[] newElements;
int numMoved = len - index;
if (numMoved == 0)
newElements = Arrays.copyOf(elements, len + 1);
else {
newElements = new Object[len + 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index, newElements, index + 1,
numMoved);
}
newElements[index] = element;
setArray(newElements);
} finally {
lock.unlock();
}
}
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];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements);
}
return oldValue;
} finally {
lock.unlock();
}
}
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字段。但是一方面会对内存造成压力,另一方面也降低了效率。所以CopyOnWriteArrayList要用在读远超于写的场景下,据说90+%以上的读操作使用较为妥当。

查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public E get(int index) {
return get(getArray(), index);
}
private E get(Object[] a, int index) {
return (E) a[index];
}
//指定元素的索引
public int indexOf(Object o) {
//循环遍历对比,O(n)
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}

说明:O(1)的读取效率,读的时候也没有加锁。因为读的是snapshot,也正因为如此,在有修改的时候,读不满足强一致性,更佐证了其适用场景。

ListIterator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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;
}
@SuppressWarnings("unchecked")
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}
@SuppressWarnings("unchecked")
public E previous() {
if (! hasPrevious())
throw new NoSuchElementException();
return (E) snapshot[--cursor];
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor-1;
}
public void remove() {
throw new UnsupportedOperationException();
}
public void set(E e) {
throw new UnsupportedOperationException();
}
public void add(E e) {
throw new UnsupportedOperationException();
}
}

说明:COWIterator是阉割版本的ListItr,不支持removesetadd操作。而我们知道CopyOnWriteArrayList是支持遍历的时候remove元素,这时候不能调用Iterator#remove,应该使用CopyOnWriteArrayList#remove。这点刚好跟ArrayList相反。ArrayList在遍历的时候remove只能调用Iterator#remove,调用ArrayList#remove会报ConcurrentModificationException

使用场景

首先应该弄明白为什么有了ArrayList还要写CopyOnWriteArrayList呢?前者有什么场景不能满足而必须使用到后者呢?既然这个类是为了高并发写的,那么看看ArrayList在高并发下会出现什么问题可能是一个线索。

1
2
3
4
5
6
//ArrayList.java
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

高并发下add问题很多:

  1. size统计不准确,size的值也不可预期。
  2. 10个线程并发执行新增元素,elementData[size++] = e;结果可能是只新增了一个元素,其他元素均被覆盖。

在反过来看CopyOnWriteArrayList的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//CopyOnWriteArrayList.java
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}

即使在高并发下,也能保证10个线程并发执行新增元素一定新增10个元素。

还有一点就是老生常谈的ConcurrentModificationExceptionCopyOnWriteArrayList保证不会抛出这样的异常。保证了高并发下读(包括遍历)和写同时进行,这点也是ArrayList做不到的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//ArrayList.java
//注意这里的checkForComodification函数
public E get(int index) {
rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
//listIterator#next
public E next() {
checkForComodification();
int i = cursor;
if (i >= SubList.this.size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[offset + (lastRet = i)];
}

思考

CopyOnWriteArrayListVector的异同

虽然两个都是ArrayList的线程安全版本,但是它们却不是等价的
Vector是很古老的实现,来自jdk1.0版本。它的实现也非常简单粗暴:在每个方法前面都添加synchronized。不仅效率非常低下,也仅实现了增删改查的原子操作。而CopyOnWriteArrayList就不一样了,通过上面的分析,它不仅实现了增删改的线程安全性(注意不是原子操作),还能防止抛出ConcurrentModificationException异常。这一点Vector是做不到的。

总结

CopyOnWriteArrayListArrayList现代化的线程安全版本,适用于读多写少的高并发环境。支持多线程并发的读写操作而不抛出ConcurrentModificationException异常。它的迭代器不支持增删改动作,可以完全替代Vector。自此,JDK中List的三个实现类就都分析完毕了,各有各的特点,各有各的适用场景。没有最好的只有最合适的~

参考

作者: wuzhaoyang(John)
出处: http://wuzhaoyang.me/
因为作者水平有限,无法保证每句话都是对的,但能保证不复制粘贴,每句话经过推敲。希望能表达自己对于技术的态度,做一名优秀的软件工程师。