文档章节

多线程十之CopyOnWriteArrayList源码分析

o
 osc_a22drz29
发布于 2019/03/25 09:39
字数 1888
阅读 15
收藏 0

精选30+云产品,助力企业轻松上云!>>>

[TOC]

简介

  我们都很熟悉容器对象ArrayList,并且在初学时就被告知ArrayList不是线程安全的:当我们在使用迭代器遍历ArrayList时,如果有其他线程修改了ArrayList对象,那么就会抛出ConcurrentModificationException异常。相较于Vector使用synchronized加锁保证线程安全性,JUC提供了多线程版“ArrayList”:CopyOnWriteArrayList。下面是JDK对CopyOnWriteArrayList的介绍:

A thread-safe variant of ArrayList in which all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array. This is ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations, and is useful when you cannot or don't want to synchronize traversals, yet need to preclude interference among concurrent threads. The "snapshot" style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException. The iterator will not reflect additions, removals, or changes to the list since the iterator was created. Element-changing operations on iterators themselves (remove, set, and add) are not supported. These methods throw UnsupportedOperationException.

大意是CopyOnWriteArrayList是线程安全版本的ArrayList,所有对CopyOnWriteArrayList修改的操作都是在内部数组的拷贝上进行操作的,这样做虽然内存花费大,但是在遍历操作大于修改操作时这样效率更高,可以有效防止抛出ConcurrentModificationException异常,迭代器迭代期间不支持对元素更改操作,否则会抛出UnsupportedOperationException异常。

类结构

  CopyOnWriteArrayList实现了List接口,List表示是有序的Collection,即它用某种特定的插入顺序来维护元素顺序;实现了标记接口RandomAccess接口支持快速访问;实现了Iterable接口可以使用迭代器遍历容器元素。

源码解析

构造方法

  CopyOnWriteArrayList互斥锁用于对修改容器元素阶段加锁,被volatile修饰的Object数组是CopyOnWriteArrayList存储数据的底层数据结构,通过volatile保证能够读到其他线程对CopyOnWriteArrayList数据的修改,对于数组的访问都是通过getArray/setArray方法。   CopyOnWriteArrayList提供了三个重载的构造函数,无参构造函数会调用setArray方法构造一个空的Object数组,另外两个构造函数分别传入集合/数组参数,将集合/数组内元素存入CopyOnWriteArrayList的底层Object数组。

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访问设置,volatile动态数组
    private transient volatile Object[] array;

    final Object[] getArray() {
        return array;
    }

    final void setArray(Object[] a) {
        array = a;
    }

    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);
    }

	//传入数组
    public CopyOnWriteArrayList(E[] toCopyIn) {
        setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
    }
}

add(E e)

   add方法的作用是把传入元素添加到链表list的末尾。add方法有两点需要注意:1.在写入过程使用了互斥锁,所以同一时间只有一个线程在修改CopyOnWriteArrayList 2.增加元素并不是直接在原数组操作,而是在原数组的拷贝数组上添加元素的,添加完成后再调用setArray方法用新数组代替原始数组

    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(int index, E element)

  这个方法的作用是把新元素插入到特定位置,会把原来位置的元素向后挤。过程与上面的add大致相同。

    public void add(int index, E element) {
		//互斥锁
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
			//原始数组
            Object[] elements = getArray();
            int len = elements.length;
			//检查index有效性
            if (index > len || index < 0)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+len);
			//拷贝数组
            Object[] newElements;
			//从index到数组末尾要向后移动一位数组元素的个数
            int numMoved = len - index;
			//如果index==length,直接把原数组复制到新数组
            if (numMoved == 0)
                newElements = Arrays.copyOf(elements, len + 1);
			//否则分成两段复制,原始数组index前面的元素位置一一对应赋值到新数组,原数组index开始的元素复制到
			//新数组index+1到length+1,相当于依次后移。空出来的index就是新元素插入的位置
            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();
        }
    }

get(int index)

  获取索引位置为index位置处的元素,获取元素过程中没有使用互斥锁上锁。

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

    @SuppressWarnings("unchecked")
    private E get(Object[] a, int index) {
		//返回数组index处位置
        return (E) a[index];
    }

remove(int index)

  移除index处元素。由于涉及到修改到对链表内元素的修改,因此移除过程会使用互斥锁上锁。

    public E remove(int index) {
		//上锁
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
			//原始数组
            Object[] elements = getArray();
            int len = elements.length;
			//数组index处要移除的元素
            E oldValue = get(elements, index);
			//index+1到数组末尾要移动的元素个数
            int numMoved = len - index - 1;
			//如果要移除的元素在数组末尾(index=len-1),直接复制数组区间[0,len-2]所有元素到新数组
            if (numMoved == 0)
                setArray(Arrays.copyOf(elements, len - 1));
			//如果移除的元素不再末尾,分成两段赋值,首先把[0,index-1]区间元素复制到新数组,再把
			//[index+1,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();
        }
    }

