转载

Java系列-CopyOnWriteArrayList源码解析

CopyOnWriteArrayList 是 ArrayList 的线程安全版本。用一句话概括它的特点就是:所有的修改操作都是基于副本来进行的。

Java系列-CopyOnWriteArrayList源码解析

设计思想

java.util.concurrent 下,有很多线程安全的容器,大致可以分成三类 Concurrent*CopyOnWrite*Blocking* 这三类的容器都可以在并发环境下使用,但是实现的方式却不一样。

Concurrent* 容器是基于无锁技术实现,性能很好,ConcurrentHashMap 就是典型代表;CopyOnWrie* 容器则是基于拷贝来实现的,所以对于内存有很大的开销,CopyOnWriteArrayList 就属于这一类;Blocking* 容器则使用 锁技术实现了阻塞技术,在某些场景下非常有用。

CopyOnWriteArrayList 的核心操作如下,就是通过不断的拷贝数组来更新容器:

Java系列-CopyOnWriteArrayList源码解析

具体实现

CopyOnWriteArrayList 的成员变量如下:

final transient Object lock = new Object();
private transient volatile Object[] array;
复制代码

变量的数量很少,仅仅包含一个锁对象和一个用来放元素数组。因为 CopyOnWriteArrayList 保证线程安全的方式很简单,不断的通过备份元素来保证数据不会被修改。

如何实现线程安全

和其他线程安全的容器思路不一样,这个容器从空间的角度来解决线程安全的问题。所有对容器的修改是基于副本进行的,修改的过程中也通过锁对象锁来保证并发安全,从这个角度来说,CopyOnWriteArrayList 的并发度也不会太高。所以一句话概括就是使用 synchronized + Array.copyOf 来实现线程安全。

迭代器是基于副本进行的,即使原数组被改变,副本也不会被影响。也就不会抛出 ConcurrentModificationException 异常。但是这样也会让最新的修改无法及时体现出来。

核心方法的实现

get 方法直接读取数组就行,不需要上锁,多个线程同时读也就不会有并发的问题产生。

public E get(int index) {
    return elementAt(getArray(), index);
}
static <E> E elementAt(Object[] a, int index) {
    return (E) a[index];
}
复制代码

下来来看一下 add 方法,代码很短:

// CopyOnWriteArrayList.add()
public boolean add(E e) {
    synchronized (lock) {
        Object[] es = getArray();
        int len = es.length;
        // 复制原数组,并且长度加一
        es = Arrays.copyOf(es, len + 1);
        es[len] = e;
        // 指向新的数组
        setArray(es);
        return true;
    }
}
复制代码

也就是是说,每次添加元素的时候,都会把原数组复制一次,并把复制后的数组长度加 1,然后把元素添加进数组,最后用新数组去替代旧数组,完成添加。这样 CopyOnWriteArrayList 根本就不需要扩容,因为每次添加元素都是一个扩容的过程。

// CopyOnWriteArrayList.remove()
public E remove(int index) {
    synchronized (lock) {
        Object[] es = getArray();
        int len = es.length;
        E oldValue = elementAt(es, index);
        // 计算需要移动的元素
        int numMoved = len - index - 1;
        Object[] newElements;
        // 如果删除的是最后一个元素,则不需要移动
        if (numMoved == 0)
            newElements = Arrays.copyOf(es, len - 1);
        else {
            newElements = new Object[len - 1];
            // 删除的是中间元素,则需要分两次复制
            System.arraycopy(es, 0, newElements, 0, index);
            System.arraycopy(es, index + 1, newElements, index, numMoved);
        }
        // 指向新的数组
        setArray(newElements);
        return oldValue;
    }
}
复制代码

删除元素的情况就要复杂一些。删除的时候如果是删除中间的元素,需要后面元素进行移动。然后新数组的长度也会减 1,这就相当于缩容过程。

CopyOnWriteArrayList 的迭代器的实现也很不复杂:

# COWIterator 构造函数
COWIterator(Object[] es, int initialCursor) {
    cursor = initialCursor;
    // 容器元素的副本
    snapshot = es;
}
复制代码

可以看到,构造迭代器的时候,直接把整个元素的副本都传进来了,后续的操作都会在这个副本上进行,甚至都需要上锁。所以是 fail-safe 的。

在 CopyOnWriteArrayList 中,有两种数组拷贝方式 Arrays.copyOfSystem.arraycopy 。这两种方式有什么区别吗?实际上是没有的,来看一下 Arrays.copyOf 的源码:

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                        Math.min(original.length, newLength));
    return copy;
}
复制代码

没错,Arrays.copyOf 调用了 System.arraycopy 来实现数组拷贝。

通过上面的分析可知,CopyOnWriteArrayList 的读效率很高,但是写的效率很低,所以比较适合读多写少的场景。

另外需要说一句,CopyOnWriteArraySet 使用 CopyOnWriteArrayList 实现。Set 一如继往喜欢使用现成的类来实现。

原文

原文  https://juejin.im/post/5e191e79e51d453cc14cfd97
正文到此结束
Loading...