🔍 基于JDK1.8的CopyOnWriteArrayList源码解析。
⚡ 涉及的API：System#copyArray(Object src, int srcPos,Object dest, int destPos, int length)
用于数组克隆，参数如下：
- src：原数组
- srcPos：原数组克隆的起始位置
- dest：新数组
- destPos：新数组克隆的起始位置
- length：克隆的长度
基本知识
始于：JDK 1.5
作者：Doug Lea
特点：线程安全，写时加锁，读不加锁，支持读多写少的场景
思想：写时复制（copy on write，简称COW）
写时复制是CS领域的一种优化策略，核心思想是，如果有多个调用者同时请求相同的资源，它们会获取相同的指针指向的资源；如果某个调用者试图修改资源的内容时，复制一份副本给该调用者，该调用者修改的便是副本，其他调用者所见的依然是最初的资源，当修改完毕时，使用副本替换原始资源。
类图：
基本属性
两个属性，简单明了；数组存储数据，独占锁保证线程安全。
1
2
3
4
5
|
final transient ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array;
|
构造函数
无参构造：
1
2
3
4
5
6
7
8
| final void setArray(Object[] a) {
array = a;
}
public CopyOnWriteArrayList() {
setArray(new Object[0]);
}
|
集合构造：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public CopyOnWriteArrayList(Collection<? extends E> c) {
Object[] elements;
if (c.getClass() == CopyOnWriteArrayList.class)
elements = ((CopyOnWriteArrayList<?>)c).getArray();
else {
elements = c.toArray();
if (elements.getClass() != Object[].class)
elements = Arrays.copyOf(elements, elements.length, Object[].class);
}
setArray(elements);
}
|
数组构造：
1
2
3
4
| public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
|
add(E e)
用途：向数组末尾添加一个元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| 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();
}
}
|
流程：
- 获取独占锁
- 加锁
- 复制一份
array给新数组，新数组长度为array的长度+1
- 在新数组的末尾添加新元素
- 将新数组赋值给
array
- 释放独占锁
add (int index, E element)
用途：在数组的指定下标添加指定元素。
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
| public void add(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
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)
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();
}
}
|
set(int index, E element)
用途：设置数组指定下标的元素。
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
| 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();
}
}
|
remove(int index)
用途：删除数组指定下标的元素。
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
| 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();
}
}
|
get(int index)
用途：获取数组指定下标的值。
1
2
3
4
5
6
7
| public E get(int index) {
return get(getArray(), index);
}
private E get(Object[] a, int index) {
return (E) a[index];
}
|
整个过程并没有加锁，在并发环境下可能出现如下情况：
- 线程1调用
get方法获取值，内部通过getArray方法获取到array数组；
- 线程2调用
add/set/remove方法，内部通过setArray方法修改了array数组；
- 线程1看的依然是曾经的
array。
因此，get方法是弱一致性的。
Iterator
迭代器，用于遍历数组元素。
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
| public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
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;
}
@SuppressWarnings("unchecked")
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}
}
|
当我们调用interator()方法获取迭代器时，实际上返回一个COWIterator对象，其中快照snapshot保存的是当前array的内容，下标cursor为0。
迭代器没有在锁中进行，依然是弱一致性的。
比如，以下代码：
1
2
3
4
5
6
7
8
9
10
| CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("Hello");
Thread thread = new Thread(() -> {
list.add("KHighness");
});
Iterator<String> iterator = list.iterator();
thread.start();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
|
保证迭代器在另一个添加数据的线程前获取，结果如下：
最后小结
CopyOnWriteArrayList体现了写时复制的思想，增删改都是在副本中进行；
CopyOnWriteArrayList的取值方法是弱一致性的，无法确保实时获得的是最新的数据；
CopyOnWriteArrayList的增删改操作都是在独占式可重入锁中进行，保证线程安全；
CopyOnWriteArrayList的线程安全性体现在多线程修改不会抛出
java.util.ConcurrentModificationException异常，并不能保证数据的强一致性；
同一时刻，只能有一个线程可以对CopyOnWriteArrayList进行增删改操作，而读操作没有限制。增删改操作都需要复制一份新数组，增加了内存消耗，所以更适用于读多写少的场景。
