CopyOnWriteArrayList的add方法

Spring Wu 503 2021-02-03

源码分析

是JUC包下提供的一个线程安全的ArrayList容器。使用了ReetrantLock来保证线程安全。

  • add(E e) 往集合末尾添加一个元素
    public boolean add(E e) {
        // 使用juc的可重入锁保证线程安全
        // 其中lock在CopyOnWriteArrayList的定义:final transient ReentrantLock lock = new ReentrantLock();
        final ReentrantLock lock = this.lock;
        // 线程得到锁,同时只能有一个线程操作
        lock.lock();
        try {
            // 获取当前的数组,和ArrayList一样。底层就是一个数组。
            Object[] elements = getArray();
            // 得到数组的长度
            int len = elements.length;
            // 直接copy出一个新数组,传入的参数是旧数组和新数组的容量。返回一个新数组,新数组数据就是就数组的数组,并且新数组的容量+1
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            // 往elements.length添加一个新元素。也就是末尾添加一个元素。
            newElements[len] = e;
            // 用新数组覆盖旧数组
            setArray(newElements);
            // 添加成功,返回true
            return true;
        } finally {
            // 当前线程操作完成,释放锁。
            lock.unlock();
        }
    }
  • add(int index, E element) 往集合指定位置添加一个元素
    public void add(int index, E element) {
        // 上面add(E e)一样的逻辑就不再赘述
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            // 判断插入的位置是否合法。
            if (index > len || index < 0)
                throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len);
            Object[] newElements;
            int numMoved = len - index;
            // 如果插入的是数组的最后一个位置,直接copy一个新数组,并且新数组的容量+1
            if (numMoved == 0)
                newElements = Arrays.copyOf(elements, len + 1);
            else {
                // 如果插入的不是最后一个位置,则new一个新数组,新数组的容量在原来的旧数组容量上+1
                newElements = new Object[len + 1];
                // 把旧数组直接拷贝到空的新数组中。
                // System.arraycopy参数解释:
                // 第一个参数是需要被拷贝的旧数组,第二个参数从旧数组的什么位置开始拷贝,
                // 第三个参数是拷贝到的目标数组,第四个参数是从旧数组的第几个参数开始拷贝,
                // 第五个参数是从旧数组拷贝多少个元素到新数组。
                // 第一次拷贝:把旧数组拷贝到新数组,把要插入的位置的index之前的数据拷贝到新数组。
                System.arraycopy(elements, 0, newElements, 0, index);
                // 第二次拷贝:把旧数组从要插入的位置开始拷贝到新数组要插入的位置+1开始,把剩下的旧数组数据拷贝到新数组。
                // 这里index+1就在新数组中预留了一个插入位置。
                System.arraycopy(elements, index, newElements, index + 1, numMoved);
            }
            // 往index的位置插入元素
            newElements[index] = element;
            // 覆盖旧数组
            setArray(newElements);
        } finally {
            // 线程执行完毕,解锁
            lock.unlock();
        }
    }

在看源码的过程中,产生了如下的疑问:

  • 为什么没有像ArrayList一样的1.5倍扩容机制?

想了一下,本身add就已经复制整个旧数组到新数组了,复制的时候把新数组的容量+1。对比于ArrayList并不是每次add都直接复制整个数组,而是给了一个初始容量,默认初始容量为10。当判断插入后容量比当前容量大时,才会进行扩容操作,扩容的时候才会复制整个数组。区别就是ArrayList不支持两个线程同时增加或删除。比如以下操作:

    public static void main(String[] args) {

        final List<Integer> list = Arrays.asList(1, 2, 3);

        // Thread1往list中增加元素
        new Thread(() -> {
            list.forEach(i -> {
                list.add(i + 1);
            });
        }, "Thread1").start();

        // Thread2同时在list中删除元素
        new Thread(() -> {
            list.forEach(i -> {
                list.remove(i);
            });
        }, "Thread2").start();
    }

运行后出现以下异常:

Exception in thread "Thread-0" Exception in thread "Thread-1" java.lang.UnsupportedOperationException
	at java.util.AbstractList.add(AbstractList.java:148)
	at java.util.AbstractList.add(AbstractList.java:108)
	at io.wooo.practice.studyplan.juc.SynchronizedDemo.lambda$null$0(SynchronizedDemo.java:22)
	at java.util.Arrays$ArrayList.forEach(Arrays.java:3880)
	at io.wooo.practice.studyplan.juc.SynchronizedDemo.lambda$main$1(SynchronizedDemo.java:21)
	at java.lang.Thread.run(Thread.java:748)
java.lang.UnsupportedOperationException
	at java.util.AbstractList.remove(AbstractList.java:161)
	at java.util.AbstractList$Itr.remove(AbstractList.java:374)
	at java.util.AbstractCollection.remove(AbstractCollection.java:293)
	at io.wooo.practice.studyplan.juc.SynchronizedDemo.lambda$null$2(SynchronizedDemo.java:28)
	at java.util.Arrays$ArrayList.forEach(Arrays.java:3880)
	at io.wooo.practice.studyplan.juc.SynchronizedDemo.lambda$main$3(SynchronizedDemo.java:27)
	at java.lang.Thread.run(Thread.java:748)

如果使用CopyOnWriteArrayList就不会出现这个问题:

   public static void main(String[] args) {

        final List<Integer> initList = Arrays.asList(1, 2, 3);

        List<Integer> list = new CopyOnWriteArrayList(initList);
        
        // Thread1往list中增加元素
        new Thread(() -> {
            list.forEach(i -> {
                list.add(i + 1);
            });
        }, "Thread1").start();

        // Thread2同时在list中删除元素
        new Thread(() -> {
            list.forEach(i -> {
                list.remove(i);
            });
        }, "Thread2").start();
    }

对于这个疑问,这篇文章写得不错CopyOnWriteArrayList 的set为什么要复制?扩容为什么一个一个来,而不是1.5倍

  • 优点
  1. 当读多写少的时候,读的速度快,毕竟读和写是在不同的对象中进行的。相当于”读写分离“。写是copy了一个新数组来写入数据,读的是旧数组。
  2. 并且在多个线程同时操作(添加、删除)同一个CopyOnWriteArrayList对象时,不会出现ConcurrentModificationExceptionUnsupportedOperationException的错误。
  • 缺点
  1. 因为每次写入都需要重新copy一个新数组出来,所以相当于写入时,一个CopyOnWriteArrayList中存储了两个数组。内存压力较大,
  2. 正是由于”读写分离“,虽然可以保证多个线程可以同时操作。而且互补影响,但是,缺丢失了实时性。因为读的时候与写的时候是不同的数组。
  3. 因为每次写都要copy新数组,所以,写的时候性能极差。