乐趣区

关于java:写时复制集合-CopyOnWriteArrayList

前言

JUC 上面还有一个系列的类,都是 CopyOnWriteXXX,意思是写时复制,这个到底是怎么回事?那就以 CopyOnWriteArrayList 为切入点,一起理解写时复制是怎么回事?

公众号:『刘志航』,记录工作学习中的技术、开发及源码笔记;时不时分享一些生存中的见闻感悟。欢送大佬来领导!

介绍

ArrayList 的一个线程平安的变体,其中所有可变操作(add、set 等等)都是通过对底层数组进行一次新的复制来实现的。

像名字一样,每次进行操作的时候,都会进行一次复制,当然会有很大的性能耗费,然而在某些应用场景下,又会进步性能。具体是怎么操作的,那就一步一步浏览源码,而后再做总结演绎。

根本应用

public class CopyOnWriteArrayListTest {public static void main(String[] args) {CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();

        // 增加元素
        list.add("liuzhihang");

        // 移除元素
        list.remove("liuzhihang");

        // 查看元素
        String value0 = list.get(0);

        // 遍历
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {String next = iterator.next();
        }

    }
}

问题疑难

  1. 为什么要叫写时复制汇合?
  2. CopyOnWriteArrayList 实现原理是什么?
  3. CopyOnWriteArrayList 和 ArrayList 有什么区别?
  4. CopyOnWriteArrayList 复制是怎么进行复制的?

源码剖析

根本构造

参数介绍

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

    /** 数据有变动时应用 */
    final transient ReentrantLock lock = new ReentrantLock();

    /** 数组 只能通过 getArray/setArray 拜访 */
    private transient volatile Object[] array;

    final Object[] getArray() {return array;}
    // 将数组指向传入的新数组
    final void setArray(Object[] a) {array = a;}
}

通过参数能够理解到以下内容:

  1. 基于数组实现;
  2. 应用了 ReentrantLock 互斥锁。

构造函数

public CopyOnWriteArrayList() {setArray(new Object[0]);
}

在初始化 CopyOnWriteArrayList 时,就是创立了一个 Object 的数组。

add

public boolean add(E e) {
    // 加锁
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        // 获取以后数组
        Object[] elements = getArray();
        int len = elements.length;
        // 创立一个新数组,并将原数组数据复制到新数组
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 增加的新元素到数组尾部
        newElements[len] = e;
        // 将数组指向新数组
        setArray(newElements);
        return true;
    } finally {lock.unlock();
    }
}

add 办法逻辑很简略:

  1. 通过加互斥锁(ReentrantLock)从而保障在写的时候只有一个线程能够写。
  2. 新增元素时,先应用 Arrays.copyOf(elements, len + 1) 复制出一个长度 +1 的新数组。
  3. 增加元素到新数组。
  4. 而后再将原数组对象指向新数组。

画图如下:

remove

public E remove(int index) {
    // 加锁
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        // 原数组
        Object[] elements = getArray();
        int len = elements.length;
        // 移除的值
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        if (numMoved == 0)
            // 如果移除最初一个元素
            // 间接复制后面的元素即可
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            // 移除两头的元素,进行两次复制
            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();
    }
}

remove 办法绝对多了一些判断:

  1. 通过加互斥锁(ReentrantLock)从而保障在写的时候只有一个线程能够移除元素。
  2. 如果移除的是最初一个元素,则间接复制后面的元素到新数组,并指向新数组即可。
  3. 如果移除的是两头的元素,则须要进行两次复制,而后指向新数组。

画图如下:

get

public E get(int index) {return get(getArray(), index);
}

get 办法能够看出:

  1. 获取元素并没有进行加锁。
  2. 从原数组获取的元素。

所以并发状况下,并不能保障很及时的读取的刚插入或者移除的元素。

数组复制

通过浏览 add 和 remove 相干代码,能够看到在数组复制时应用了 Arrays.copyOfSystem.arraycopy,这相当于一个优化方面吧。

毕竟数组复制总不能把原数组遍历一遍,挨着赋值到新数组外面吧。

那接下来看一下外部是如何实现的:

public class Arrays {
    
    // 其余办法省略 ...
    
    /**
     * original 要复制的数组
     * newLength 新数组的长度
     */
    public static <T> T[] copyOf(T[] original, int newLength) {return (T[]) copyOf(original, newLength, original.getClass());
    }

    /**
     * original 要复制的数组
     * newLength 新数组的长度
     */
    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        // 创立一个新数组,长度是指定的长度
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            // 创立具备指定的组件类型和长度的新数组
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        
        // 调用 System.arraycopy 复制数组
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }
}

通过浏览 Arrays.copyOf 相干源码,发现其实 Arrays.copyOf 底层也是调用的 System.arraycopy

public final class System {

    // 其余办法省略 ...

    /**
     * src 源数组
     * srcPos 源数组起始地位
     * dest 指标数组
     * destPos 指标数组的起始地位
     * length 要复制的元素数量
     */
    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);
}

能够看到 System.arraycopy 是一个 native 办法,这个是 JVM 外部实现的,具体能够浏览相干材料。而应用这种形式要比 for 循环和 clone 要高效很多。

总结

Q&A

Q: 为什么要叫写时复制汇合?

A: 因为在 add、remove 操作时会复制进去一个新数组。

Q: CopyOnWriteArrayList 实现原理是什么?

A: 在 add、remove 操作时会进行加锁,而后复制进去一个新数组,操作的都是新数组,而此时原数组是能够提供查问的。当操作完结之后,会将对象指针指向新数组。

Q: CopyOnWriteArrayList 和 ArrayList 有什么区别?

A: CopyOnWriteArrayList 在读多写少的场景下能够提高效率,而 ArrayList 只是一般数组汇合,并不适用于并发场景,而如果对 ArrayList 加锁,则会影响一部分性能。

同样对 CopyOnWriteArrayList 而言,仅能保障最终一致性。因为刚写入的数据,是写到的复制的数组中,此时并不能立刻查问到。如果要保障实时性能够尝试应用 Collections.synchronizedList 或者加锁等形式。

Q: CopyOnWriteArrayList 复制是怎么进行复制的?

A: 外部应用的是本地办法 System.arraycopy 进行数组的复制。

结束语

通过浏览 CopyOnWriteArrayList 源码,理解到写时复制是的原理。同时理解到能够应用 System.arraycopy 的形式进步数组复制的效率。

同样 CopyOnWriteArrayList 适宜读多写少的场景,满足最终一致性,然而并不能保证数据批改及时查问到。

退出移动版