CopyOnWriteArrayList介绍和使用

时间:2024-03-13 13:22:44

1. CopyOnWriteArrayList是什么

CopyOnWriteArrayList 是 Java.util.concurrent 包中的一个线程安全的 List 实现类。它通过在修改操作时创建底层数组的副本来实现线程安全,从而保证了并发访问的一致性。它适用于读操作频繁、写操作较少的场景。

2. CopyOnWriteArrayList特性

  1. 线程安全性:
    CopyOnWriteArrayList 是线程安全的,可以在多线程环境下并发访问而无需额外的同步措施。它通过在修改操作(如添加、修改、删除元素)时创建底层数组的副本,并在副本上进行修改操作,以确保原始数组的线程安全性。这样,读取操作可以在不阻塞的情况下同时进行,不会影响其他线程的读取操作。
  2. 内部实现:
    CopyOnWriteArrayList 内部使用一个可变数组来存储元素。在进行修改操作时,会创建一个新的数组副本,并将修改操作应用于副本,然后将副本替换原始数组。这种写时复制的机制保证了修改操作的线程安全性,但也带来了一些额外的开销和内存消耗。
  3. 迭代器一致性:
    CopyOnWriteArrayList 提供的迭代器是弱一致性的。即,在迭代过程中,如果有其他线程对列表进行了修改,迭代器不会抛出 ConcurrentModificationException 异常,而是仍然基于迭代器创建时的快照进行迭代。这意味着迭代器不会遇到并发修改的异常,但可能会遇到迭代过程中数据的变化。
  4. 适用场景:
    CopyOnWriteArrayList 适用于读操作频繁、写操作较少的场景。由于每次写操作都会创建底层数组的副本,因此写操作的开销较大,不适合频繁的修改操作。但对于读操作,由于读取操作不需要额外的同步措施,所以可以在并发访问下获得较好的性能。

需要注意的是,由于 CopyOnWriteArrayList 每次修改操作都会创建副本,因此它的内存消耗较大。因此,对于存储大量数据的情况,应谨慎使用,以免导致内存占用过高。

CopyOnWriteArrayList 提供了一种线程安全的 List 实现,适用于读操作频繁、写操作较少的场景,具有良好的并发性能和一致性保证。

3. CopyOnWriteArrayList 的线程安全原理

CopyOnWriteArrayList 的线程安全原理是通过写时复制(Copy-On-Write)的机制实现的。

当进行修改操作(如添加、修改、删除元素)时,CopyOnWriteArrayList 会创建一个底层数组的副本,并在副本上进行修改操作,而不是直接在原始数组上进行修改。这样做的目的是保证并发访问的线程安全性。

  1. 在读取操作时,多个线程可以同时进行读取,而不需要额外的同步措施。因为读取操作直接读取当前的数组,不会受到其他线程修改操作的影响。
  2. 在写操作时,CopyOnWriteArrayList 会创建一个新的数组副本,并在副本上进行修改操作。这样做的好处是,写操作不会影响其他线程的读取操作。
  3. 当修改操作完成后,CopyOnWriteArrayList 会将新的数组副本替换原始数组。这个替换操作是原子的,确保了新的数组副本对其他线程的可见性。

通过使用写时复制的机制,CopyOnWriteArrayList 实现了线程安全。每个线程在进行修改操作时都会操作自己的副本,不会对其他线程的读取操作造成影响。这样就避免了传统的同步机制(如锁)带来的竞争和阻塞,提高了并发性能。

4. 源码解析

4.1. add方法

