重新认识 Java 中的队列

「这是我参与11月更文挑战的第18天，活动详情查看：2021最后一次更文挑战」

本文被《从小工到专家的 Java 进阶之旅》收录。

你好，我是看山。

书接上文，上次聊了聊在多线程中使用 ArrayList 会发生什么，这次我们说说平时常用的列表：Vector、ArrayList、CopyOnWriteArrayList、SynchronizedList。

Vector

Vector是在 JDK 1.0 提供的，虽然没有被标记Deprecated，但是事实上已经没人使用了。主要原因是性能差，且不符合需求。

从源码可以看出（这里不贴源码了），Vector是基于数组实现，几乎在所有操作方法上，都用synchronized关键字实现方法同步，这种同步方式可以对单一操作进行加锁，比如多个线程同时执行add会同步阻塞执行，但是多线程执行add和remove时，就不会阻塞了。

但是，大部分需要对队列加锁的场景，是想对整个队列加锁，而不仅仅是对单一操作加锁。也就是说，Vector和我们的期望不同，但是又额外增加了同步操作带来的性能开销。所以，不是必须使用的场景，都可以使用ArrayList代替，即使是多线程情况下需要同步队列，也可以使用CopyOnWriteArrayList和SynchronizedList代替。

ArrayList

ArrayList是在 JDK 1.1 提供的，作为Vector的继任者（ArrayList实现方式与Vector几乎完全相同），ArrayList把方法上的synchronized全部去掉了，完全没有实现同步，是非线程安全的。

它的非线程安全，还体现在迭代器的快速失败上。在使用方法iterator和listIterator创建迭代器之后，如果还对原来的ArrayList队列进行修改（add 或 remove），迭代器迭代的时候就会报ConcurrentModificationException异常。从源码可以看出，迭代器在迭代过程中，会检查队列中修改次数modCount与创建迭代器时落下的修改次数快照expectedModCount是否相等，相等表示没有修改过，代码如下：

