17 并发容器的使用：识别不同场景下最优容器
你好，我是刘超。
在并发编程中，我们经常会用到容器。今天我要和你分享的话题就是：在不同场景下我们该如何选择最优容器。
并发场景下的Map容器
假设我们现在要给一个电商系统设计一个简单的统计商品销量TOP 10的功能。常规情况下，我们是用一个哈希表来存储商品和销量键值对，然后使用排序获得销量前十的商品。在这里，哈希表是实现该功能的关键。那么请思考一下，如果要你设计这个功能，你会使用哪个容器呢？
在07讲中，我曾详细讲过HashMap的实现原理，以及HashMap结构的各个优化细节。我说过HashMap的性能优越，经常被用来存储键值对。那么这里我们可以使用HashMap吗？
答案是不可以，我们切忌在并发场景下使用HashMap。因为在JDK1.7之前，在并发场景下使用HashMap会出现死循环，从而导致CPU使用率居高不下，而扩容是导致死循环的主要原因。虽然Java在JDK1.8中修复了HashMap扩容导致的死循环问题，但在高并发场景下，依然会有数据丢失以及不准确的情况出现。
这时为了保证容器的线程安全，Java实现了Hashtable、ConcurrentHashMap以及ConcurrentSkipListMap等Map容器。
Hashtable、ConcurrentHashMap是基于HashMap实现的，对于小数据量的存取比较有优势。
ConcurrentSkipListMap是基于TreeMap的设计原理实现的，略有不同的是前者基于跳表实现，后者基于红黑树实现，ConcurrentSkipListMap的特点是存取平均时间复杂度是O（log（n）），适用于大数据量存取的场景，最常见的是基于跳跃表实现的数据量比较大的缓存。
回归到开始的案例再看一下，如果这个电商系统的商品总量不是特别大的话，我们可以用Hashtable或ConcurrentHashMap来实现哈希表的功能。
Hashtable 🆚 ConcurrentHashMap
更精准的话，我们可以进一步对比看看以上两种容器。
在数据不断地写入和删除，且不存在数据量累积以及数据排序的场景下，我们可以选用Hashtable或ConcurrentHashMap。
Hashtable使用Synchronized同步锁修饰了put、get、remove等方法，因此在高并发场景下，读写操作都会存在大量锁竞争，给系统带来性能开销。
相比Hashtable，ConcurrentHashMap在保证线程安全的基础上兼具了更好的并发性能。在JDK1.7中，ConcurrentHashMap就使用了分段锁Segment减小了锁粒度，最终优化了锁的并发操作。
到了JDK1.8，ConcurrentHashMap做了大量的改动，摒弃了Segment的概念。由于Synchronized锁在Java6之后的性能已经得到了很大的提升，所以在JDK1.8中，Java重新启用了Synchronized同步锁，通过Synchronized实现HashEntry作为锁粒度。这种改动将数据结构变得更加简单了，操作也更加清晰流畅。
与JDK1.7的put方法一样，JDK1.8在添加元素时，在没有哈希冲突的情况下，会使用CAS进行添加元素操作；如果有冲突，则通过Synchronized将链表锁定，再执行接下来的操作。
综上所述，我们在设计销量TOP10功能时，首选ConcurrentHashMap。
但要注意一点，虽然ConcurrentHashMap的整体性能要优于Hashtable，但在某些场景中，ConcurrentHashMap依然不能代替Hashtable。例如，在强一致的场景中ConcurrentHashMap就不适用，原因是ConcurrentHashMap中的get、size等方法没有用到锁，ConcurrentHashMap是弱一致性的，因此有可能会导致某次读无法马上获取到写入的数据。
ConcurrentHashMap 🆚 ConcurrentSkipListMap
我们再看一个案例，我上家公司的操作系统中有这样一个功能，提醒用户手机卡实时流量不足。主要的流程是服务端先通过虚拟运营商同步用户实时流量，再通过手机端定时触发查询功能，如果流量不足，就弹出系统通知。
该功能的特点是用户量大，并发量高，写入多于查询操作。这时我们就需要设计一个缓存，用来存放这些用户以及对应的流量键值对信息。那么假设让你来实现一个简单的缓存，你会怎么设计呢？
你可能会考虑使用ConcurrentHashMap容器，但我在07讲中说过，该容器在数据量比较大的时候，链表会转换为红黑树。红黑树在并发情况下，删除和插入过程中有个平衡的过程，会牵涉到大量节点，因此竞争锁资源的代价相对比较高。
而跳跃表的操作针对局部，需要锁住的节点少，因此在并发场景下的性能会更好一些。你可能会问了，在非线程安全的Map容器中，我并没有看到基于跳跃表实现的SkipListMap呀？这是因为在非线程安全的Map容器中，基于红黑树实现的TreeMap在单线程中的性能表现得并不比跳跃表差。
因此就实现了在非线程安全的Map容器中，用TreeMap容器来存取大数据；在线程安全的Map容器中，用SkipListMap容器来存取大数据。
那么ConcurrentSkipListMap是如何使用跳跃表来提升容器存取大数据的性能呢？我们先来了解下跳跃表的实现原理。
什么是跳跃表
跳跃表是基于链表扩展实现的一种特殊链表，类似于树的实现，跳跃表不仅实现了横向链表，还实现了垂直方向的分层索引。
一个跳跃表由若干层链表组成，每一层都实现了一个有序链表索引，只有最底层包含了所有数据，每一层由下往上依次通过一个指针指向上层相同值的元素，每层数据依次减少，等到了最顶层就只会保留部分数据了。
跳跃表的这种结构，是利用了空间换时间的方法来提高了查询效率。程序总是从最顶层开始查询访问，通过判断元素值来缩小查询范围。我们可以通过以下几张图来了解下跳跃表的具体实现原理。
首先是一个初始化的跳跃表：
当查询key值为9的节点时，此时查询路径为：
当新增一个key值为8的节点时，首先新增一个节点到最底层的链表中，根据概率算出level值，再根据level值新建索引层，最后链接索引层的新节点。新增节点和链接索引都是基于CAS操作实现。
当删除一个key值为7的结点时，首先找到待删除结点，将其value值设置为null；之后再向待删除结点的next位置新增一个标记结点，以便减少并发冲突；然后让待删结点的前驱节点直接越过本身指向的待删结点，直接指向后继结点，中间要被删除的结点最终将会被JVM垃圾回收处理掉；最后判断此次删除后是否导致某一索引层没有其它节点了，并视情况删除该层索引 。
通过以上两个案例，我想你应该清楚了Hashtable、ConcurrentHashMap以及ConcurrentSkipListMap这三种容器的适用场景了。
如果对数据有强一致要求，则需使用Hashtable；在大部分场景通常都是弱一致性的情况下，使用ConcurrentHashMap即可；如果数据量在千万级别，且存在大量增删改操作，则可以考虑使用ConcurrentSkipListMap。
并发场景下的List容器
下面我们再来看一个实际生产环境中的案例。在大部分互联网产品中，都会设置一份黑名单。例如，在电商系统中，系统可能会将一些频繁参与抢购却放弃付款的用户放入到黑名单列表。想想这个时候你又会使用哪个容器呢？
首先用户黑名单的数据量并不会很大，但在抢购中需要查询该容器，快速获取到该用户是否存在于黑名单中。其次用户ID是整数类型，因此我们可以考虑使用数组来存储。那么ArrayList是否是你第一时间想到的呢？
我讲过ArrayList是非线程安全容器，在并发场景下使用很可能会导致线程安全问题。这时，我们就可以考虑使用Java在并发编程中提供的线程安全数组，包括Vector和CopyOnWriteArrayList。
Vector也是基于Synchronized同步锁实现的线程安全，Synchronized关键字几乎修饰了所有对外暴露的方法，所以在读远大于写的操作场景中，Vector将会发生大量锁竞争，从而给系统带来性能开销。
相比之下，CopyOnWriteArrayList是java.util.concurrent包提供的方法，它实现了读操作无锁，写操作则通过操作底层数组的新副本来实现，是一种读写分离的并发策略。我们可以通过以下图示来了解下CopyOnWriteArrayList的具体实现原理。
回到案例中，我们知道黑名单是一个读远大于写的操作业务，我们可以固定在某一个业务比较空闲的时间点来更新名单。
这种场景对写入数据的实时获取并没有要求，因此我们只需要保证最终能获取到写入数组中的用户ID就可以了，而CopyOnWriteArrayList这种并发数组容器无疑是最适合这类场景的了。
总结
在并发编程中，我们经常会使用容器来存储数据或对象。Java在JDK1.1到JDK1.8这个漫长的发展过程中，依据场景的变化实现了同类型的多种容器。我将今天的主要内容为你总结了一张表格，希望能对你有所帮助，也欢迎留言补充。
思考题
在抢购类系统中，我们经常会使用队列来实现抢购的排队等待，如果要你来选择或者设计一个队列，你会怎么考虑呢？
期待在留言区看到你的见解。也欢迎你点击“请朋友读”，把今天的内容分享给身边的朋友，邀请他一起学习。
- 晓杰 👍（49） 💬（3）
可以用ConcurrentLinkedQueue，优势如下： 1、抢购场景一般都是写多读少，该队列基于链表实现，所以新增和删除元素性能较高 2、写数据时通过cas操作，性能较高。 但是LinkedQueue有一个普遍存在的问题，就是该队列是无界的，需要控制容量，否则可能引起内存溢出
2019-06-28 - 东方奇骥 👍（30） 💬（7）
如果数据变动频繁，就不建议使用CopyOnWriteArrayList了，因为每次写都要拷贝一份，代价太大。老师，怎么直观理解强一致性和弱一致性？之前一直觉得ConcurrentHashMap就是用来代替HashTable的，因为HashTable并发时因为同步锁性能差。
2019-06-27 - 学无涯 👍（27） 💬（7）
为什么ConcurrentHashMap和HashTable的key和value不能为空，而HashMap却可以，这么设计的原因是什么呢
2019-11-12 - undifined 👍（14） 💬（1）
抢购的过程中存在并发操作，所以需要用线程安全的容器，同时，抢购的用户会很多，应当使用链表的数据结构，这种场景往往是写多读少，还需要排队，所以 ConcurrentLinkedQueue应该是最合适的
2019-06-27 - 天天向上 👍（7） 💬（1）
ConcurrentHashMap 是弱一致性的，因此有可能会导致某次读无法马上获取到写入的数据。这句话不理解啊，为什么会无法马上获取到写入的数据呢？又不像mysql那样存在事务隔离。
2020-04-26 - 大雁小鱼 👍（7） 💬（1）
老师，ConcurrentHashMap为啥是弱一致性的？
2019-06-27 - 陆离 👍（6） 💬（1）
这一节要是有Queue就更好了，那几个blockingQueue还是很有意思的
2019-06-27 - WL 👍（5） 💬（3）
请问一下老师两个问题: 1. 为什么在无锁是红黑树和跳表的性能差不多呢, 红黑树再平衡的操作会不会更复杂一些. 2. 从本篇文章看好像ConcurrentSkipListMap的性能比ConcurrentHashMap性能要好, 那为啥平时还是用后者的人更多呢, 我想很定是后者相对前者也有一定的优势吧, 但我自己没想出来, 老师能不能指点一下是啥优势.
2019-06-27 - Liam 👍（4） 💬（1）
老师，我有2个问题: 1 top 10 问题涉及到排序, 我感觉用优先级队列或带排序功能的ConcurrentSkipListMap更合适？ConcurrentHashMap不支持排序吧 2 CopyOnWrite的list为什么还要加锁呢，副本不是线程独享的吗？
2019-06-27 - 学无涯 👍（2） 💬（2）
老师，我的意思是Unsafe#compareAndSetObject和Unsafe#getObjectVolatile方法，这两个方法的volatile语义可以保证数组元素的可见性。这样即使新增一个node，这俩方法也可以保证其他线程可以读到。还是说我对这两个方法有误解，请老师解惑！
2019-11-13 - 学无涯 👍（2） 💬（1）
老师，1.7ConcurrentHashMap弱一致性我理解，但是1.8为什么呀，1.8使用CAS可以保证可见性吧
2019-11-12 - 脱缰的野马__ 👍（1） 💬（2）
老师您好，黑名单的案例为什么不用线程安全的map啊，这样便于查询吧，如果总链表，要查询某个用户是否在黑名单不是要遍历整个链表吗？
2020-03-27 - 小笨蛋 👍（1） 💬（1）
我有个疑问，你有提到ConcurrntHashMap里面数据量比较大的情况下会有很多的红黑树的转化操作，但是据我了解Java里面的Hash算法是采用的分散很好的Time33算法，这份hash还是很均匀的，应该不会出现大量的红黑树的转化工作。能麻烦老师解答一下吗？
2019-08-25 - Eaglet 👍（1） 💬（1）
老师，top10的问题，你说：在数据不断地写入和删除，且不存在数据量累积以及数据排序的场景，可以选用 CurrentHashMap。可是top10问题有排序，数据量也在实时的累积，感觉用 CurrentHashMap 也不是最合适吧？这里不太懂，请老师解释下我是否对 top10这个问题本身理解有问题。
2019-07-28 - Lambor 👍（0） 💬（1）
老师，您好！一直有个疑惑，现在基本都是微服务架构，服务都是多实例运行，例如黑名单那个场景，数据应该不是直接使用 CopyOnWriteArrayList 保存在内存中的，这样多个实例的数据可能不一致，而是用 redis 这类中间件保存起来，服务中每次查询黑名单时从 redis 查询，写入应该也是写入到 redis 的。所以这个场景使用 CopyOnWriteArrayList 我不知道是不是能满足实际的业务需求。还望解答。
2020-03-19