集合 - CopyOnWriteArrayList
前言
ArrayList 是一个非线程安全集合，需要使用方自行处理线程安全问题，或者使用 Collections.synchronizedList 包装。从 JDK 1.5 开始 JUC 中提供了使用写时复制机制实现的并发容器 CopyOnWriteArrayList。
概述
CopyOnWriteArrayList 遵从 CopyOnWrite，顾名思义就是写时复制。简单来说就是当我们操作容器时并不直接操作当前容器，而是先根据当前容器复制出一个新的容器，然后在这个新的容器上操作，完成操作后再将原容器引用指向新容器。
源码解析
CopyOnWriteArrayList 的类继承关系类图如下:
属性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 8673264195747942595L;
final transient ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array;
}
|
CopyOnWriteArrayList 核心属性就是以上两个。lock 用于保护所有更改操作，控制并发写操作。array 作为内部数组用于保存数据，读操作都是操作当前 array，写操作都是根据当前 array 复制一个新的 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
| 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();
}
}
|
下面对上述代码流程进行说明：
- 使用
ReentrantLock 独占锁保证同时只有一个线程对集合进行写操作。
- 数据存储在
CopyOnWriteArrayList 的内部 array 数组中。
- 元素并不是直接存储到 array 数组中，而是复制出一个新的数组，并且复制出的数组的长度是旧数组长度+1，然后将元素加入到新数组中，最后再把旧的数组替换成新的数组。
查询
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public E get(int index) {
return get(getArray(), index);
}
@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
return (E) a[index];
}
|
由于整个 get 方法是没有加锁的，而 CopyOnWriteArrayList 的写操作是通过复制出新的数组来完成操作的，这可能会导致读写的短暂不一致。
修改
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
| 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 {
setArray(elements);
}
return oldValue;
} finally {
lock.unlock();
}
}
|
和 add 方法类似，不同的是对要修改的元素进行判断。
删除
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
| 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();
}
}
|
删除方法和其它修改方法类似，先是获取独占锁来保证线程安全，接着判断要删除的元素是否是最后一个，如果是最后一个则复制出一个长度-1的新数组然后替换掉旧数组；如果要删除的元素不是最后一个，则分两次复制，随后替换旧数组。
迭代器
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
|
static final class COWIterator<E> implements ListIterator<E> {
private final Object[] snapshot;
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 void remove() {
throw new UnsupportedOperationException();
}
public void set(E e) {
throw new UnsupportedOperationException();
}
public void add(E e) {
throw new UnsupportedOperationException();
}
}
|
当获取迭代器时，内部会调用 COWIterator 的构造方法，该构造方法有两个参数，一个是 array 数组，另一个是下标 0 。构造方法中会把 array 数组赋值给 snapshot 变量，当其他线程进行了增删改的操作，旧的数组会被新的数组给替换掉，但是 snapshot 还是原来旧的数组的引用。当我们使用迭代器遍历 CopyOnWriteArrayList 的时候，不能保证拿到的数据是最新的，这是弱一致性问题。
设计特点
CopyOnWriteArrayList 仅适用于写操作非常少的场景，而且能够容忍读写的短暂不一致。虽然采用了读写分离思想，但写操作时内存里会同时存在两个对象的内存，若这些对象占用内存较大，可能会带来系列问题，如造成频繁 GC。
小结
CopyOnWriteArrayList 是 Java 并发包中相对比较简单的一个实现，它的核心思想是写时复制机制，支持并发读写，但带来的后果是内存 double 和数据一致性问题。
