全部标签
写点什么
开源云计算行业资讯玩转写作平台算法Python人工智能区块链Linux前端个人成长面试架构师编程企业动态新基建敏捷安全读书笔记高效工作团队管理创业活动专区生涯规划知识管理运维产品经理 查看更多

认识 Java 中的队列：Vector、ArrayList、CopyOnWriteArrayList、SynchronizedList

用户头像
看山
关注
发布于: 2021 年 02 月 10 日
认识 Java 中的队列：Vector、ArrayList、CopyOnWriteArrayList、SynchronizedList

你好，我是看山。


书接上文，上次聊了聊 在多线程中使用 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是否相等，相等表示没有修改过，代码如下：


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


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方法的源码：


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


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。借用网上的测试结果：



文末总结


  1. synchronized关键字在 JDK 8 之前性能比较差，可以看到 JDK1.5 之后实现的同步代码，很多是通过ReentrantLock实现的。

  2. 多线程场景中除了需要考虑同步外，还需要考虑数据可见性，可以通过volatile关键字实现。

  3. ArrayList完全没有同步操作，是非线程安全的

  4. CopyOnWriteArrayList和SynchronizedList属于线程安全队列

  5. CopyOnWriteArrayList实现读写分离，适合场景是写少读多的场景

  6. SynchronizedList要求数据强一致，是队列全局加锁方式，读操作也会加锁

  7. Vector只是在迭代器遍历性能很差，如果不考虑全局锁定队列，单纯读操作和单独写操作性能与SynchronizedList相差不大。


参考


  1. Why is Java Vector (and Stack) class considered obsolete or deprecated?

  2. CopyOnWriteArrayList 与 Collections.synchronizedList 的性能对比

  3. Collections.synchronizedList 、CopyOnWriteArrayList、Vector 介绍、源码浅析与性能对比


推荐阅读


  1. 如果非要在多线程中使用 ArrayList 会发生什么？



你好，我是看山，公众号：看山的小屋，10 年老后端，Apache Storm、WxJava、Cynomys 开源贡献者。主业：程序猿，兼职：架构师。游于码界，戏享人生。


划线
评论
复制
发布于: 2021 年 02 月 10 日阅读数: 43

版权声明: 本文为 InfoQ 作者【看山】的原创文章。

原文链接:【http://xie.infoq.cn/article/eba6dfb552dd76188706fdcf7】。

本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。

Java线程安全
用户头像

看山

关注

公众号：看山的小屋 2017.10.26 加入

游于码界，戏享人生。

评论

发布
暂无评论
Copyright © 2021, Geekbang Technology Ltd. All rights reserved. 极客邦控股（北京）有限公司 | 京 ICP 备 16027448 号 - 5京公网安备京公网安备 11010502039052号
认识 Java 中的队列：Vector、ArrayList、CopyOnWriteArrayList、SynchronizedList