java复制代码private class Itr implements Iterator<E> {
    // 这段代码是从 ArrayList 中摘取的
    // 只留下检查方法，略过其他代码，有兴趣的可以从源码中查看
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

第三点是在多线程场景中，添加元素可能会丢失数据，或者发生数组越界异常，在多线程中使用 ArrayList 会发生什么有详细描述，这里就不赘述了。

SynchronizedList

SynchronizedList是Collections的静态内部类，使用Collections.synchronizedList()静态方法创建，是一个通过组合List类实现的封装实现。它的大多数方法通过synchronized (mutex){...}代码块同步方式，因为加锁对象mutex是队列对象中定义的相同对象，所以对mutex加锁时，就实现对整个队列加锁，也就解决了Vector不能对整个队列加锁的问题。所以如果有多个线程同时操作add和remove方法，会阻塞同步执行。

ArrayList中存在的迭代器快速失败情况，依然存在，正如下面源码中的注释：想要使用迭代器，需要用户手动实现同步。

java复制代码static class SynchronizedList<E>
    extends SynchronizedCollection<E>
    implements List<E> {
    
    // 代码摘自 Collections，省略很多代码

    public void add(int index, E element) {
        synchronized (mutex) {list.add(index, element);}
    }

    public ListIterator<E> listIterator() {
        return list.listIterator(); // Must be manually synched by user
    }

    public ListIterator<E> listIterator(int index) {
        return list.listIterator(index); // Must be manually synched by user
    }
}

手动同步的时候需要注意，既然我们关注的全局同步，在迭代器设置同步的时候，要保证锁定对象与add等方法中对象相同。这个在后续补充说明，这里就不展开了。

CopyOnWriteArrayList

CopyOnWriteArrayList是从 JDK 1.5 开始提供的，先看看add方法的源码：

java复制代码public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    /** The lock protecting all mutators */
    final transient ReentrantLock lock = new ReentrantLock();

    /** The array, accessed only via getArray/setArray. */
    private transient volatile Object[] array;

    // 代码摘自 CopyOnWriteArrayList，省略很多代码

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

    public boolean addAll(Collection<? extends E> c) {
        Object[] cs = (c.getClass() == CopyOnWriteArrayList.class) ?
            ((CopyOnWriteArrayList<?>)c).getArray() : c.toArray();
        if (cs.length == 0)
            return false;
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            if (len == 0 && cs.getClass() == Object[].class)
                setArray(cs);
            else {
                Object[] newElements = Arrays.copyOf(elements, len + cs.length);
                System.arraycopy(cs, 0, newElements, len, cs.length);
                setArray(newElements);
            }
            return true;
        } finally {
            lock.unlock();
        }
    }

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

    /**
     * {@inheritDoc}
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        return get(getArray(), index);
    }
}

可以看到，CopyOnWriteArrayList借助ReentrantLock实现同步，在synchronized优化之前，ReentrantLock性能高于synchronized。CopyOnWriteArrayList也是通过数组实现的，但是在数组前面增加了volatile关键字，实现了多线程情况下数组的可见性，更加安全。更重要的一点是，CopyOnWriteArrayList在add添加元素的时候，实现方式是重建数组对象，替换原来的数组引用。与ArrayList的扩容方式相比，减少了空间，但是也增加了赋值数组的性能开销。在get获取元素的时候，没有任何锁，直接数据返回。

CopyOnWriteArrayList的迭代器时通过COWIterator实现的，调用iterator方法时，将当前队列中数组的快照赋值到迭代器中的数组引用上。如果原来的队列发生修改，队列中数组会指向别的引用，而迭代器中的数组不会发生变化，所以在多线程执行过程中，通过迭代器遍历数组，也可以修改队列中的数据。这种方式保障线程安全的同时，也可能会出现数据不一致的情况，只能是使用的使用多注意了。

java复制代码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;
    }
}

对比 CopyOnWriteArrayList 和 SynchronizedList

CopyOnWriteArrayList和SynchronizedList都实现了同步，实现方式上采用的是不同策略，各自的侧重点不同。

CopyOnWriteArrayList侧重于读写分离，发生数据写操作（add或remove）时，会加锁，各个线程阻塞执行，执行过程会创建数据副本，替换对象引用；如果同时有读操作（get或iterator），读操作读取的是老数据，或者成为历史数据快照，或者成为缓存数据。这会造成读写同时发生时，数据不一致的情况，但是数据最终会一致。这种方式与数据库读写分离模式几乎相同，很多特性可以类比。

SynchronizedList侧重数据强一致，也就是说当发生数据写操作（add或remove）时，会加锁，各个线程阻塞执行，而且也会通过相同的锁阻塞get操作。

从CopyOnWriteArrayList和SynchronizedList两种不同事项方式，可以推断CopyOnWriteArrayList在写少读多的场景中执行效率高，SynchronizedList的读写操作效率很均衡，所以在写多读多、写多读少的场景执行效率都会高于CopyOnWriteArrayList。借用网上的测试结果：

对比 CopyOnWriteArrayList 和 SynchronizedList

文末总结

synchronized关键字在 JDK 8 之前性能比较差，可以看到 JDK1.5 之后实现的同步代码，很多是通过ReentrantLock实现的。
多线程场景中除了需要考虑同步外，还需要考虑数据可见性，可以通过volatile关键字实现。
ArrayList完全没有同步操作，是非线程安全的
CopyOnWriteArrayList和SynchronizedList属于线程安全队列
CopyOnWriteArrayList实现读写分离，适合场景是写少读多的场景
SynchronizedList要求数据强一致，是队列全局加锁方式，读操作也会加锁
Vector只是在迭代器遍历性能很差，如果不考虑全局锁定队列，单纯读操作和单独写操作性能与SynchronizedList相差不大。

Vector

ArrayList

SynchronizedList

CopyOnWriteArrayList

对比 CopyOnWriteArrayList 和 SynchronizedList

文末总结

推荐阅读