美文网首页
CopyOnWriteArrayList源码解析

CopyOnWriteArrayList源码解析

作者: 小小的coder | 来源:发表于2020-01-14 20:24 被阅读0次

    Java并发包提供了很多线程安全的集合,有了他们的存在,使得我们在多线程开发下,可以和单线程一样去编写代码,大大简化了多线程开发的难度,但是如果不知道其中的原理,可能会引发意想不到的问题,所以知道其中的原理还是很有必要的。

    今天我们来看下Java并发包中提供的线程安全的List,即CopyOnWriteArrayList。

    刚接触CopyOnWriteArrayList的时候,我总感觉这个集合的名称有点奇怪:在写的时候复制?后来才知道它就是在写的时候进行了复制,所以这个命名还是相当严谨的。当然,翻译成 写时复制 会更好一些。

    我们在研究源码的时候,可以带着问题去研究,这样可能效果会更好,把问题一个一个攻破,也更有成就感,所以在这里,我先抛出几个问题:

    1. CopyOnWriteArrayList如何保证线程安全性的。
    2. CopyOnWriteArrayList长度有没有限制。
    3. 为什么说CopyOnWriteArrayList是一个写时复制集合。

    我们先来看下CopyOnWriteArrayList的UML图:

    1698b96d01a09513.png

    主要方法源码解析

    add

    我们可以通过add方法添加一个元素

        public boolean add(E e) {
            //1.获得独占锁
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                Object[] elements = getArray();//2.获得Object[]
                int len = elements.length;//3.获得elements的长度
                Object[] newElements = Arrays.copyOf(elements, len + 1);//4.复制到新的数组
                newElements[len] = e;//5.将add的元素添加到新元素
                setArray(newElements);//6.替换之前的数据
                return true;
            } finally {
                lock.unlock();//7.释放独占锁
            }
        }
    复制代码
    
    
        final Object[] getArray() {
            return array;
        }
    复制代码
    

    当调用add方法,代码会跑到(1)去获得独占锁,因为独占锁的特性,导致如果有多个线程同时跑到(1),只能有一个线程成功获得独占锁,并且执行下面的代码,其余的线程只能在外面等着,直到独占锁被释放。

    线程获得到独占锁后,执行(2),获得array,并且赋值给elements ,(3)获得elements的长度,并且赋值给len,(4)复制elements数组,在此基础上长度+1,赋值给newElements,(5)将我们需要新增的元素添加到newElements,(6)替换之前的数组,最后跑到(7)释放独占锁。

    解析源码后,我们明白了

    1. CopyOnWriteArrayList是如何保证【写】时线程安全的?因为用了ReentrantLock独占锁,保证同时只有一个线程对集合进行修改操作。
    2. 数据是存储在CopyOnWriteArrayList中的array数组中的。
    3. 在添加元素的时候,并不是直接往array里面add元素,而是复制出来了一个新的数组,并且复制出来的数组的长度是 【旧数组的长度+1】,再把旧的数组替换成新的数组,这是尤其需要注意的。

    get

        public E get(int index) {
            return get(getArray(), index);
        }
    复制代码
    
        final Object[] getArray() {
            return array;
        }
    复制代码
    

    我们可以通过调用get方法,来获得指定下标的元素。

    首先获得array,然后获得指定下标的元素,看起来没有任何问题,但是其实这是存在问题的。别忘了,我们现在是多线程的开发环境,不然也没有必要去使用JUC下面的东西了。

    试想这样的场景,当我们获得了array后,把array捧在手心里,如获珍宝。。。由于整个get方法没有独占锁,所以另外一个线程还可以继续执行修改的操作,比如执行了remove的操作,remove和add一样,也会申请独占锁,并且复制出新的数组,删除元素后,替换掉旧的数组。而这一切get方法是不知道的,它不知道array数组已经发生了天翻地覆的变化,它还是傻乎乎的,看着捧在手心里的array。。。这就是弱一致性

    就像微信一样,虽然对方已经把你给删了,但是你不知道,你还是每天打开和她的聊天框,准备说些什么。。。

    set

    我们可以通过set方法修改指定下标元素的值。

        public E set(int index, E element) {
            //(1)获得独占锁
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                Object[] elements = getArray();//(2)获得array
                E oldValue = get(elements, index);//(3)根据下标,获得旧的元素
    
                if (oldValue != element) {//(4)如果旧的元素不等于新的元素
                    int len = elements.length;//(5)获得旧数组的长度
                    Object[] newElements = Arrays.copyOf(elements, len);//(6)复制出新的数组
                    newElements[index] = element;//(7)修改
                    setArray(newElements);//(8)替换
                } else {
                    //(9)为了保证volatile 语义,即使没有修改,也要替换成新的数组
                    // Not quite a no-op; ensures volatile write semantics
                    setArray(elements);
                }
                return oldValue;
            } finally {
                lock.unlock();//(10)释放独占锁
            }
        }
    复制代码
    

    当我们调用set方法后:

    1. 和add方法一样,先获取独占锁,同样的,只有一个线程可以获得独占锁,其他线程会被阻塞。
    2. 获取到独占锁的线程获得array,并且赋值给elements。
    3. 根据下标,获得旧的元素。
    4. 进行一个对比,检查旧的元素是否不等于新的元素,如果成立的话,执行5-8,如果不成立的话,执行9。
    5. 获得旧数组的长度。
    6. 复制出新的数组。
    7. 修改新的数组中指定下标的元素。
    8. 把旧的数组替换掉。
    9. 为了保证volatile语义,即使没有修改,也要替换成新的数组。
    10. 不管是否执行了修改的操作,都会释放独占锁。

    通过源码解析,我们应该更有体会:

    1. 通过独占锁,来保证【写】的线程安全。
    2. 修改操作,实际上操作的是array的一个副本,最后才把array给替换掉。

    remove

    我们可以通过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方法和add,set方法是一样的,第一步还是先获取独占锁,来保证线程安全性,如果要删除的元素是最后一个,则复制出一个长度为【旧数组的长度-1】的新数组,随之替换,这样就巧妙的把最后一个元素给删除了,如果要删除的元素不是最后一个,则分两次复制,随之替换。

    迭代器

    在解析源码前,我们先看下迭代器的基本使用:

    public class Main {public static void main(String[] args) {
            CopyOnWriteArrayList<String> copyOnWriteArrayList=new CopyOnWriteArrayList<>();
            copyOnWriteArrayList.add("Hello");
            copyOnWriteArrayList.add("copyOnWriteArrayList");
            Iterator<String>iterator=copyOnWriteArrayList.iterator();
            while (iterator.hasNext()){
                System.out.println(iterator.next());
            }
        }
    }
    复制代码
    

    运行结果:

    [图片上传失败...(image-95063d-1579004712595)]

    <figcaption style="display: block; text-align: center; font-size: 1rem; line-height: 1.6; color: rgb(144, 144, 144); margin-top: 2px;"></figcaption>

    代码很简单,这里就不再解释了,我们直接来看迭代器的源码:

        public Iterator<E> iterator() {
            return new COWIterator<E>(getArray(), 0);
        }
    复制代码
    
            static final class COWIterator<E> implements ListIterator<E> {
    
            private final Object[] snapshot;
    
            private int cursor;
    
            private COWIterator(Object[] elements, int initialCursor) {
                cursor = initialCursor;
                snapshot = elements;
            }
    
            // 判断是否还有下一个元素
            public boolean hasNext() {
                return cursor < snapshot.length;
            }
    
            //获取下个元素
            @SuppressWarnings("unchecked")
            public E next() {
                if (! hasNext())
                    throw new NoSuchElementException();
                return (E) snapshot[cursor++];
            }
    复制代码
    

    当我们调用iterator方法获取迭代器,内部会调用COWIterator的构造方法,此构造方法有两个参数,第一个参数就是array数组,第二个参数是下标,就是0。随后构造方法中会把array数组赋值给snapshot变量。 snapshot是“快照”的意思,如果Java基础尚可的话,应该知道数组是引用类型,传递的是指针,如果有其他地方修改了数组,这里应该马上就可以反应出来,那为什么又会是snapshot这样的命名呢?没错,如果其他线程没有对CopyOnWriteArrayList进行增删改的操作,那么snapshot就是本身的array,但是如果其他线程对CopyOnWriteArrayList进行了增删改的操作,旧的数组会被新的数组给替换掉,但是snapshot还是原来旧的数组的引用。也就是说 当我们使用迭代器便利CopyOnWriteArrayList的时候,不能保证拿到的数据是最新的,这也是弱一致性问题。

    什么?你不信?那我们通过一个demo来证实下:

      public static void main(String[] args) throws InterruptedException {
            CopyOnWriteArrayList<String> copyOnWriteArrayList=new CopyOnWriteArrayList<>();
            copyOnWriteArrayList.add("Hello");
            copyOnWriteArrayList.add("CopyOnWriteArrayList");
            copyOnWriteArrayList.add("2019");
            copyOnWriteArrayList.add("good good study");
            copyOnWriteArrayList.add("day day up");
            new Thread(()->{
                copyOnWriteArrayList.remove(1);
                copyOnWriteArrayList.remove(3);
            }).start();
            TimeUnit.SECONDS.sleep(3);
            Iterator<String> iterator = copyOnWriteArrayList.iterator();
            while (iterator.hasNext()) {
                System.out.println(iterator.next());
            }
        }
    复制代码
    

    运行结果:

    [图片上传失败...(image-69eb8d-1579004712594)]

    <figcaption style="display: block; text-align: center; font-size: 1rem; line-height: 1.6; color: rgb(144, 144, 144); margin-top: 2px;"></figcaption>

    这没问题把,我们先是往list里面add了点数据,然后开一个线程,在线程里面删除一些元素,睡3秒是为了保证线程运行完毕。然后获取迭代器,遍历元素,发现被remove的元素没有被打印出来。

    然后我们换一种写法:

       public static void main(String[] args) throws InterruptedException {
            CopyOnWriteArrayList<String> copyOnWriteArrayList=new CopyOnWriteArrayList<>();
            copyOnWriteArrayList.add("Hello");
            copyOnWriteArrayList.add("CopyOnWriteArrayList");
            copyOnWriteArrayList.add("2019");
            copyOnWriteArrayList.add("good good study");
            copyOnWriteArrayList.add("day day up");
            Iterator<String> iterator = copyOnWriteArrayList.iterator();
            new Thread(()->{
                copyOnWriteArrayList.remove(1);
                copyOnWriteArrayList.remove(3);
            }).start();
            while (iterator.hasNext()) {
                System.out.println(iterator.next());
            }
        }
    复制代码
    

    这次我们改变了代码的顺序,先是获取迭代器,然后是执行删除线程的操作,最后遍历迭代器。 运行结果:

    [1D~XKU28O6X{A]XM}S3_MS.png

    可以看到被删除的元素,还是打印出来了。

    如果我们没有分析源码,不知道其中的原理,不知道弱一致性,当在多线程中用到CopyOnWriteArrayList的时候,可能会痛不欲生,想砸电脑,不知道为什么获取的数据有时候就不是正确的数据,而有时候又是。所以探究原理,还是挺有必要的,不管是通过源码分析,还是通过看博客,甚至是直接看JDK中的注释,都是可以的。

    在Java并发包提供的集合中,CopyOnWriteArrayList应该是最简单的一个,希望通过源码分析,让大家有一个信心,原来JDK源码也是可以读懂的。

    原文地址:https://juejin.im/post/5c8e3b17f265da682132c5c4

    相关文章

      网友评论

          本文标题:CopyOnWriteArrayList源码解析

          本文链接:https://www.haomeiwen.com/subject/vooaactx.html