美文网首页
CopyOnWriteArrayList源码解析——JDK1.8

CopyOnWriteArrayList源码解析——JDK1.8

作者: SinX竟然被占用了 | 来源:发表于2017-09-07 21:54 被阅读0次

    参考:http://www.cnblogs.com/skywang12345/p/3498483.html

    1、CopyOnWriteArrayList介绍

    它相当于线程安全的ArrayList。和ArrayList一样,它是个可变数组;但是和ArrayList不同的时,它具有以下特性:

    1. 它最适合于具有以下特征的应用程序:List 大小通常保持很小,只读操作远多于可变操作,需要在遍历期间防止线程间的冲突。

    2. 它是线程安全的

    3. 因为通常需要复制整个基础数组,所以可变操作(add()、set() 和 remove() 等等)的开销很大。

    4. 迭代器支持hasNext(), next()等不可变操作,但不支持可变 remove()等操作。

    5. 使用迭代器进行遍历的速度很快,并且不会与其他线程发生冲突。在构造迭代器时,迭代器依赖于不变的数组快照。

    6. CopyOnWriteArrayList使用了一种叫写时复制的方法,当有新元素添加到CopyOnWriteArrayList时,先将原有数组的元素拷贝到新数组中,然后在新的数组中做写操作,写完之后,再将原来的数组引用(volatile 修饰的数组引用)指向新数组。CopyOnWriteArrayList的整个add操作都是在的保护下进行的。

    2、要点

    这里写图片描述
    1. CopyOnWriteArrayList实现了List接口,因此它是一个队列

    2. CopyOnWriteArrayList包含了成员lock。每一个CopyOnWriteArrayList都和一个互斥锁lock绑定,通过lock,实现了对CopyOnWriteArrayList的互斥访问。

    3. CopyOnWriteArrayList包含了成员array数组,这说明CopyOnWriteArrayList本质上通过数组实现的。

        final transient ReentrantLock lock = new ReentrantLock();
    
        private transient volatile Object[] array;
    

    下面从“动态数组”和“线程安全”两个方面进一步对CopyOnWriteArrayList的原理进行说明。

    • CopyOnWriteArrayList的“动态数组”机制

      • 它内部有个“volatile数组”(array)来保持数据。在“添加(add)/修改(set)/删除(remove)”数据时,都会新建一个数组,并将原数组中的元素拷贝到新数组中,然后在新数组中更新,最后再将“volatile数组”引用指向新数组。这就是它叫做CopyOnWriteArrayList的原因!CopyOnWriteArrayList就是通过这种方式实现的动态数组;不过正由于它在“添加/修改/删除”数据时,都会新建数组,所以涉及到修改数据的操作,CopyOnWriteArrayList效率很低;但是单单只是进行遍历查找的话,效率比较高。
    • CopyOnWriteArrayList的“线程安全”机制

      • 是通过 volatile互斥锁 来实现的。
      • CopyOnWriteArrayList是通过“volatile数组”来保存数据的。一个线程读取volatile数组时,总能看到其它线程对该volatile数组最后的写入;就这样,通过volatile提供了“读取到的数据总是最新的”这个机制的保证。
      • CopyOnWriteArrayList通过互斥锁来保护数据。在“添加/修改/删除”数据时,会先“获取互斥锁”,再修改完毕之后,先将“volatile数组”引用指向新数组,然后再“释放互斥锁”;这样,就达到了保护数据的目的。

    3、创建,添加,删除,获取,遍历

    3.1 创建

    CopyOnWriteArrayList共3个构造函数。

        //创建空的CopyOnWriteArrayList对象
        public CopyOnWriteArrayList() {
            setArray(new Object[0]);
        }
    
        //创建含有指定Collection的元素的CopyOnWriteArrayList
        public CopyOnWriteArrayList(Collection<? extends E> c) {
            Object[] elements;
            if (c.getClass() == CopyOnWriteArrayList.class)
                elements = ((CopyOnWriteArrayList<?>)c).getArray();
            else {
                elements = c.toArray();
                // c.toArray might (incorrectly) not return Object[] (see 6260652)
                if (elements.getClass() != Object[].class)
                    elements = Arrays.copyOf(elements, elements.length, Object[].class);
            }
            setArray(elements);
        }
    
        
        //创建含有指定数组的元素的CopyOnWriteArrayList
        public CopyOnWriteArrayList(E[] toCopyIn) {
            setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
        }
    
        final void setArray(Object[] a) {
            array = a;
        }
    

    3.2 添加

    以add(E e)为例,来对“CopyOnWriteArrayList的添加操作”进行说明。

        //添加元素
        public boolean add(E e) {
            //获取该对象的锁
            final ReentrantLock lock = this.lock;
            // 获取“锁”,每次只有一个线程可进入临界区
            lock.lock();
            try {
                // 获取原始”volatile数组“中的数据和数据长度。
                Object[] elements = getArray();
                int len = elements.length;
                // 新建一个数组newElements,并将原始数据拷贝到newElements中;
                // newElements数组的长度=“原始数组的长度”+1
                Object[] newElements = Arrays.copyOf(elements, len + 1);
                // 将“新增加的元素”保存到newElements中。
                newElements[len] = e;
                // 将”volatile数组“引用指向newElements数组,这样旧数组就被GC回收了
                setArray(newElements);
                return true;
            } finally {
                // 释放“锁”
                lock.unlock();
            }
        }
    

    3.3 删除

    以remove(int index)为例,来对“CopyOnWriteArrayList的删除操作”进行说明。

            //删除索引index处的元素
            public E remove(int index) {
                final ReentrantLock lock = l.lock;
                //获得“锁”
                lock.lock();
                try {
                    //检测是否“数组越界”
                    rangeCheck(index);
                    checkForComodification();
                    //删除元素
                    E result = l.remove(index+offset);
                    expectedArray = l.getArray();
                    size--;
                    return result;
                } finally {
                    //释放“锁”
                    lock.unlock();
                }
            }
    
            private void rangeCheck(int index) {
                if (index < 0 || index >= size)
                    throw new IndexOutOfBoundsException("Index: "+index+",Size: "+size);
            }
    
            private void checkForComodification() {
                if (l.getArray() != expectedArray)
                    throw new ConcurrentModificationException();
            }
    
        //删除元素的真正实现
        public E remove(int index) {
            final ReentrantLock lock = this.lock;
            //获得“锁”
            lock.lock();
            try {
                // 获取原始”volatile数组“中的数据和数据长度。
                Object[] elements = getArray();
                int len = elements.length;
                //// 获取elements数组中的第index个数据。
                E oldValue = get(elements, index);
                int numMoved = len - index - 1;
                // 如果被删除的是最后一个元素,则直接通过Arrays.copyOf()进行处理,而不需要新建数组。
                if (numMoved == 0)
                    setArray(Arrays.copyOf(elements, len - 1));
                else {
                    // 否则,新建数组,然后将”volatile数组中被删除元素之外的其它元素“拷贝到新数组中;
                    // 最后,将”volatile数组“引用指向newElements数组,这样旧数组就被GC回收了。
                    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();
            }
        }
    

    3.4 获取

    get(int index)的实现很简单,就是返回”volatile数组“中的第index个元素。

        public E get(int index) {
            return get(getArray(), index);
        }
    
        private E get(Object[] a, int index) {
            return (E) a[index];
        }
    

    3.5 遍历

    以iterator()为例,来对“CopyOnWriteArrayList的遍历操作”进行说明。

        public Iterator<E> iterator() {
            return new COWIterator<E>(getArray(), 0);
        }
    
        static final class COWIterator<E> implements ListIterator<E> {
            /** Snapshot(快照) of the array */
            private final Object[] snapshot;
            /** Index of element to be returned by subsequent call to next.  */
            private int cursor;    // 游标
    
            private COWIterator(Object[] elements, int initialCursor) {
                cursor = initialCursor;
                snapshot = elements;
            }
    
            public boolean hasNext() {
                return cursor < snapshot.length;
            }
    
            public boolean hasPrevious() {
                return cursor > 0;
            }
    
            // 获取下一个元素
            @SuppressWarnings("unchecked")
            public E next() {
                if (! hasNext())
                    throw new NoSuchElementException();
                return (E) snapshot[cursor++];
            }
    
            // 获取上一个元素
            @SuppressWarnings("unchecked")
            public E previous() {
                if (! hasPrevious())
                    throw new NoSuchElementException();
                return (E) snapshot[--cursor];
            }
    
            public int nextIndex() {
                return cursor;
            }
    
            public int previousIndex() {
                return cursor-1;
            }
    
    
            //不支持remove
            public void remove() {
                throw new UnsupportedOperationException();
            }
    
            //不支持set
            public void set(E e) {
                throw new UnsupportedOperationException();
            }
    
    
            //不支持add
            public void add(E e) {
                throw new UnsupportedOperationException();
            }
    
            @Override
            public void forEachRemaining(Consumer<? super E> action) {
                Objects.requireNonNull(action);
                Object[] elements = snapshot;
                final int size = elements.length;
                for (int i = cursor; i < size; i++) {
                    @SuppressWarnings("unchecked") E e = (E) elements[i];
                    action.accept(e);
                }
                cursor = size;
            }
        }
    

    说明

    (1)创建迭代器的时候, 会保存数组元素的快照(有一个引用指向原数组)。

    (2)COWIterator不支持修改元素的操作。例如,对于remove(), set(), add()等操作,COWIterator都会抛出异常!

    (3)另外,需要提到的一点是,CopyOnWriteArrayList返回迭代器不会抛出ConcurrentModificationException异常,即它不是fail-fast机制的!

    相关文章

      网友评论

          本文标题:CopyOnWriteArrayList源码解析——JDK1.8

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