更新日志

CopyOnWriteArrayList

CopyOnWriteArrayList 是 ArrayList 的线程安全版本，从他的名字可以推测，CopyOnWriteArrayList 是在有写操作的时候会 copy 一份数据，然后写完再设置成新的数据。CopyOnWriteArrayList 适用于读多写少的并发场景，CopyOnWriteArraySet 是线程安全版本的 Set 实现，它的内部通过一个 CopyOnWriteArrayList 来代理读写等操作，使得 CopyOnWriteArraySet 表现出了和 CopyOnWriteArrayList 一致的并发行为，他们的区别在于数据结构模型的不同，set 不允许多个相同的元素插入容器中，具体的细节将在下文中分析。

CopyOnWriteArrayList 类图
上面的图片展示你了 CopyOnWriteArrayList 的类图，可以看到它实现了 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.lock;
        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

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

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

CopyOnWriteArraySet

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

    private final CopyOnWriteArrayList<E> 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 (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 这样的容器集合是我们经常使用的，理解他的具体实现有助于我们更好的使用它。

作者：一字马胡
链接：https://www.jianshu.com/p/cd7a73e6bd78
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。