深入浅出 JAVA 之集合 - CopyOnWriteArrayList
文章目录
!版权声明：本博客内容均为原创,每篇博文作为知识积累,写博不易,转载请注明出处。
系统环境
- JDK 版本: OpenJDK 8
参考地址:
一、CopyOnWriteArrayList 简介
CopyOnWriteArrayList 是一种线程安全的 List 接口实现，它采用了读写分离的思想，即读取操作和修改操作分别在不同的内部数组中进行，从而实现了读取操作的高效性和修改操作的线程安全性。
具体来说，当 CopyOnWriteArrayList 被修改时，它会创建一个新的内部数组，并将修改操作应用于这个新的数组，而不是直接在原数组上进行修改。这个过程虽然会增加内存的开销，但由于读取操作并不会被加锁，所以可以允许多个线程同时进行读取操作，从而提高了整个程序的并发性能。
注: 由于 CopyOnWriteArrayList 将修改操作应用于新的数组上，因此在进行迭代操作时，迭代器可能会看不到最新的修改，因为迭代器仍然指向旧的数组。因此，CopyOnWriteArrayList 适用于读取操作远远多于修改操作的场合，而不适合频繁进行修改操作。
二、CopyOnWriteArrayList 主要特性
CopyOnWriteArrayList 的主要特性如下：
- 线程安全: CopyOnWriteArrayList是线程安全的，多个线程可以同时读取内部数组，而不会出现数据覆盖等并发问题。
- 读写分离: CopyOnWriteArrayList采用了读写分离的思想，即读取操作和修改操作分别在不同的内部数组中进行，从而提高了读取操作的效率。
- 内存开销较大: 由于每次修改都会创建一个新的内部数组，因此CopyOnWriteArrayList的内存开销比较大，特别是在修改操作比较频繁的情况下。
- 迭代器不支持修改操作: 由于迭代器依赖于内部数组，并且每次修改都会创建一个新的内部数组，因此迭代器不支持修改操作，否则会抛出ConcurrentModificationException异常。
- 适用于读取操作远远多于修改操作的场合: 由于每次修改都会创建一个新的内部数组，因此CopyOnWriteArrayList适用于读取操作远远多于修改操作的场合，特别是基于事件的编程模型中的回调函数列表等场合
ArrayList 的优缺点是什么
三、CopyOnWriteArrayList 的常见操作方法有哪些
ConcurrentArrayList 扩展了标准的 ArrayList ，提供了线程安全的读写操作，以下是一些常见的操作方法：
- add(E e): 添加元素到集合末尾。
- add(int index, E element): 在指定位置插入元素。
- addAll(Collection<? extends E> c): 将一个集合中的所有元素添加到列表末尾。
- get(int index): 获取指定位置上的元素。
- indexOf(Object o): 返回指定元素在列表中第一次出现的位置。
- isEmpty(): 判断列表是否为空。
- remove(Object o): 从列表中删除指定元素。
- remove(int index): 从列表中删除指定位置的元素。
- set(int index, E element): 将指定位置的元素替换为指定元素。
- size(): 返回列表的大小。
需要注意的是， ConcurrentArrayList 的常见操作方法和 ArrayList 大致相同，但是在多线程环境下它们提供了不同的线程安全保障。
四、CopyOnWriteArrayList 的优缺点是什么
CopyOnWriteArrayList 的优点和缺点如下：
CopyOnWriteArrayList 的优点:
- 线程安全: CopyOnWriteArrayList 是线程安全的，多个线程可以并发读取数据，而不需要额外的同步机制。
- 高效: CopyOnWriteArrayList 在读多写少的场景下表现优异，因为写操作并不会影响到读操作，读操作也不会被锁定，从而提高了系统的并发性能。
- 不需要加锁: CopyOnWriteArrayList 在写操作时创建新的数组，读操作仍旧在老的数组中进行，因此它不需要额外的加锁机制，避免了线程间的竞争，提高了系统的并发性能。
CopyOnWriteArrayList 的缺点:
- 内存占用高: 由于每次写操作都会新建一个数组，因此内存占用会比较高。如果写操作很频繁，那么会造成资源浪费。
- 读操作不能实时反映最新结果: 由于写操作不会对老数组进行修改，因此在写操作完成之前，读操作只能看到老数组中的数据，不能及时反映最新的结果。
- 不适合实时性要求高的场景: 由于读操作不能实时反映最新结果，因此它并不适合实时性要求比较高的场景，例如金融交易等场景。
五、CopyOnWriteArrayList 如何保证线程安全
CopyOnWriteArrayList 通过使用 "写时复制" 的方式来保证线程安全。
在每次写操作时，它都会创建一个新的数组，并将原有数组中的元素复制到新数组中，然后再在新数组中进行写操作。
通过这种方式，读操作可以在原有数组中进行，并且不需要额外的同步机制来保证线程之间的安全性。只有在写操作完成后，才会将新数组赋值给原有数组，从而完成一次写操作。
这种写时复制的方式，保证了写操作和读操作的并发执行，从而提高了系统的并发性能。但是需要注意的是，这种方式会导致内存占用较高，因为每个副本都需要占用一定的内存空间。
六、CopyOnWriteArrayList 底层结构
CopyOnWriteArrayList 底层结构是一个数组，它是通过 volatile 修饰的 Object[] 数组来存储元素的，即：
1private transient volatile Object[] array;
在 CopyOnWriteArrayList 中，读取操作和修改操作是在不同的数组上进行的，即读取操作是在当前的 array 数组上进行的，而修改操作是在新的数组上进行的。当进行修改操作时，CopyOnWriteArrayList 会创建一个新的数组，将原来的元素复制到新的数组中，然后再进行修改操作，最后将新的数组的引用赋值给 array，完成修改操作。当进行读取操作时，CopyOnWriteArrayList 则直接在当前的 array 数组上进行。
七、CopyOnWriteArrayList 源码 - 属性
1/** 可重入锁对象 */
2final transient ReentrantLock lock = new ReentrantLock();
3
4/** 存储元素的数组 */
5private transient volatile Object[] array;
八、CopyOnWriteArrayList 源码 - 关键方法
8.1 构造方法 CopyOnWriteArrayList
(1) 无参构造方法
1/**
2 * 无参构造方法，创建一个空数组
3 */
4public CopyOnWriteArrayList() {
5 setArray(new Object[0]);
6}
(2) 支持根据已有 Collection 集合创建新集合的构造方法
1/**
2 * 支持根据已有 Collection 集合创建新集合的构造方法
3 *
4 * @param c 已有的 Collection 集合
5 * @throws NullPointerException 空指针异常
6 */
7public CopyOnWriteArrayList(Collection<? extends E> c) {
8 // 创建新数组
9 Object[] elements;
10 // 判断传入的集合是否为 CopyOnWriteArrayList 类型:
11 // - 如果是，则直接将传入集合的数组作为新集合的数组；
12 // - 如果不是，则将集合转换为数组来充当新集合的数组，然后判断传入集合是否为 ArrayList 类型，
13 // 如果不是则将元素转换为 Object[] 类型；
14 if (c.getClass() == CopyOnWriteArrayList.class) {
15 elements = ((CopyOnWriteArrayList<?>)c).getArray();
16 } else {
17 elements = c.toArray();
18 if (c.getClass() != java.util.ArrayList.class) {
19 // 因为 ArrayList 集合中的数组为 Object[] 类型，但是如果集合不是 ArrayList 类型，
20 // 则数组元素类型可能不是 Object 类型，所以这里需要执行一遍复制转换过程；
21 elements = Arrays.copyOf(elements, elements.length, Object[].class);
22 }
23 }
24 // 设置新创建的数组作为集合存储元素的数组
25 setArray(elements);
26}
(3) 支持根据已有数组创建新集合的构造方法
1/**
2 * 支持根据已有数组创建新集合的构造方法
3 *
4 * @param toCopyIn 已有的数组
5 * @throws NullPointerException 空指针异常
6 */
7public CopyOnWriteArrayList(E[] toCopyIn) {
8 // 创建新数组，并从传入数组中复制元素且转换位 Object 类型到新数组中
9 setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
10}
8.2 末尾位置插入元素方法 add(E e)
add(E e)
1/**
2 * 在集合末尾插入一个元素
3 *
4 * @param e 插入的元素
5 * @return 插入成功则返回 true
6 */
7public boolean add(E e) {
8 // 获取可重入锁对象
9 final ReentrantLock lock = this.lock;
10 // 上锁
11 lock.lock();
12 try {
13 // 获取集合存储元素的数组
14 Object[] elements = getArray();
15 // 获取元素数组长度赋给贝变量 len
16 int len = elements.length;
17 // 创建一个长度为 len+1 的新数组，并且将原先数据转移到新数组中
18 Object[] newElements = Arrays.copyOf(elements, len + 1);
19 // 将新插入的元素添加到数组末尾索引位置
20 newElements[len] = e;
21 // 设置新创建的数组作为集合存储元素的数组
22 setArray(newElements);
23 // 插入成功，返回 true
24 return true;
25 } finally {
26 // 解锁
27 lock.unlock();
28 }
29}
getArray()
1/**
2 * 获取集合存储元素的数组
3 */
4final Object[] getArray() {
5 return array;
6}
8.3 指定位置插入元素方法 add(int index, E element)
1/**
2 * 指定位置插入元素方法
3 *
4 * @param index 插入的索引位置
5 * @param element 要插入的元素
6 * @throws IndexOutOfBoundsException 索引越界异常
7 */
8public void add(int index, E element) {
9 // 获取可重入锁对象
10 final ReentrantLock lock = this.lock;
11 // 上锁
12 lock.lock();
13 try {
14 // 获取集合存储元素的数组
15 Object[] elements = getArray();
16 // 获取元素数组长度赋给贝变量 len
17 int len = elements.length;
18 // 判断待插入的索引是否在元素数组长度范围内，如果不在则抛出数组越界异常
19 if (index > len || index < 0) {
20 throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+len);
21 }
22 // 创建记录新数组的变量
23 Object[] newElements;
24 // 计算需要从指定索引位置开始往后挪移的元素数量
25 int numMoved = len - index;
26 // 判断挪移数量是否为 0:
27 // - 如果数量为 0，则相当于在数组末尾插入新元素，则直接创建一个长度为 len+1 的新数组，并且将原先数据转移到新数组中，
28 // 最后将新插入的元素添加到数组指定索引位置；
29 // - 如果数量不为 0，则相当在数组指定位置插入新元素，则创建一个 len+1 的新数组，然后复制索引位置之前的数据到新数组中，
30 // 再复制索引位置之后的数据到新数组中，最后将新插入的元素添加到数组指定索引位置；
31 if (numMoved == 0) {
32 newElements = Arrays.copyOf(elements, len + 1);
33 } else {
34 newElements = new Object[len + 1];
35 System.arraycopy(elements, 0, newElements, 0, index);
36 System.arraycopy(elements, index, newElements, index + 1, numMoved);
37 }
38 newElements[index] = element;
39 // 设置新创建的数组作为集合存储元素的数组
40 setArray(newElements);
41 } finally {
42 // 解锁
43 lock.unlock();
44 }
45}
8.4 删除指定位置元素方法 remove(int index)
1/**
2 * 删除指定位置元素
3 *
4 * @throws IndexOutOfBoundsException {@inheritDoc}
5 */
6public E remove(int index) {
7 // 获取可重入锁对象
8 final ReentrantLock lock = this.lock;
9 // 上锁
10 lock.lock();
11 try {
12 // 获取集合存储元素的数组
13 Object[] elements = getArray();
14 // 获取元素数组长度赋给贝变量 len
15 int len = elements.length;
16 // 获取待删除元素位置的元素值赋给变量 oldValue
17 E oldValue = get(elements, index);
18 // 计算需要挪移的元素数量
19 int numMoved = len - index - 1;
20 // 判断挪移数量是否为 0:
21 // - 如果数量为 0，则相当于在数组末尾删除元素，则直接创建一个长度为 len-1 的新数组，这样相当于删除了末尾的元素；
22 // - 如果数量不为 0，则相当在数组指定位置删除元素，则创建一个 len-1 的新数组，然后复制索引位置之前的数据到新数组中，
23 // 再复制索引位置之后的数据到新数组中，唯独不复制待删除索引位置的元素，这样相当于删除了该元素；
24 if (numMoved == 0) {
25 setArray(Arrays.copyOf(elements, len - 1));
26 } else {
27 Object[] newElements = new Object[len - 1];
28 System.arraycopy(elements, 0, newElements, 0, index);
29 System.arraycopy(elements, index + 1, newElements, index, numMoved);
30 // 设置新创建的数组作为集合存储元素的数组
31 setArray(newElements);
32 }
33 // 返回删除前待删除索引位置的元素值
34 return oldValue;
35 } finally {
36 lock.unlock();
37 }
38}
8.5 删除指定元素值的元素方法 remove(Object o)
remove(Object o)
1/**
2 * 删除指定元素值的元素
3 *
4 * @param o 待删除的元素 (如果存在)
5 * @return 如果删除成功则返回 true，否则返回 false
6 */
7public boolean remove(Object o) {
8 // 创建变量 snapshot 存储集合当前存储元素的数组
9 Object[] snapshot = getArray();
10 // 查找指定元素值在数组中的索引
11 int index = indexOf(o, snapshot, 0, snapshot.length);
12 // 判断索引是否小于 0:
13 // - 如果是，则说明在数组中没有找到该索引值，index=-1，所以返回 false；
14 // - 如果否则说明在数组中找到了该索引值，这时候调用 remove 方法从数组中删除该元素；
15 return (index < 0) ? false : remove(o, snapshot, index);
16}
indexOf(Object o, Object[] elements, int index, int fence)
1/**
2 * 查找指定元素索引
3 *
4 * @param o 待查找的元素值
5 * @param elements 待查找的元素数组
6 * @param index 查找的起始索引位置
7 * @param fence 查找的结束索引位置
8 * @return 返回查找到的索引，如果没有找到则返回 -1
9 */
10private static int indexOf(Object o, Object[] elements, int index, int fence) {
11 // 判断待查找的元素值是否为 null:
12 // - 如果为 null，则从 i 索引位置开始遍历，到 fence 位置截止，查找元素值为 null 的索引；
13 // - 如果不为 null，则从 i 索引位置开始遍历，到 fence 位置截止，查找元素值为 o 的索引；
14 if (o == null) {
15 for (int i = index; i < fence; i++) {
16 if (elements[i] == null) {
17 return i;
18 }
19 }
20 } else {
21 for (int i = index; i < fence; i++) {
22 if (o.equals(elements[i])) {
23 return i;
24 }
25 }
26 }
27 // 没有找到返回 -1
28 return -1;
29}
remove(Object o, Object[] snapshot, int index)
1/**
2 * 删除指定数组中指定索引位置和元素值的元素
3 */
4private boolean remove(Object o, Object[] snapshot, int index) {
5 // 获取可重入锁对象
6 final ReentrantLock lock = this.lock;
7 // 上锁
8 lock.lock();
9 try {
10 // 获取当前集合存储元素的数组
11 Object[] current = getArray();
12 // 获取元素数组长度赋给贝变量 len
13 int len = current.length;
14 // 判断 snapshot 变量记录的数组是否和 current 变量记录的当前数组相同，
15 // - 如果不相同，则在新数组中查找元素值的索引位置；
16 // - 如果相同，则执行后续的数组数据转移和删除操作；
17 if (snapshot != current) {
18 // 设置标签，当 : 中 {} 里面的代码逻辑满足后执行 continue 或者 break 时，
19 // 后面加标签，这样在执行完 continue 或者 break 操作后就会回到标签的位置，
20 // 不再执行 continue 或 break 后面的代码逻辑，直接执行标签的下一行代码。
21 // 用法类似于 C/C++ 中的 goto 关键字
22 findIndex:
23 {
24 // 使待查找的索引和当前数组长度进行比较，获取其中较小的值，作为下一步循环的结束位置
25 int prefix = Math.min(index, len);
26 // 进行循环，使待删除的元素值与当前集合元素数组中的元素进行比较，以 prefix 为遍历结束点，
27 // 然后判断是否相同，如果相同则直接设置循环到的位置作为索引，然后执行 break findIndex，
28 // 回到 findIndex 代码位置
29 for (int i = 0; i < prefix; i++) {
30 if (current[i] != snapshot[i] && eq(o, current[i])) {
31 index = i;
32 break findIndex;
33 }
34 }
35 // 判断待删除的索引是否大于当前数组长度，如果是则表示遍历新数组也没有找到待删除元素的索引位置，
36 // 则返回 false，表示删除失败，该元素可能已经被删除。
37 if (index >= len) {
38 return false;
39 }
40 // 如果数组 index 位置正好与待删除的索引值内存地址相同，则直接执行 break findIndex，回到
41 // findIndex 代码位置
42 if (current[index] == o) {
43 break findIndex;
44 }
45 // 再次调用 indexOf 方法从当前数组中查找待删除元素值的索引
46 index = indexOf(o, current, index, len);
47 // 如果 index=-1，即小于 0，则说明当前数组中没有找到这个待删除的元素值，可能已经删除掉了，
48 // 这里直接返回 false
49 if (index < 0) {
50 return false;
51 }
52 }
53 }
54 // 创建一个长度为 len-1 的新数组，然后复制索引位置之前的数据到新数组中，再复制索引位置之后的数据到新数组中，
55 // 唯独不复制待删除索引位置的元素，这样相当于删除了该元素；
56 Object[] newElements = new Object[len - 1];
57 System.arraycopy(current, 0, newElements, 0, index);
58 System.arraycopy(current, index + 1, newElements, index, len - index - 1);
59 // 设置新创建的数组作为集合存储元素的数组
60 setArray(newElements);
61 // 返回 true
62 return true;
63 } finally {
64 // 解锁
65 lock.unlock();
66 }
67}
8.6 获取指定索引位置元素值方法 get(int index)
get(int index)
1/**
2 * 获取指定索引位置的元素值
3 *
4 * @param index 索引位置
5 * @return 指定索引位置的元素值
6 */
7public E get(int index) {
8 // 获取当前集合存储元素的数组，然后调用 get(Object[] a, int index) 方法，获取指定索引位置元素
9 return get(getArray(), index);
10}
get(Object[] a, int index)
1/**
2 * 获取指定数组下指定位置的元素值
3 *
4 * @param a 待操作的数组
5 * @param index 指定的索引位置
6 * @return 指定索引位置的元素值
7 */
8@SuppressWarnings("unchecked")
9private E get(Object[] a, int index) {
10 return (E) a[index];
11}
8.7 设置指定索引位置元素值方法 set(int index, E element)
set(int index, E element)
1/**
2 * 设置指定索引位置元素值
3 *
4 * @param index 索引
5 * @param element 元素值
6 * @return 先前位于指定位置的元素
7 * @throws IndexOutOfBoundsException 索引越界异常
8 */
9public E set(int index, E element) {
10 // 获取可重入锁对象
11 final ReentrantLock lock = this.lock;
12 // 上锁
13 lock.lock();
14 try {
15 // 获取集合存储元素的数组
16 Object[] elements = getArray();
17 // 获取待替换元素位置的元素值赋给变量 oldValue
18 E oldValue = get(elements, index);
19 // 判断待替换索引位置的元素是否和新元素相同:
20 // - 如果不相同，则创建一个新数组，然后转移旧数组中的元素，之后将新数组指定索引位置的元素替换为新元素，
21 // 最好设置新创建的数组作为集合存储元素的数组
22 // - 如果相同，则继续将旧数组作为集合存储元素的数组
23 if (oldValue != element) {
24 int len = elements.length;
25 Object[] newElements = Arrays.copyOf(elements, len);
26 newElements[index] = element;
27 setArray(newElements);
28 } else {
29 setArray(elements);
30 }
31 // 返回先前位于指定位置的元素
32 return oldValue;
33 } finally {
34 // 解锁
35 lock.unlock();
36 }
37}
九、ConcurrentArrayList 中的疑问
9.1 ConcurrentArrayList 是否有性能问题？
9.2 ConcurrentArrayList 如何保证线程安全？
!版权声明：本博客内容均为原创,每篇博文作为知识积累,写博不易,转载请注明出处。