迭代器Iterator遍历

  CopyOnWriteArrayList支持使用迭代器迭代,使用iterator方法返回COWIterator对象,在迭代过程中没有上锁,也不支持remove/set/add等修改方法。

	//返回COWIterator对象
    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;
        }

        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;
        }
    }

总结

  Copy-On-Write简称COW,中文简称写入时复制,是一种程序设计优化策略,具体思想就是对于共享内容做修改操作时,会把共享内容复制出来,在复制内容上修改,修改完成后在返还到原内容上。对于CopyOnWriteArrayList而言,向容器添加元素是先把容器复制一份,向复制的容器添加元素,添加成功后把复制的容器赋值给原容器对象;而对于读取容器的操作直接在原容器进行操作。CopyOnWriteArrayList利用了COW技术实现读写的分离,对于写操作实行加锁保证安全性,读操作不改变容器不需加锁,相对于Vector对所有操作加锁来保证安全性的效率更高,适合于读多写少的场景。同时在CopyOnWriteArrayList保存数据量较大时,对于容器的写入由于复制原容器产生新容器用于写操作,造成了两倍的内存消耗,会引发频繁的垃圾回收,降低性能。

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
Java 高频面试题:聊一聊 JUC 下的 CopyOnWriteArrayList

ArrayList 是我们常用的工具类之一,但是在多线程的情况下,ArrayList 作为共享变量时,并不是线程安全的。主要有以下两个原因: 1、ArrayList 自身的 elementData、size、modCount 在进行操...

weixin_46062001
05/08
0
0
Java 经典面试题:聊一聊 JUC 下的 CopyOnWriteArrayList

Java 经典面试题:聊一聊 JUC 下的 CopyOnWriteArrayList ArrayList 是我们常用的工具类之一,但是在多线程的情况下,ArrayList 作为共享变量时,并不是线程安全的。主要有以下两个原因: 1、...

优惠码发放
05/07
0
0
Java 经典面试题:聊一聊 JUC 下的 CopyOnWriteArrayList

ArrayList 是我们常用的工具类之一,但是在多线程的情况下,ArrayList 作为共享变量时,并不是线程安全的。主要有以下两个原因: 1、 ArrayList 自身的 elementData、size、modCount 在进行操...

平头哥的技术博文
05/07
0
0
Java 经典面试题:聊一聊 JUC 下的 CopyOnWriteArrayList

ArrayList 是我们常用的工具类之一,但是在多线程的情况下,ArrayList 作为共享变量时,并不是线程安全的。主要有以下两个原因: 1、 ArrayList 自身的 elementData、size、modCount 在进行操...

平头哥的技术博文
05/07
0
0
Vector和CopyOnWriteArrayList源码解析

前面介绍的ArrayList和LinkedList, 在多线程的场景中就不适合了。JDK提供了线程安全的List。 Vector和CopyOnWriteArrayList是线程安全的 1、Vector 这个类属性和方法同ArrayList,主要区别是...

osc_tjnx25e9
04/05
4
0

没有更多内容

加载失败,请刷新页面

加载更多

skywalking实现分布式系统链路追踪

一、背景 随着微服务的越来越流行,我们服务之间的调用关系就显得越来越复杂,我们急需一个APM工具来分析系统中存在的各种性能指标问题以及调用关系。目前主流的APM工具有CAT、Zipkin、Pinpo...

燚-焱
1分钟前
0
0
2020最新的Spring Boot 分布式锁的具体实现(内附代码)

前言 面试总是会被问到有没有用过分布式锁、redis 锁,大部分读者平时很少接触到,所以只能很无奈的回答 “没有”。本文通过 Spring Boot 整合 redisson 来实现分布式锁,并结合 demo 测试结...

北柠Java
7分钟前
0
0
Shiro中获取Cookie

自定义shiro的SessionIdCookie 在使用shiro的时候,曾经有段时间很苦恼,因为我cookie的sessionId经常无故被改,然后抛There is no session with id [xxxx]的异常。我们知道,当请求过来,s...

豫华商
7分钟前
0
0
JPA和Hibernate有什么区别? [关闭] - What's the difference between JPA and Hibernate? [closed]

问题: I understand that JPA 2 is a specification and Hibernate is a tool for ORM. 我知道JPA 2是一个规范,而Hibernate是ORM的工具。 Also, I understand that Hibernate has more fea......

富含淀粉
24分钟前
6
0
Java知识回顾-基础知识(2)

局部变量/成员变量: 成员变量是属于类的 局部变量是属于方法的 都可以被final修饰 java中使用new 创建实例对象 方法返回值的作用: 方法的返回值 是指方法中的一系列操作有返回结果 返回值的作...

心田已荒
29分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部