18.jdk源码阅读之CopyOnWriteArrayList

1. 写在前面

CopyOnWriteArrayList 是 Java 中的一种线程安全的 List 实现，基于“写时复制”（Copy-On-Write）机制。下面几个问题大家可以先思考下，在阅读源码的过程中都会解答：

1. CopyOnWriteArrayList 适用于哪些场景？
2. CopyOnWriteArrayList 如何保证线程安全？
3. CopyOnWriteArrayList 的优缺点是什么？
4. 为什么 CopyOnWriteArrayList 的迭代器是安全的？
5. CopyOnWriteArrayList 与 ArrayList 有什么区别？
6. 如何在 CopyOnWriteArrayList 中进行批量操作？
7. 如何在 CopyOnWriteArrayList 中进行批量操作？

2. 全局视角

2.1 RandomAccess

RandomAccess 是 Java 集合框架中的一个标识接口（Marker Interface），它定义在 java.util 包中。实现 RandomAccess 接口的类表示其支持快速（通常是常数时间复杂度 O(1)）的随机访问操作。
RandomAccess 接口本身是一个空接口，没有任何方法。其定义如下：

package java.util;

public interface RandomAccess {
}
1
2
3
4

2.1.1 标识快速随机访问能力

• 实现 RandomAccess 接口的类表明它们支持快速的随机访问操作。具体来说，这意味着 get(int index) 和 set(int index, E element) 操作的时间复杂度通常是 O(1)。
• 例如，ArrayList 实现了 RandomAccess 接口，因为它基于数组实现，能够在常数时间内访问任意索引位置的元素。

2.1.2 优化算法选择

• 一些算法可以根据集合是否实现了 RandomAccess 接口来选择更合适的实现方式。例如，Collections 类中的一些方法会检查传入的列表是否实现了 RandomAccess 接口，从而决定是使用基于索引的循环还是使用迭代器进行遍历。
• 例如，Collections.sort 方法在对列表进行排序时，如果列表实现了 RandomAccess 接口，它将使用基于索引的访问方式，否则将使用迭代器。

2.1.3 如何使用 RandomAccess 接口来优化算法

以下是一个简单的示例，展示了如何使用 RandomAccess 接口来优化算法选择：

import java.util.*;

public class RandomAccessExample {
    public static void main(String[] args) {
        List<Integer> arrayList = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
        List<Integer> linkedList = new LinkedList<>(Arrays.asList(1, 2, 3, 4, 5));

        printList(arrayList);
        printList(linkedList);
    }

