Java 中 CopyOnWriteArrayList 的底层数据结构及相关分析

Java 中 CopyOnWriteArrayList 的底层数据结构及相关分析

1. CopyOnWriteArrayList 简介

CopyOnWriteArrayList 是 Java 中的一个线程安全的 List 实现，属于 java.util.concurrent 包。其核心特点是在写操作时不会直接修改原数组，而是创建一个新数组进行更新，从而避免并发修改时的冲突。

2. 底层数据结构

CopyOnWriteArrayList 底层使用 数组（Object[] array）来存储数据，和 ArrayList 类似。但 CopyOnWriteArrayList 的核心区别在于它的 写时复制（Copy-On-Write）机制。

3. 实现原理

3.1 读操作

读操作（get、size、contains 等）不会加锁，直接读取 array 数组的数据。因此，多个线程可以并发读取，而不会产生数据一致性问题。

3.2 写操作

写操作（add、set、remove 等）会创建新数组，避免直接修改原数组，从而保证线程安全。

示例：add(E e) 方法的实现逻辑如下：

1. 获取当前数组 Object[] oldArray。
2. 复制原数组到一个新的数组 Object[] newArray，并将新元素添加到新数组。
3. 使用 this.array = newArray 替换旧数组。

代码示例：

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock(); // 加锁确保线程安全
    try {
        Object[] oldArray = array;
        int len = oldArray.length;
        Object[] newArray = Arrays.copyOf(oldArray, len + 1);
        newArray[len] = e;
        array = newArray; // 替换原数组
        return true;
    } finally {
        lock.unlock(); // 释放锁
    }
}

4. 适用场景

CopyOnWriteArrayList 适用于 读多写少 的并发场景，例如：

• 缓存（Cache）：频繁读取数据，但更新较少。
• 订阅者列表：多个线程读取订阅列表，但订阅变化不频繁。
• 黑名单、白名单：高频查询，低频更新。

不适用于 高并发写入场景，因为每次写操作都会创建新的数组，成本较高。

5. 优缺点分析

5.1 优点

• 线程安全：无锁读取，写时复制避免数据竞争。
• 一致性保证：读操作永远不会阻塞。
• 弱一致性：读取时看到的是旧数据，而不会因写操作失败。

5.2 缺点

• 写操作开销大：每次修改都复制整个数组，消耗内存和 CPU。
• 不适用于大数据量：数组复制的时间复杂度为 O(n)。

6. 替代方案

如果 CopyOnWriteArrayList 不适用于某些高并发场景，可以考虑以下替代方案：

7. 使用示例

7.1 基本用法

import java.util.concurrent.CopyOnWriteArrayList;

public class CopyOnWriteArrayListDemo {
    public static void main(String[] args) {
        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        
        System.out.println("List: " + list);
        list.remove("B");
        System.out.println("After removal: " + list);
    }
}

7.2 并发环境下的使用

import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class CopyOnWriteExample {
    public static void main(String[] args) {
        CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
        ExecutorService executor = Executors.newFixedThreadPool(3);

        Runnable writer = () -> {
            for (int i = 0; i < 5; i++) {
                list.add(i);
                System.out.println(Thread.currentThread().getName() + " added: " + i);
            }
        };

        Runnable reader = () -> {
            for (Integer num : list) {
                System.out.println(Thread.currentThread().getName() + " read: " + num);
            }
        };

        executor.execute(writer);
        executor.execute(reader);
        executor.shutdown();
    }
}

8. 总结

CopyOnWriteArrayList 在 读多写少 场景下是一个优秀的选择。如果写操作频繁，可以考虑 ConcurrentHashMap 或 ConcurrentLinkedQueue。