20 并发容器：都有哪些“坑”需要我们填？
Java并发包有很大一部分内容都是关于并发容器的，因此学习和搞懂这部分的内容很有必要。
Java 1.5之前提供的同步容器虽然也能保证线程安全，但是性能很差，而Java 1.5版本之后提供的并发容器在性能方面则做了很多优化，并且容器的类型也更加丰富了。下面我们就对比二者来学习这部分的内容。
同步容器及其注意事项
Java中的容器主要可以分为四个大类，分别是List、Map、Set和Queue，但并不是所有的Java容器都是线程安全的。例如，我们常用的ArrayList、HashMap就不是线程安全的。在介绍线程安全的容器之前，我们先思考这样一个问题：如何将非线程安全的容器变成线程安全的容器？
在前面《12 | 如何用面向对象思想写好并发程序？》我们讲过实现思路其实很简单，只要把非线程安全的容器封装在对象内部，然后控制好访问路径就可以了。
下面我们就以ArrayList为例，看看如何将它变成线程安全的。在下面的代码中，SafeArrayList内部持有一个ArrayList的实例c，所有访问c的方法我们都增加了synchronized关键字，需要注意的是我们还增加了一个addIfNotExist()方法，这个方法也是用synchronized来保证原子性的。
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 true;
}
return false;
}
}
看到这里，你可能会举一反三，然后想到：所有非线程安全的类是不是都可以用这种包装的方式来实现线程安全呢？其实这一点不止你想到了，Java SDK的开发人员也想到了，所以他们在Collections这个类中还提供了一套完备的包装类，比如下面的示例代码中，分别把ArrayList、HashSet和HashMap包装成了线程安全的List、Set和Map。
List list = Collections.
synchronizedList(new ArrayList());
Set set = Collections.
synchronizedSet(new HashSet());
Map map = Collections.
synchronizedMap(new HashMap());
我们曾经多次强调，组合操作需要注意竞态条件问题，例如上面提到的addIfNotExist()方法就包含组合操作。组合操作往往隐藏着竞态条件问题，即便每个操作都能保证原子性，也并不能保证组合操作的原子性，这个一定要注意。
在容器领域一个容易被忽视的“坑”是用迭代器遍历容器，例如在下面的代码中，通过迭代器遍历容器list，对每个元素调用foo()方法，这就存在并发问题，这些组合的操作不具备原子性。
List list = Collections.
synchronizedList(new ArrayList());
Iterator i = list.iterator();
while (i.hasNext())
foo(i.next());
而正确做法是下面这样，锁住list之后再执行遍历操作。如果你查看Collections内部的包装类源码，你会发现包装类的公共方法锁的是对象的this，其实就是我们这里的list，所以锁住list绝对是线程安全的。
List list = Collections.
synchronizedList(new ArrayList());
synchronized (list) {
Iterator i = list.iterator();
while (i.hasNext())
foo(i.next());
}
上面我们提到的这些经过包装后线程安全容器，都是基于synchronized这个同步关键字实现的，所以也被称为同步容器。Java提供的同步容器还有Vector、Stack和Hashtable，这三个容器不是基于包装类实现的，但同样是基于synchronized实现的，对这三个容器的遍历，同样要加锁保证互斥。
并发容器及其注意事项
Java在1.5版本之前所谓的线程安全的容器，主要指的就是同步容器。不过同步容器有个最大的问题，那就是性能差，所有方法都用synchronized来保证互斥，串行度太高了。因此Java在1.5及之后版本提供了性能更高的容器，我们一般称为并发容器。
并发容器虽然数量非常多，但依然是前面我们提到的四大类：List、Map、Set和Queue，下面的并发容器关系图，基本上把我们经常用的容器都覆盖到了。
并发容器关系图
鉴于并发容器的数量太多，再加上篇幅限制，所以我并不会一一详细介绍它们的用法，只是把关键点介绍一下。
（一）List
List里面只有一个实现类就是CopyOnWriteArrayList。CopyOnWrite，顾名思义就是写的时候会将共享变量新复制一份出来，这样做的好处是读操作完全无锁。
那CopyOnWriteArrayList的实现原理是怎样的呢？下面我们就来简单介绍一下
CopyOnWriteArrayList内部维护了一个数组，成员变量array就指向这个内部数组，所有的读操作都是基于array进行的，如下图所示，迭代器Iterator遍历的就是array数组。
执行迭代的内部结构图
如果在遍历array的同时，还有一个写操作，例如增加元素，CopyOnWriteArrayList是如何处理的呢？CopyOnWriteArrayList会将array复制一份，然后在新复制处理的数组上执行增加元素的操作，执行完之后再将array指向这个新的数组。通过下图你可以看到，读写是可以并行的，遍历操作一直都是基于原array执行，而写操作则是基于新array进行。
执行增加元素的内部结构图
使用CopyOnWriteArrayList需要注意的“坑”主要有两个方面。一个是应用场景，CopyOnWriteArrayList仅适用于写操作非常少的场景，而且能够容忍读写的短暂不一致。例如上面的例子中，写入的新元素并不能立刻被遍历到。另一个需要注意的是，CopyOnWriteArrayList迭代器是只读的，不支持增删改。因为迭代器遍历的仅仅是一个快照，而对快照进行增删改是没有意义的。
（二）Map
Map接口的两个实现是ConcurrentHashMap和ConcurrentSkipListMap，它们从应用的角度来看，主要区别在于ConcurrentHashMap的key是无序的，而ConcurrentSkipListMap的key是有序的。所以如果你需要保证key的顺序，就只能使用ConcurrentSkipListMap。
使用ConcurrentHashMap和ConcurrentSkipListMap需要注意的地方是，它们的key和value都不能为空，否则会抛出NullPointerException这个运行时异常。下面这个表格总结了Map相关的实现类对于key和value的要求，你可以对比学习。
ConcurrentSkipListMap里面的SkipList本身就是一种数据结构，中文一般都翻译为“跳表”。跳表插入、删除、查询操作平均的时间复杂度是 O(log n)，理论上和并发线程数没有关系，所以在并发度非常高的情况下，若你对ConcurrentHashMap的性能还不满意，可以尝试一下ConcurrentSkipListMap。
（三）Set
Set接口的两个实现是CopyOnWriteArraySet和ConcurrentSkipListSet，使用场景可以参考前面讲述的CopyOnWriteArrayList和ConcurrentSkipListMap，它们的原理都是一样的，这里就不再赘述了。
（四）Queue
Java并发包里面Queue这类并发容器是最复杂的，你可以从以下两个维度来分类。一个维度是阻塞与非阻塞，所谓阻塞指的是当队列已满时，入队操作阻塞；当队列已空时，出队操作阻塞。另一个维度是单端与双端，单端指的是只能队尾入队，队首出队；而双端指的是队首队尾皆可入队出队。Java并发包里阻塞队列都用Blocking关键字标识，单端队列使用Queue标识，双端队列使用Deque标识。
这两个维度组合后，可以将Queue细分为四大类，分别是：
1.单端阻塞队列：其实现有ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue、LinkedTransferQueue、PriorityBlockingQueue和DelayQueue。内部一般会持有一个队列，这个队列可以是数组（其实现是ArrayBlockingQueue）也可以是链表（其实现是LinkedBlockingQueue）；甚至还可以不持有队列（其实现是SynchronousQueue），此时生产者线程的入队操作必须等待消费者线程的出队操作。而LinkedTransferQueue融合LinkedBlockingQueue和SynchronousQueue的功能，性能比LinkedBlockingQueue更好；PriorityBlockingQueue支持按照优先级出队；DelayQueue支持延时出队。
单端阻塞队列示意图
2.双端阻塞队列：其实现是LinkedBlockingDeque。
双端阻塞队列示意图
3.单端非阻塞队列：其实现是ConcurrentLinkedQueue。
4.双端非阻塞队列：其实现是ConcurrentLinkedDeque。
另外，使用队列时，需要格外注意队列是否支持有界（所谓有界指的是内部的队列是否有容量限制）。实际工作中，一般都不建议使用无界的队列，因为数据量大了之后很容易导致OOM。上面我们提到的这些Queue中，只有ArrayBlockingQueue和LinkedBlockingQueue是支持有界的，所以在使用其他无界队列时，一定要充分考虑是否存在导致OOM的隐患。
总结
Java并发容器的内容很多，但鉴于篇幅有限，我们只是对一些关键点进行了梳理和介绍。
而在实际工作中，你不单要清楚每种容器的特性，还要能选对容器，这才是关键，至于每种容器的用法，用的时候看一下API说明就可以了，这些容器的使用都不难。在文中，我们甚至都没有介绍Java容器的快速失败机制（Fail-Fast），原因就在于当你选对容器的时候，根本不会触发它。
课后思考
线上系统CPU突然飙升，你怀疑有同学在并发场景里使用了HashMap，因为在1.8之前的版本里并发执行HashMap.put()可能会导致CPU飙升到100%，你觉得该如何验证你的猜测呢？
欢迎在留言区与我分享你的想法，也欢迎你在留言区记录你的思考过程。感谢阅读，如果你觉得这篇文章对你有帮助的话，也欢迎把它分享给更多的朋友。
- 黑白尤文 👍（176） 💬（3）
Java7中的HashMap在执行put操作时会涉及到扩容，由于扩容时链表并发操作会造成链表成环，所以可能导致cpu飙升100%。
2019-04-13 - ykkk88 👍（93） 💬（6）
没有理解为什么concurrentskiplistmap比concurrenthashmap性能好
2019-04-13 - 张天屹 👍（47） 💬（2）
我理解的hashMap比其它线性容器更容易出问题是因为有扩容操作，存在更多竞态条件，所以如果条件满足时切换可能导致新生成很多数组，甚至可能出现链表闭环，这种情况可以查看堆栈，比如jstack查看会发现方法调用栈一直卡在HashMap的方法。另外上文迭代器遍历不安全是因为hasNext(size)和next()存在的竞态条件吗
2019-04-13 - WolvesLeader 👍（39） 💬（5）
个人认为您第二篇内存模型讲的非常棒，，，，，，，，，，
2019-04-13 - 龙猫 👍（35） 💬（3）
java8之前的版本hashmap执行put方法时会有环形链表的风险，java8以后改成了红黑树
2019-04-18 - CCC 👍（21） 💬（1）
老师，用跳表实现的ConcurrentSkipListMap为什么可以做到无锁并发呢
2019-04-13 - Liam 👍（20） 💬（1）
LinkedTransferQueue有什么应用场景吗？
2019-04-13 - QQ怪 👍（16） 💬（2）
除了jdk8之前因为并发导致的链表成环的问题还有一种可能是因为jdk8之前hash冲突还是使用的是链表，而jdk8之后使用了红黑树，开始还是生成链表，当链表长度为8时就会转变为红黑树，时间复杂度为O(logn),比链表效果好的多。
2019-04-13 - 罗洲 👍（14） 💬（1）
jdk1.8以前的HashMap并发扩容的时候会导致陷入死循环，所以会导致cpu飙升，那么验证猜想我觉得有2种方法： 1.线上查故障，用dump分析线程。 2.用1.8以前的jdk在本地模拟。
2019-04-13 - Randy 👍（12） 💬（3）
留言中很多都提到在JDK1.8以前会存在HashMap的并发情况下resize可能导致死循环问题，其实这个问题在1.8中也存在，并没有因为在1.8中引入了红黑树而规避掉。因为导致问题的原因是resize方法调用了transfer，也就是说是发生在链表的重组过程，跟红黑树没有关系。所以JDK1.8中还是存在这个问题 请宝令老师指正
2019-11-14 - 张申傲 👍（10） 💬（3）
老师，我有个问题： 文章里面说，使用CopyOnWriteArrayList时，需要能够容忍读写的短暂不一致，但是我理解CopyOnWriteArrayList应该不会出现不一致问题吧。因为底层的array是用volatile修饰的，根据happens-before原则，对volatile变量的写happens-before于对变量的读，也就是说如果存在并发读写的情况，写线程的setArray()一定是对读线程的getArray()可见的，所以我认为读到的始终都是最新的数据。 不知道我的理解有没有问题？
2019-05-24 - candy 👍（9） 💬（7）
老师，你好，最近两天，我线上跑的计费进程假死了(从1月11日开始跑的，4月10日第一次出现假死）， ExecutorService services = Executors.newFixedThreadPool(taskThreads); CountDownLatch cdt = new CountDownLatch(size); //一个个的处理数据 for (int j = 0; j < size; j++) { CFTask task = new CFTask(table, channelIds.get(j), batchId, cdt); services.submit(task); } cdt.await(); 这个有什么错误吗？让多个线程处理步调一致 线上jstack pid 查看 部分日志，如下：好像线程池所有线程都在等待执行，感觉一个数据库查询操作跑死了，很奇怪
2019-04-20 - 我劝你善良 👍（7） 💬（2）
老师，针对CopyOnWriteArrayList 1.如果正在遍历的时候，同时有两个写操作执行，是会顺序在一个新数组上执行写操作，还是有两个写操作分别进行？如果是两个新数组的话，那么array又将指向哪一个新数组？ 2.如果在遍历的过程中，写操作已经完成了，但是遍历尚未结束，那么是array是直接指向新数组，并继续在新数组上执行未完成的遍历，还是等待遍历完成了，再修改array的指向呢？如果在遍历完之前就修改指向，那么就会存在问题了啊！
2019-04-22 - 月月月月 👍（6） 💬（1）
老师，我想问下，文章里提到容器在遍历时要注意加锁保证线程安全，对于非线程安全的容器，我们可以通过包装让它变成线程安全的容器，然后在遍历的时候锁住集合对象。但是对于并发容器来说，在遍历的时候要怎么保证线程安全呢？如果还是锁住容器对象，但是对于不是使用synchronized去实现的并发容器，锁对象不就不一样了吗？那这样该怎么保证线程安全呢？
2019-04-19 - Sunny_Lu 👍（6） 💬（1）
感觉copyonwrite的使用限制很大，首先要容忍暂时的不一致，数据量大的情况下，写一旦多一点 不断的复制也会有性能上的问题吧？还是说多次的写用的是同一个数组呢
2019-04-17