    public static void printList(List<Integer> list) {
        if (list instanceof RandomAccess) {
            System.out.println("Using index-based loop");
            for (int i = 0; i < list.size(); i++) {
                System.out.println(list.get(i));
            }
        } else {
            System.out.println("Using iterator-based loop");
            for (Integer element : list) {
                System.out.println(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

在这个示例中，printList 方法根据列表是否实现了 RandomAccess 接口来选择不同的遍历方式：

• 如果列表实现了 RandomAccess 接口（如 ArrayList），则使用基于索引的循环进行遍历。
• 如果列表没有实现 RandomAccess 接口（如 LinkedList），则使用迭代器进行遍历。

看到这里你肯定想问 基于索引的循环进行遍历和使用迭代器进行遍历 有什么区别？
在 Java 中，基于索引的循环遍历和使用迭代器进行遍历是两种常见的遍历集合的方法。这两种方法在性能、可读性和使用场景上各有优缺点。下面我们详细比较一下这两种遍历方法的区别。

2.1.3.1 基于索引的循环遍历

基于索引的循环遍历通常使用 for 循环，通过索引访问集合中的元素。例如：

List<String> list = Arrays.asList("A", "B", "C", "D");
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}
1
2
3
4

优点

• 直接访问：对于实现了 RandomAccess 接口的集合（如 ArrayList），基于索引的访问是非常高效的，通常是 O(1) 时间复杂度。
• 简洁：代码简洁明了，易于理解。
  缺点
• 性能问题：对于不支持快速随机访问的集合（如 LinkedList），基于索引的访问可能会非常低效，因为每次访问元素都需要从头遍历链表，时间复杂度为 O(n)。
• 不安全的并发修改：在遍历过程中，如果集合被修改（添加或删除元素），会导致 ConcurrentModificationException。

2.1.3.2 使用迭代器进行遍历

使用迭代器进行遍历通常通过 Iterator 或增强的 for-each 循环来实现。例如：

List<String> list = Arrays.asList("A", "B", "C", "D");
for (String element : list) {
    System.out.println(element);
}

// 或者显式使用 Iterator
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}
1
2
3
4
5
6
7
8
9
10

优点

• 适用于所有集合：无论集合是否支持快速随机访问，使用迭代器进行遍历都是高效的。对于链表等不支持随机访问的集合，迭代器的性能优于基于索引的访问。
• 安全的并发修改：迭代器提供了 fail-fast 机制，可以检测到并发修改并抛出 ConcurrentModificationException，从而避免潜在的并发问题。
• 简洁的语法：增强的 for-each 循环语法简洁，易于阅读和维护。
  缺点
• 无法直接访问索引：迭代器不提供直接访问索引的方法。如果需要访问元素的索引，必须额外维护一个计数器。
• 额外的开销：迭代器可能会引入一些额外的开销，尤其是在创建迭代器对象时。

2.1.3.3 性能比较

对于实现了 RandomAccess 接口的集合（如 ArrayList），基于索引的访问通常是最快的，因为它支持常数时间复杂度的随机访问。
对于不支持快速随机访问的集合（如 LinkedList），使用迭代器进行遍历通常更高效，因为链表的随机访问时间复杂度为 O(n)，而迭代器可以通过链表的节点引用进行顺序访问，时间复杂度为 O(1)。

2.1.3.4 选择建议

• 如果你确定集合实现了 RandomAccess 接口（如 ArrayList），并且需要频繁的随机访问，可以使用基于索引的循环进行遍历。
• 如果你不确定集合的实现类型，或者集合可能是链表（如 LinkedList），建议使用迭代器进行遍历，以获得更好的性能和安全性。
• 在并发环境中，如果集合可能在遍历过程中被修改，建议使用迭代器进行遍历，以利用其 fail-fast 机制检测并发修改。

3. 从使用说起

以下是一个简单的示例，展示了 CopyOnWriteArrayList 的基本用法：

import java.util.concurrent.CopyOnWriteArrayList;

public class CopyOnWriteArrayListExample {
    public static void main(String[] args) {
        // 创建一个 CopyOnWriteArrayList 实例
        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();

        // 添加元素
        list.add("A");
        list.add("B");
        list.add("C");

        // 读取元素
        System.out.println("Element at index 1: " + list.get(1));

        // 遍历元素
        System.out.println("Elements in the list:");
        for (String s : list) {
            System.out.println(s);
        }

        // 删除元素
        list.remove("B");

        // 再次遍历元素
        System.out.println("Elements in the list after removal:");
        for (String s : list) {
            System.out.println(s);
        }

        // 使用迭代器遍历元素
        System.out.println("Using iterator to traverse the list:");
        for (String s : list) {
            System.out.println(s);
        }
    }
}

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

3.1 创建 CopyOnWriteArrayList 实例

你可以通过无参构造方法或通过传入一个已有集合来创建 CopyOnWriteArrayList 实例。

3.2 添加元素

使用 add 方法可以向列表中添加元素

3.3 读取元素

使用 get 方法可以读取指定索引位置的元素

3.4 删除元素

使用 remove 方法可以删除指定的元素或指定索引位置的元素

3.5 遍历元素

可以使用增强的 for 循环或迭代器进行遍历

4. CopyOnWriteArrayList 的工作原理是什么？

CopyOnWriteArrayList 基于“写时复制”机制。当进行写操作（如添加、删除、更新）时，它会复制一个新的底层数组，在新的数组上进行修改，然后将新的数组设置为当前数组。读操作则直接访问当前数组，不需要加锁。

5. CopyOnWriteArrayList 适用于哪些场景？

CopyOnWriteArrayList 适用于读操作远多于写操作的场景。由于写操作需要复制数组，开销较大，因此在写操作频繁的场景下性能较差。但在读操作频繁、写操作较少的场景下，CopyOnWriteArrayList 可以提供非常高效的并发读性能。

6. CopyOnWriteArrayList 如何保证线程安全？

CopyOnWriteArrayList 通过在每次写操作时复制底层数组来保证线程安全。由于每次写操作都会创建一个新的数组，读操作始终访问的是一个稳定的、不变的数组，因此不需要加锁。这种机制避免了读写锁的开销，提高了读操作的性能。

7. CopyOnWriteArrayList 的优缺点是什么？

7.1 优点

• 高效的并发读性能：读操作不需要加锁，可以并发执行。
• 线程安全：通过写时复制机制保证线程安全。
• 迭代器安全：迭代过程中不需要担心 ConcurrentModificationException。

7.2 缺点

• 写操作开销大：每次写操作都会复制底层数组，开销较大。
• 内存消耗高：频繁的写操作会导致大量的数组复制，增加内存消耗。
• 不适合写操作频繁的场景：在写操作频繁的场景下性能较差。

8. CopyOnWriteArrayList 与 ArrayList 有什么区别？

• 线程安全性：CopyOnWriteArrayList 是线程安全的，而 ArrayList 不是。
• 写操作：CopyOnWriteArrayList 的写操作会复制底层数组，开销较大；ArrayList 的写操作直接修改底层数组。
• 读操作：CopyOnWriteArrayList 的读操作不需要加锁，可以并发执行；ArrayList 在多线程环境下读操作需要外部同步。
• 迭代器：CopyOnWriteArrayList 的迭代器基于数组快照，不会抛出 ConcurrentModificationException；ArrayList 的迭代器在检测到结构性修改时会抛出 ConcurrentModificationException。

9. 如何在 CopyOnWriteArrayList 中进行批量操作？

由于 CopyOnWriteArrayList 的写操作开销较大，批量操作（如批量添加、删除）可能会导致性能问题。可以通过以下方式优化批量操作：

// 批量添加元素
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
List<String> elementsToAdd = Arrays.asList("A", "B", "C");
list.addAll(elementsToAdd);

// 批量删除元素
List<String> elementsToRemove = Arrays.asList("A", "B");
list.removeAll(elementsToRemove);

1
2
3
4
5
6
7
8
9

系列文章

1.JDK源码阅读之环境搭建

2.JDK源码阅读之目录介绍

3.jdk源码阅读之ArrayList(上)

4.jdk源码阅读之ArrayList(下)

5.jdk源码阅读之HashMap

6.jdk源码阅读之HashMap（下）

7.jdk源码阅读之ConcurrentHashMap(上)

8.jdk源码阅读之ConcurrentHashMap（下）

9.jdk源码阅读之ThreadLocal

10.jdk源码阅读之ReentrantLock

11.jdk源码阅读之CountDownLatch

12.jdk源码阅读之CyclicBarrier

13.jdk源码阅读之Semaphore

14.jdk源码阅读之线程池(上)

15.jdk源码阅读之线程池(下)

16.jdk源码阅读之ArrayBlockingQueue

17.jdk源码阅读之LinkedBlockingQueue