CopyOnWriteArrayList 源码分析

CopyOnWriteArrayList 源码分析

1. 概述

CopyOnWriteArrayList 是 Java 中的一个线程安全的 List 实现，它使用了“写时复制”策略来保证线程安全。这意味着每次对列表进行修改（如添加、删除或更新元素）时，它都会复制原列表并在副本上进行操作，而不是直接在原列表上进行修改。这样可以确保多个线程能够安全地并发读取列表，而无需进行同步。

CopyOnWriteArrayList 的设计旨在优化读操作，适用于读多写少的场景，避免了传统同步方法（如 synchronized 或 ReentrantLock）的性能瓶颈。

---

2. 主要成员变量

private transient volatile Object[] array;

• array：CopyOnWriteArrayList 使用一个 Object[] 数组来存储元素。这个数组是 volatile 的，意味着对数组的任何修改都会立即对其他线程可见。

---

3. 构造方法

CopyOnWriteArrayList 提供了多个构造方法，其中最常用的是：

public CopyOnWriteArrayList() {
    this.array = new Object[0];
}

public CopyOnWriteArrayList(Collection<? extends E> c) {
    array = c.toArray();
    if ((length = array.length) != 0) {
        // do something
    }
}

• 无参构造：初始化为一个空数组。
• 传入集合构造：将传入集合的元素复制到 array 数组中。

---

4. 核心方法分析

4.1 读操作：get

public E get(int index) {
    return (E) array[index];
}

• get 方法直接通过索引访问 array 数组。
• 由于 array 是 volatile 的，因此读取操作本身是线程安全的。

4.2 写操作：add

CopyOnWriteArrayList 的关键特性在于它的“写时复制”策略。当执行修改操作时，都会对原数组进行复制，然后在副本上执行修改，最后将副本替换原数组。

public boolean add(E e) {
    final Object[] snapshot = array;
    final int len = snapshot.length;
    final Object[] newArray = Arrays.copyOf(snapshot, len + 1);
    newArray[len] = e;
    array = newArray;
    return true;
}

• 步骤：
  1. 获取当前数组的快照 snapshot。
  2. 通过 Arrays.copyOf 创建一个新的数组 newArray，其大小比原数组多 1。
  3. 将新的元素 e 添加到新的数组中。
  4. 将原数组引用更新为 newArray。
• 特点：
  • 由于修改操作是基于副本进行的，整个操作是原子性的，不会影响到其他线程的读取。
  • 这种写时复制的策略意味着每次写操作的时间复杂度为 O(n)，其中 n 是当前列表的长度。

4.3 批量操作：addAll

public boolean addAll(Collection<? extends E> c) {
    final Object[] snapshot = array;
    final int len = snapshot.length;
    final int newLength = len + c.size();
    final Object[] newArray = Arrays.copyOf(snapshot, newLength);
    int i = len;
    for (E e : c) {
        newArray[i++] = e;
    }
    array = newArray;
    return true;
}

• 步骤：
  1. 创建一个新数组 newArray，它的长度是原数组长度加上传入集合的大小。
  2. 将原数组和新集合的元素复制到新数组中。
  3. 将原数组引用更新为新的数组。
• 特点：
  • 这个操作的时间复杂度是 O(n + m)，其中 n 是当前数组的大小，m 是传入集合的大小。
  • 由于每次 addAll 操作都会创建一个新的数组，因此它同样需要 O(n) 的时间来复制数组。

4.4 删除操作：remove

public boolean remove(Object o) {
    final Object[] snapshot = array;
    final int len = snapshot.length;
    int index = indexOf(o);
    if (index == -1) {
        return false;
    }
    final Object[] newArray = new Object[len - 1];
    System.arraycopy(snapshot, 0, newArray, 0, index);
    System.arraycopy(snapshot, index + 1, newArray, index, len - index - 1);
    array = newArray;
    return true;
}

• 步骤：
  1. 查找目标元素的索引，如果找不到则返回 false。
  2. 创建一个新的数组 newArray，它的长度比原数组少 1。
  3. 使用 System.arraycopy 将原数组中目标元素前后的部分复制到新数组中。
  4. 更新 array 引用为新的数组。
• 特点：
  • 删除操作的时间复杂度是 O(n)，因为需要在新数组中复制元素。

---

5. 性能特性

1. 读操作：

   • CopyOnWriteArrayList 对读操作进行了优化，因为它不需要同步，直接访问内存中的数组即可，读操作是 O(1) 的。

2. 写操作：

   • 写操作（如 add、remove 等）会涉及到数组的复制，因此它们的时间复杂度是 O(n)。
   • 虽然写操作的时间复杂度较高，但在多线程环境下，多个线程可以并发进行读操作而不会发生冲突。

3. 适用场景：

   • 适用于读多写少的场景，例如缓存系统、事件监听器等，能够高效地支持并发读取。

---

总结

• CopyOnWriteArrayList 通过使用写时复制的策略，确保了并发环境下的线程安全，特别适合于读操作远多于写操作的场景。
• 每次修改操作都涉及到数组的复制，因此它的写操作开销较高，适合写入较少的场景。
• 它的读操作非常高效，因为没有使用同步机制，避免了锁的开销。