🔍 基于JDK1.8的CopyOnWriteArrayList源码解析。

⚡ 涉及的API:System#copyArray(Object src, int srcPos,Object dest, int destPos, int length)

用于数组克隆,参数如下:

  1. src:原数组
  2. srcPos:原数组克隆的起始位置
  3. dest:新数组
  4. destPos:新数组克隆的起始位置
  5. 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() {
// 直接创建一个长度为0的Object数组,赋值给array
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();
// c的类型不为Object,转换为Object
if (elements.getClass() != Object[].class)
elements = Arrays.copyOf(elements, elements.length, Object[].class);
}
// 将新数组的赋值给array
setArray(elements);
}

数组构造:

1
2
3
4
public CopyOnWriteArrayList(E[] toCopyIn) {
// 拷贝一份数组赋值给array
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 {
// 获取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();
}
}

流程:

  1. 获取独占锁
  2. 加锁
  3. 复制一份array给新数组,新数组长度为array的长度+1
  4. 在新数组的末尾添加新元素
  5. 将新数组赋值给array
  6. 释放独占锁

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 {
// 获取array
Object[] elements = getArray();
// 获取array
int len = elements.length;
// 检查index的合法性
if (index > len || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+len);
// 新数组,长度为array.length + 1
Object[] newElements;
// 需要移动的元素数量,在index之后(包含index)的元素全部需要移动
int numMoved = len - index;
// 插在数组末尾,不需要移动
if (numMoved == 0)
newElements = Arrays.copyOf(elements, len + 1);
// 插在数组中部,后面元素移动
else {
newElements = new Object[len + 1];
// 将index之前的元素复制到新数组中,位置不变
System.arraycopy(elements, 0, newElements, 0, index);
// 将index及之后的元素复制到新数组中,下标+1
System.arraycopy(elements, index, newElements, index + 1,
numMoved);
}
// 将新元素插入到index位置
newElements[index] = element;
// 将新数组赋值给array
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 {
// 获取array
Object[] elements = getArray();
// 获取array下标为index的元素
E oldValue = get(elements, index);
// 如果旧元素与新元素不相等
if (oldValue != element) {
int len = elements.length;
// 复制一份新数组,长度和array保持一致
Object[] newElements = Arrays.copyOf(elements, len);
// 修改新数组index下标的值
newElements[index] = element;
// 将新数组赋值给array
setArray(newElements);
} else {
// 即时新值和旧值一致,为了确保volatile语义,需要重新设置array
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 {
// 获取array
Object[] elements = getArray();
// 获取array长度
int len = elements.length;
// 获取待删除元素
E oldValue = get(elements, index);
// 需要移动的元素数量,在index之后(不包含index)的元素全部需要移动
int numMoved = len - index - 1;
// 如果删除元素在末尾,需要移动
if (numMoved == 0)
// 直接复制一份新数组,最后一个元素丢弃
// 并将新数组赋值给array
setArray(Arrays.copyOf(elements, len - 1));
// 如果删除元素在中部,index及后面元素移动
else {
// 新数组,长度为array.length - 1
Object[] newElements = new Object[len - 1];
// 将index之前的元素复制到新数组中,位置不变
System.arraycopy(elements, 0, newElements, 0, index);
// 将index之后的元素复制到新数组中,下标 - 1
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
// 将新数组的值赋值给array
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. 线程1调用get方法获取值,内部通过getArray方法获取到array数组;
  2. 线程2调用add/set/remove方法,内部通过setArray方法修改了array数组;
  3. 线程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());
}

保证迭代器在另一个添加数据的线程前获取,结果如下:

1
Hello

📓 总结

  1. CopyOnWriteArrayList体现了写时复制的思想,增删改都是在副本中进行;

  2. CopyOnWriteArrayList的取值方法是弱一致性的,无法确保实时获得的是最新的数据;

  3. CopyOnWriteArrayList的增删改操作都是在独占式可重入锁中进行,保证线程安全;

  4. CopyOnWriteArrayList的线程安全性体现在多线程修改不会抛出
    java.util.ConcurrentModificationException异常,并不能保证数据的强一致性;

  5. 同一时刻,只能有一个线程可以对CopyOnWriteArrayList进行增删改操作,而读操作没有限制。增删改操作都需要复制一份新数组,增加了内存消耗,所以更适用于读多写少的场景。