看山聊并发：认识 Java 中的队列：Vector、ArrayList、CopyOnWriteArrayList、SynchronizedList

￡神魔★判官ぃ 2021-09-25 04:22 261阅读 0赞

![认识 Java 中的队列：Vector、ArrayList、CopyOnWriteArrayList、SynchronizedList][Java _Vector_ArrayList_CopyOnWriteArrayList_SynchronizedList]

你好，我是看山。

书接上文，上次聊了聊 [在多线程中使用 ArrayList 会发生什么][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 会发生什么][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`。借用网上的测试结果：

![对比 CopyOnWriteArrayList 和 SynchronizedList][CopyOnWriteArrayList _ SynchronizedList]

## 文末总结 ##

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?][Why is Java Vector _and Stack_ class considered obsolete or deprecated]
2.  [CopyOnWriteArrayList 与 Collections.synchronizedList 的性能对比][CopyOnWriteArrayList _ Collections.synchronizedList]
3.  [Collections.synchronizedList 、CopyOnWriteArrayList、Vector 介绍、源码浅析与性能对比][Collections.synchronizedList _CopyOnWriteArrayList_Vector]

## 推荐阅读 ##

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

--------------------

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

个人主页：[https://www.howardliu.cn][https_www.howardliu.cn]  
个人博文：[认识 Java 中的队列：Vector、ArrayList、CopyOnWriteArrayList、SynchronizedList][Java _Vector_ArrayList_CopyOnWriteArrayList_SynchronizedList 1]  
CSDN 主页：[http://blog.csdn.net/liuxinghao][http_blog.csdn.net_liuxinghao]  
CSDN 博文：[认识 Java 中的队列：Vector、ArrayList、CopyOnWriteArrayList、SynchronizedList][Java _Vector_ArrayList_CopyOnWriteArrayList_SynchronizedList 2]

![公众号：看山的小屋][21785bb43b333b0ff8efda479e715378.png]

[Java _Vector_ArrayList_CopyOnWriteArrayList_SynchronizedList]: /images/20210923/8b812ee4caaf4bc6b2523fb02b008aff.png
[ArrayList]: https://www.howardliu.cn/arraylist-is-not-thread-safe/
[CopyOnWriteArrayList _ SynchronizedList]: /images/20210923/a5f8bde226fb4b658ef4624d7bc23630.png
[Why is Java Vector _and Stack_ class considered obsolete or deprecated]: https://stackoverflow.com/questions/1386275/why-is-java-vector-and-stack-class-considered-obsolete-or-deprecated
[CopyOnWriteArrayList _ Collections.synchronizedList]: https://blog.csdn.net/yangzl2008/article/details/39456817
[Collections.synchronizedList _CopyOnWriteArrayList_Vector]: https://juejin.cn/post/6844904054745743367
[https_www.howardliu.cn]: https://www.howardliu.cn
[Java _Vector_ArrayList_CopyOnWriteArrayList_SynchronizedList 1]: https://www.howardliu.cn/understanding-java-list/
[http_blog.csdn.net_liuxinghao]: http://blog.csdn.net/liuxinghao
[Java _Vector_ArrayList_CopyOnWriteArrayList_SynchronizedList 2]: https://blog.csdn.net/liuxinghao/article/details/113780875
[21785bb43b333b0ff8efda479e715378.png]: /images/20210923/247fcd04da3148b29c9d861c45c24e4e.png