Java 并发总结（三）：容器类

1. Java 中线程安全的容器类的分类，分别有哪些

• 同步容器：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 异常，很多容器以原子方式支持一些复合操作

  • 写时复制的 List 和 Set

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

  • ConcurrentHashMap

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

  • 基于跳表 SkipList 的 Map 和 Set

    • ConcurrentHashMap 不能排序，容器类中可以排序的 Map 和 Set 是 TreeMap 和 TreeSet，但它们不是线程安全的。Java 并发包中与 TreeMap/TreeSet 对应的并发版本是ConcurrentSkipListMap 和 ConcurrentSkipListSet
    • ConcurrentSkipListMap 是基于 SkipList 实现的，SkipList 称为跳跃表或跳表，是一种底层单链表的多索引层的数据结构，主要操作复杂度是 O(log2(N))。并发版本采用跳表而不是树，是因为跳表更易于实现高效并发算法
    • ConcurrentSkipListMap 没有使用锁，所有操作都是无阻塞的，所有操作都可以并行，包括写操作。与 ConcurrentHashMap 类似，迭代器不会抛出 ConcurrentModificationException 异常，是弱一致的，也直接支持一些原子复合操作

  • 各种队列

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