极客时间 ——《Java并发编程实战》 20 | 并发容器：有哪些坑需要我们填

JDK 并发包中很大一部分内容都是关于并发容器的，学习和搞懂这部分内容非常有必要。

JDK 1.5 之前为了应对并发环境提供了 同步容器类，但是其核心的问题在于强制的串行化，大大降低了性能。而 Java 1.5 之后的并发容器在性能方面则做了很多优化，并且容器的类型也更加丰富，这篇文章的主要内容就是对比学习「同步容器」类和「并发容器类」。

同步容器及其注意事项：

Java容器主要分为四大类：List、Map、Set、Queue。并非所有的 Java 容器都是线程安全的。例如经常使用的 ArrayList 和 HashMap 就是非线程安全的。

那么问题来了：如何将非线程安全的容器变成线程安全的容器。

之前的文章提到过，实现思路很简单，只要将非线程安全的容器封装在对象内部，然后控制好访问路径即可。

下面的例子是将 ArrayList 进行封装创造一个线程安全的容器：

SafeArrayList<T> {
  // 类内封装一个 ArrayList 
  List<T> c = new ArrayList<>();
  // 控制访问路径
  synchronized T get(int idx) {
    return c.get(idx);
  }
  
  synchronized void add(int idx, T t) {
    c.add(idx,t);
  }
  
  synchronized boolean addIfNotExist(T t) {
    if(!c.contains(t)) {
      c.add(t);
      return ture;
    }
    return false;
  }
}

这里我们做的事情很简单，就是对访问 List 的方法都是要 synchronized 内置锁保护，还增加了一个 addIfNotExist() 方法，这个方法也通过 synchronized 保证原子性。

通过这种方式，JDK 在 Collections 类中提供了一套完备的包装了，将原本非线程安全的类通过这种方式变成了线程安全的，下面的示例代码中就将 ArrayList、HashSet、HashMao 包装成了线程安全的 List、Set和Map。

List list = Collections.
  synchronizedList(new ArrayList());
Set set = Collections.
  synchronizedSet(new HashSet());
Map map = Collections.
  synchronizedMap(new HashMap());

addIfNotExist() 是一个典型的先检查后执行方法，这种方法如果不使用同步工具的话，就会产生竞态条件，因为没有办法保证组合操作的原子性，这点需要特别注意。

还有一个容易产生竞态条件的坑是对容器的遍历迭代，例如下面的例子中，通过迭代器``遍历容器 list，对每个元素调用 foo() 方法，就存在并发问题：这些组合操作不具备原子性。【这个例子第一次接触是在《Java并发编程实战》那本书中，确实让我印象深刻，原来迭代是一个隐式的组合操作】

List list = Collections.synchronizedList(new ArrayList());
Iterator i = list.iterator();
while (i.hasNext()) {
  foo(i.next)；
}

正确的做法是下面这样，先使用 synchronized 锁住 list，保证迭代期间不会有其他线程对 list 进行修改：

List list = Collections.synchronizedList(new ArrayList());
synchronized(list) {
  Iterator i = list.iterator();
  while (i.hasNext()) {
    foo(i.next());
  }
}

Java 还提供了线程安全的容器：Vector、Stack 和 HashTable，这三个容器不是基于包装类实现的，但是同样基于 synchronized 实现的，对这三个容器遍历同样需要加锁保证互斥。

并发容器及其注意事项

JDK5 中的线程安全容器主要指的就是上面提到的同步容器。JDK 6中 Java 提供了性能更高的并发容器。

并发容器虽然数量繁多，但是其归纳起来仍然是四大类：List、Map、Set 和 Queue。

这里作者并没有详细介绍这些并发容器的用法，只提了关键点，有需要的可以去看《Java 并发编程实战》第五章，用相当大的篇幅介绍了并发容器的详细使用。

（一） List

List 中包含的并发容器实现类只有 CopyOnWriteList，它保证线程安全的方法是通过将共享变量复制一份，对其视图进行操作，这样的好处在于读操作完全无锁，性能很好。

CopyOnWriteArrayList 的内部实现原理：

CopyOnWriteArrayList 类内部维护了一个数组，成员变量 array 指向这个内部数组，所有读操作都基于 array 进行，如下图所示，迭代器 Iterator 遍历的就是 array 数组。

    /** The array, accessed only via getArray/setArray. */
    // 内部维护的保存对象的数组
    private transient volatile Object[] array;

如果在遍历 array 的同时还有一个写操作，例如增加元素，CopyOnWriteList 的处理如下：将 array 复制一份，在新复制的数组上执行增加元素的操作，然后将 array 指向这个新数组。通过下图可以看到，读写可以并行，读操作针对原 array，写操作基于新 array。

使用 CopyOnWriteList 需要注意的坑有两个方面：

使用场景，这个类仅适用于写操作非常少的场景，并且能够容忍读写短暂的不一致，就像上面示意图中所示，新写入的元素并不能立刻被遍历到。
CopyOnWriteList 迭代器只读，不支持增删改查，因为迭代器遍历的是快照，而不是原数组。

【我觉得这里还少说了一个：《JCIP》中提到过，当容器变的非常大的时候，性能会下降，因为每次新增元素都需要复制一遍数组，非常消耗性能。】

（二） Map

Map 接口的主要实现是 ConcurrentHashMap 和 ConcurrentSkipListMap。从应用角度来看，主要区别在于：ConcurrentHashMap 的 key 是无序的，而 ConcurrentSkipListMap 的 key 有序。

使用这两个类的注意事项在于它们的 key 和 value 都不能为空，否则会抛出空指针异常，下面这个表格总结了 Map 相关的实现类对于 key 和 value 的要求：

集合类	Key是否允许为null	Value是否允许为null	是否线程安全
HashMap	是	是	否
TreeMap	否	否	否
Hashtable	否	否	是
ConcurrentHashMap	否	否	是
ConcurrentSkipListMap	否	否	是

（三） Set

Set 的两个接口实现是 CopyOnWriteArraySet 和 ConcurrentSkipListSet，场景参考 List 和 Map，原理一样，不多说。

（四） Queue

JDK 并发包中的 Queue 并发容器是最复杂的，可以从两个维度进行分类：

一个维度是阻塞与非阻塞：队列满和空时，入队和出队操作是否被阻塞。
一个维度是单端与双端：单端只能从队尾入队，队首出队。双端队首队尾都可以入队出队。

JDK 并发包中阻塞队列使用 Blocking 关键字表示，单端使用 Queue 标识，双端使用 Deque 标识。

将这两个维度组合，就可以将 Queue 细分为四大类：

单端阻塞队列：
- 实现包括 ArrayBlockingQueue、LinkedBlockingQueue、SynchronounsQueue、LinkedTransferQueue、PriorityBlockingQueue、DelayQueue。这六个
- 这些类内部一般持有一个队列，这个队列可以是数组（实现可以是 ArrayBlockingQueue) 也可以是链表（实现是 LinkedBlockingQueue）还可以不持有队列（SynchronunsQueue），此时生产者线程的入队操作必须等待消费者线程的出队操作。而 LinkedTransferQueue 融合了 LinkedBlockingQueue 和 SynchronusQueue 的功能，性能比 LinkedBlockingQueue 更好。
- PriorityBlockingQueue支持按照优先级`出队
- DelayQueue 支持延时出队。