20.3 容器类

线程安全的容器有两类：一类是同步容器；另一类是并发容器。在15.2节，我们介绍了同步容器。关于并发容器，我们介绍了：

• 写时复制的List和Set。
• ConcurrentHashMap。
• 基于SkipList的Map和Set。
• 各种队列。

（1）同步容器

Collections类中有一些静态方法，可以基于普通容器返回线程安全的同步容器，比如：

public static <T> Collection<T> synchronizedCollection(Collection<T> c)
public static <T> List<T> synchronizedList(List<T> list)
public static <K, V> Map<K, V> synchronizedMap(Map<K, V> m)

它们是给所有容器方法都加上synchronized来实现安全的。同步容器的性能比较低，另外，还需要注意一些问题，比如复合操作和迭代，需要调用方手工使用synchronized同步，并注意不要同步错对象。

而并发容器是专为并发而设计的，线程安全、并发度更高、性能更高、迭代不会抛出ConcurrentModificationException、很多容器以原子方式支持一些复合操作。

（2）写时复制的List和Set

CopyOnWriteArrayList基于数组实现了List接口，CopyOnWriteArraySet基于CopyOn-WriteArrayList实现了Set接口，它们采用了写时复制，适用于读远多于写，集合不太大的场合。不适用于数组很大且修改频繁的场景。它们是以优化读操作为目标的，读不需要同步，性能很高，但在优化读的同时牺牲了写的性能。

（3）ConcurrentHashMap

HashMap不是线程安全的，在并发更新的情况下，HashMap的链表结构可能形成环，出现死循环，占满CPU。ConcurrentHashMap是并发版的HashMap，通过细粒度锁和其他技术实现了高并发，读操作完全并行，写操作支持一定程度的并行，以原子方式支持一些复合操作，迭代不用加锁，不会抛出ConcurrentModificationException。

（4）基于SkipList的Map和Set

ConcurrentHashMap不能排序，容器类中可以排序的Map和Set是TreeMap和TreeSet，但它们不是线程安全的。Java并发包中与TreeMap/TreeSet对应的并发版本是Concurrent-SkipListMap和ConcurrentSkipListSet。ConcurrentSkipListMap是基于SkipList实现的，Skip-List称为跳跃表或跳表，是一种数据结构，主要操作复杂度为O(log2(N))。并发版本采用跳表而不是树，是因为跳表更易于实现高效并发算法。

ConcurrentSkipListMap没有使用锁，所有操作都是无阻塞的，所有操作都可以并行，包括写。与ConcurrentHashMap类似，迭代器不会抛出ConcurrentModificationException，是弱一致的，也直接支持一些原子复合操作。

（5）各种队列

各种阻塞队列主要用于协作，非阻塞队列适用于多个线程并发使用一个队列的场合，有两个非阻塞队列：ConcurrentLinkedQueue和ConcurrentLinkedDeque。Concurrent-LinkedQueue实现了Queue接口，表示一个先进先出的队列；ConcurrentLinkedDeque实现了Deque接口，表示一个双端队列。它们都是基于链表实现的，都没有限制大小，是无界的，这两个类最基础的实现原理是循环CAS，没有使用锁。