Java中的线程安全集合CopyOnWriteArrayList解析

目录

• CopyOnWriteArray编程List
• CopyOnWriteArraySet

CopyOnWriteArrayList

CopyOnWriteArrayList是ArrayList的线程安全版本，从他的名字可以推测，CopyOnWriteArrayList是在有写操作的时候会copy一份数据，然后写完再设置成新的数据。

CopyOnWriteArrayList适用于读多写少的并发场景，CopyOnWriteArraySet是线程安全版本的Set实现，它的内部通过一个CopyOnWriteArrayList来代理读写等操作，使得CopyOnWriteArraySet表现出了和CopyOnWriteArrayList一致的并发行为，他们的区别在于数据结构模型的不同，set不允许多个相同的元素插入容器中，具体的细节将在下文中分析。

可以看到它实现了List接口，如果去看ArrayList的类图的话，可以发现也是实现了List接口，也就得出一句废话，ArrayList提供的api，CopyOnWriteArrayList也提供

下文中来分析CopyOnWriteArrayList是如何来做到线程安全的实现读写数据的，而且也会顺便对比ArrayList的等效实现为什么不支持线程安全的。

下面首先展示了CopyOnWriteArrayList中比较重要的成员：

/** The lock protecting all mutators */
final transient ReentrantLock lock = new ReentrantLock();
/** The array, Accessed only via getArray/setArray. */
private transient volatile Object[] array;

可以看到，CopyOnWriteArrayList使用了ReentrantLock来支持并发操作，array就是实际存放数据的数组对象。ReentrantLock是一种支持重入的独占锁，任意时刻只允许一个线程获得锁，所以可以安全的并发去写数组，关于Java中锁的细节，可以参考文章Java可重入锁详解。接下来看一下CopyOnWriteArrayList是如何使用这个lock来实现并发写的，下面首先展示了add方法的代码：

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();//释放锁
    }
}

为了对比ArrayList，下面展示了ArrayList中的add方法的细节：

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}        

相比CopyOnWriteArrayList，ArrayList的add方法实现就显得啰嗦的多，而且ArrayList并不支持线程安全，至于为什么不支持线程安全，看代码就知道了，这几个调用的方法中都没有类似锁（与锁等效语义的组件）出现。下面再来看另一个版本的add方法：

public void add(int index, E element) {
    final ReentrantLock lock = this.pythonlock;
    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();
    }
}

在操作之前都是先lock住的，这里面有一个有意思的地方，因为该方法可以指定index来插入value，如果这个index位置上已经有旧值，那么该方法的作用类似replace，如果该index为当前数组的长度，那么该方法和上面分析的add方法等效，现在分析一下index位置上已经有值的情况，会分为两段copy，然后在中间设置新值。现在来分析一下读操作，下面是get方法的细节：

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

可以发现是非常简单的，而且读是允许多个线程进入的。下面来分析一下CopyOnWriteArrayList提高的迭代器。下面是两个重要的变量：

    /** Snapshot of the array */
    private final Object[] snapshot;
    /** Index of element to be returned by subsequent call to next.  */
    private int cursor;

遍历的时候首先会获得当前数组对象的一个拷贝，称为快照，然后遍历的操作会在该快照上进行，那如果获取了迭代器之后再对CopyOnWriteArrayList进行写操作会怎么样？迭代器能感知到这种变化吗？下面实际实验一下：

    CopyOnWriteArrayList<String> copyOnWriteArrayList = new CopyOnWriteArrayList<>();
    copyOnWriteArrayList.add("first");
    copyOnWriteArrayList.add("second");
    Iterator<String> iterator = copyOnWriteArrayList.iterator();
    copyOnWriteArrayList.add("third");
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
    //output:
    first
    second

结果是不能感知，也就是说，这个快照并不会和外界有任何联系，某个线程在获取迭代器的时候就会拷贝一份，或者说，每一个线程都将获得当前时刻的一个快照，所以不需要加锁就可以安全的实现遍历，下面的代码也php证实了上面的说法：

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
}

CopyOnWriteArraySet

CopyOnWriteArraySet使用一个CopyOnWriteArrayList来做代理，它的所有api都是依赖于CopyOnWriteArrayList来实现的，下面的代码也展示了这种代理的事实： private final CopyOnWriteArrayList al;

/**
 * Creates an empty set.
 */
public CopyOnWriteArraySet() {
    al = new CopyOnWriteArrayList<E>();
}

下面来分析一下CopyOnWriteArraySet的写操作实现，比如add方法：

public boolean add(E e) {
    return al.addIfAbsent(e);
}
public boolean addIfAbsent(E e) {
    Object[] snapshot = getArray();
    return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
        addIfAbsent(e, snapshot);
}
private boolean addIfAbsent(E e, Object[] snapshot) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] current = getArray();
        int len = current.length;
        if (snapshot != current) {
            // Optimize for lost race to another addXXX operation
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++)
                if js(current[i] != snapshot[i] && eq(e, current[i]))
                    return false;
            if (indexOf(e, current, common, len) >= 0)
                    return false;
        }
        Object[] newElements = Arrays.copyOf(current, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}    

set是一种不允许有重复元素的简单数据结构，所以和CopyOnWriteArrayList不同，CopyOnWriteArraySet需要add在插入新元素的时候多做一些判断，而CopyOnWriteArraySet在实现上使用了CopyOnWriteArrayList的addIfAbsent方法，这个方法的意思就是如果存在就不再插入，如果不存在再进行插入。

本人分析了CopyOnWriteArrayList的实现细节，并且分析了基于CopyOnWriteArrayList实现的CopyOnWriteArraySet，介于CopyOnWriteArrayList的简单性，本文没有太多亮点，但是理解CopyOnWriteArrayList的实现细节是有必要的，在并发环境下，我们在选择对象容器的时候需要考量是否需要选择线程安全的容器，如果不需要编程客栈，则优先选择ArrayList等没有线程安全保障的容器，如果需要线程安全保障，那么必须选择类似CopyOnWriteArrayList的线程安全的容器集合，否则会造成不可预料的错误。当然，实现线程安全的代价是以损失部分性能为代价的，毕竟有lock-unlock的操作，但是这又是必须的。接下来的文章会分析一些java中实现的线程安全的容器，比如ConcurrentHashMap等，当然，也会对类似HashMap之类的非线程安全的容器集合进行分析总结，毕竟类似HashMap这样的容器集合是我们经常使用的，理解他的具体实现有助于我们更好的使用它。

到此这篇关于Java中的线程安全集合CopyOnWriteArrayList解析的文章就介绍到这了,更多相关Java的CopyOnWriteArrayList内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！