精读JDK源码之CopyOnWriteArrayList

大家都知道ArrayList线程安全的,推荐我们自己加或者使用Collections.synchronizedList方法,其实JDK还提供了一种线程安全的List-CopyOnWriteArrayList,它的特征如下:

1、 线程安全
2、 通过锁+数组拷贝+volatile关键字保证了线程安全
3、 每次数组操作,都会把数组拷贝一份出来,在新数组上进行操作,操作成功之后再赋值回去

整体思路

从整体讲,CopyOnWriteArrayList数据结构和ArrayList是一致的,底层是个数组

CopyOnWriteArrayList对数组进行操作时,会进行一下操作
1、加锁
2、从原数组中拷贝出新数组
3、在新数组上进行操作,并把新数组赋值给数组容器
4、解锁

另外CopyOnWriteArrayList底层数组采用volatile修饰,保证了可见性

不知道看到这里你是否和我有同样的疑问,既然加锁了,为什么还要加volatile关键字?

读到后面发现CopyOnWriteArrayList读操作并不会加锁,也就是不同线程操作可能拿到不同的锁(或者说有的不拿到锁),也就没法保证happens-before原则,volatile可以保证happens-before语意

新增

新增有很多种情况,比如新增到数组尾部、新增到数组某一个索引位置、批量新增等

首先是新增到数组尾部,源码如下:

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();
        }
    }
复制代码

可以看到,整个过程可以分为五步,加锁、新建数组拷贝原来数组、插入数据、给原来数组赋值、解锁

不知道看到这里你是否和我有同样的疑问,为什么要拷贝一份数据出来呢?

这里其实是和volatile有关,因为volatile修饰的是数组,线程的工作内存只拷贝了数组的引用,如果只改变数组值,无法触发可见性

再看指定位置插入数据

public void add(int index, E element) {
        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;
            if (numMoved == 0)
                newElements = Arrays.copyOf(elements, len + 1);
            else {
                newElements = new Object[len + 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index, newElements, index + 1,
                                 numMoved);
            }
            newElements[index] = element;
            setArray(newElements);
        } finally {
            lock.unlock();
        }
    }
复制代码

可以看到,如果插入位置正好是末尾,只需要拷贝一次。否则,会进行两次拷贝

删除

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();
        }
    }
复制代码

可以看得出,删除操作与新增操作类似。分为四步

1、加锁
2、判断索引位置,选择不同策略拷贝数组
3、给原来数组赋值
4、解锁

批量删除

源码如下:

public boolean removeAll(Collection<?> c) {
        if (c == null) throw new NullPointerException();
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            if (len != 0) {
                // temp array holds those elements we know we want to keep
                int newlen = 0;
                Object[] temp = new Object[len];
                for (int i = 0; i < len; ++i) {
                    Object element = elements[i];
                    if (!c.contains(element))
                        temp[newlen++] = element;
                }
                if (newlen != len) {
                    setArray(Arrays.copyOf(temp, newlen));
                    return true;
                }
            }
            return false;
        } finally {
            lock.unlock();
        }
    }
复制代码

从源码中可以看到,批量删除并不会直接对数组中得到元素挨个删除,而是先对数组中值进行循环判断,把不需要删除的放到临时数组中,最后临时数组中的数据就是我们不需要删除的数据(个人觉得这是一种空间时间的思想,因为删除操作需要o(n)的时间复杂度)

迭代

CopyOnWriteArrayList,数组原值(包括增加和删除)被改变也不会抛出ConcurrentModificationException异常,因为其迭代器持有的老数组的引用,每次都是拷贝出新数组,不会影响老数组。

原文 

https://juejin.im/post/5dd025af5188252ce1710165

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 精读JDK源码之CopyOnWriteArrayList

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址