public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;

    /** The lock protecting all mutators */
    // 可重入锁
    final transient ReentrantLock lock = new ReentrantLock();

    /** The array, accessed only via getArray/setArray. */
    // volatile 关键字修饰
    private transient volatile Object[] array;

    /**
     * Gets the array.  Non-private so as to also be accessible
     * from CopyOnWriteArraySet class.
     */
    // 获取数组
    final Object[] getArray() {
        return array;
    }

    /**
     * Sets the array.
     */
    // 设置数组
    final void setArray(Object[] a) {
        array = a;
    }


    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        // 加锁
        lock.lock();
        try {
            // 获取原数组
            Object[] elements = getArray();
            // 原数组长度
            int len = elements.length;
            // 拷贝原数组到新数组,且新数组长度=未原数组长度+1,因为要新增一个元素
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            // 新增元素放在数组最后一位
            newElements[len] = e;
            // 新数组替换掉原来的数组
            setArray(newElements);
            return true;
        } finally {
            // 解锁
            lock.unlock();
        }
    }

    /**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        final ReentrantLock lock = this.lock;
        // 加锁
        lock.lock();
        try {
            // 获取原数组
            Object[] elements = getArray();
            // 数组长度
            int len = elements.length;
            // 插入的位置大于原数组长度或者小于0就报错
            if (index > len || index < 0)
                throw new IndexOutOfBoundsException("Index: "+index+
            // 新建数组                                        ", Size: "+len);
            Object[] newElements;
            // 原数组长度 - 插入位置索引
            int numMoved = len - index;
            // 如果原数组长度 - 插入位置索引 = 0
            if (numMoved == 0)
                // 表示插入的是在最尾部,新数组等于元数组,然后长度加一
                newElements = Arrays.copyOf(elements, len + 1);
            else {
                // 否则的话表示 插入在数组中间位置,就需要两次拷贝数组
                // 新数组长度等于元数组加一
                newElements = new Object[len + 1];
                // 第一次拷贝数组 从0到index。
                System.arraycopy(elements, 0, newElements, 0, index);
                // 第二次拷贝数组 从index+1到末尾。
                System.arraycopy(elements, index, newElements, index + 1,
                                 numMoved);
            }
            // 给index索引位置赋值
            newElements[index] = element;
            // 新数组替换掉原来的数组 
            setArray(newElements);
        } finally {
            // 解锁
            lock.unlock();
        }
    }
}

4.2. System.arraycopy()介绍

System.arraycopy() 是Java中的一个方法,用于将一个数组中的元素复制到另一个数组中。它的语法如下:

System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)

参数说明:

  • src:源数组,即要复制的元素来源。
  • srcPos:源数组中要复制的起始位置。
  • dest:目标数组,即要将元素复制到的数组。
  • destPos:目标数组中开始存放复制元素的起始位置。
  • length:要复制的元素个数。

所以,System.arraycopy(elements, 0, newElements, 0, index) 的意思是将 elements 数组中从索引 0 开始的 index 个元素复制到 newElements 数组中,复制的起始位置也从目标数组的索引 0 开始。这个方法可以用来执行数组的部分复制或者数组的重排操作。

具体例子:

public static void main(String[] args) {
    Object[] elements = {1, 2, 3, 4, 5};
    int index = 3;
    int len = elements.length;
    int numMoved = len - index;
    Object[] newElements = new Object[len + 1];
    System.arraycopy(elements, 0, newElements, 0, index);
    System.out.println("第1次拷贝结果:" + Arrays.toString(newElements));
    System.arraycopy(elements, index, newElements, index + 1, numMoved);
    System.out.println("第2次拷贝结果:" + Arrays.toString(newElements));
}

控制台输出结果

img

4.3. remove方法

/**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).  Returns the element that was removed from the list.
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
public E remove(int index) {
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lock();
    try {
        // 获取原数组
        Object[] elements = getArray();
        // 原数组长度
        int len = elements.length;
        // 先得index位置的值
        E oldValue = get(elements, index);
        // 原数组长度 - index - 1
        int numMoved = len - index - 1;
        // 如果要删除的数据正好是数组的尾部,直接删除
        if (numMoved == 0)
            // 复制原数组,数组长度少1
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            // 如果删除的数据在数组的中间,分三步走
            // 1. 设置新数组的长度减一,因为是减少一个元素
            // 2. 从 0 拷贝到数组新位置
            // 3. 从新位置拷贝到数组尾部
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index,
                         numMoved);
            // 新数组替换掉原来的数组 
            setArray(newElements);
        }
        return oldValue;
    } finally {
        // 解锁
        lock.unlock();
    }
}

4.4. 总结

通过分析源码可以看出,添加、删除都是先复制原数组到新数组,然后再新数组中操作新增、删除元素,最后再替换原来的数组,再解锁。

步骤如下:

  1. 加锁
  2. 从原数组中拷贝出新数组
  3. 在新数组上进行操作,并把新数组赋值给数组容器
  4. 解锁