阿里三面，讲讲不同场景下并发 Map 容器最优使用。凉凉送给自己

本是古典何须时尚 2023-09-30 20:42 52阅读 0赞

在并发编程中，我们经常会用到 Map 容器。Map 容器比较多，那么在不同场景下我们该如何选择最优的 Map 容器。

## 并发场景下的 Map 容器 ##

一个电商系统设计一个统计商品销量 TOP 10 的功能。一般情况下，我们是用一个哈希表来存储商品和销量键值对，然后使用排序获得销量前十的商品。在这里，哈希表是实现该功能的关键。那么请思考一下，如果要你设计这个功能，你会使用哪个容器呢？

HashMap 的性能优越，经常被用来存储键值对。那么这里我们可以使用 HashMap 吗？答案是不可以的，在并发场景下使用 HashMap。但在高并发场景下，会有数据丢失以及不准确的情况出现，这个就是容器的线程不安全表现。

为了保证容器的线程安全，Java 实现了 Hashtable、ConcurrentHashMap 以及 ConcurrentSkipListMap 等 Map 容器。

Hashtable、ConcurrentHashMap 是基于 HashMap 实现的，对于小数据量的存取比较有优势。

如果这个电商系统的商品总量不是特别大的话，我们可以用 Hashtable 或 ConcurrentHashMap 来实现哈希表的功能。

## Hashtable 与 ConcurrentHashMap ##

在数据不断地写入和删除，且不存在数据量累积以及数据排序的场景下，我们可以选用 Hashtable 或 ConcurrentHashMap。

Hashtable 使用 Synchronized 同步锁修饰了 put、get、remove 等方法，因此在高并发场景下，读写操作都会存在大量锁竞争，给系统带来性能开销。

相比 Hashtable，ConcurrentHashMap 在保证线程安全的基础上兼具了更好的并发性能。在 JDK1.8 中，ConcurrentHashMap 在添加元素时，在没有哈希冲突的情况下，会使用 CAS 进行添加元素操作；如果有冲突，则通过 Synchronized 将链表锁定，再执行接下来的操作。

![89c3f2f85a9840f3f4abe7813b356461.png][]

所以我们在设计销量 TOP10 功能时，应该首选 ConcurrentHashMap

但要注意一点，虽然 ConcurrentHashMap 的整体性能要优于 Hashtable，但在某些场景中，ConcurrentHashMap 依然不能代替 Hashtable。如果是在强一致的场景中 ConcurrentHashMap 就不适用，原因是 ConcurrentHashMap 中的 get、size 等方法没有用到锁，ConcurrentHashMap 是弱一致性的，因此有可能会导致某次读无法马上获取到写入的数据。

## ConcurrentHashMap 与 ConcurrentSkipListMap ##

同样还有一个场景，电信公司经常要提醒用户手机实时流量不足。主要的流程是服务端计算出用户实时流量，再通过手机端定时触发查询功能，如果流量不足，就弹出系统通知。

该业务的特点是用户量大，并发量高，写入多于查询操作。这时我们就需要设计一个缓存，用来存放这些用户以及对应的流量键的信息。那么假设让你来实现一个简单的缓存，你会怎么设计呢？

你可能会考虑使用 ConcurrentHashMap 容器，但是该容器在数据量比较大的时候，链表会转换为红黑树。红黑树在并发情况下，删除和插入过程中会牵涉到大量节点的移动，因此竞争锁资源的代价相对比较高。

而跳跃表的操作针对局部，需要锁住的节点少，因此在并发场景下的性能会更好一些。但是在非线程安全的 Map 容器中，我并没有看到基于跳跃表实现的 SkipListMap ？这是因为在非线程安全的 Map 容器中，基于红黑树实现的 TreeMap 在单线程中的性能表现比跳跃表要好。

因此在非线程安全的 Map 容器中，用 TreeMap 容器来存取大数据；在线程安全的 Map 容器中，用 SkipListMap 容器来存取大数据。

那么 ConcurrentSkipListMap 是如何使用跳跃表来提升存取大数据的性能呢？我们先来了解下跳跃表的实现原理。

## 什么是跳跃表 ##

跳跃表是基于链表扩展实现的一种特殊链表，类似于树的实现，跳跃表不仅实现了横向链表，还实现了垂直方向的分层索引。

一个跳跃表由若干层链表组成，每一层都实现了一个有序链表索引，只有最底层包含了所有数据，每一层由下往上依次通过一个指针指向上层相同值的元素，每层数据依次减少，等到了最顶层就只会保留部分数据了。

![ea74e1b5c560e51a9862a47f9c84fdd2.jpeg][]

跳跃表的这种结构，是利用了空间换时间的方法来提高了查询效率。程序总是从最顶层开始查询访问，通过判断元素值来缩小查询范围。我们通过以下图文信息来了解下跳跃表的具体实现原理。

首先是一个初始化的跳跃表：

数据插入键值对中的 key 分别是 3,4,5,6,7,9;每个元素插入时随机生成它的 level(这个算法很复杂，这里不详细说明)，这个 level 相当于索引层，有几个 level 就有几级索引层。

![c875fd8489dfdeb380c802b897185ee5.jpeg][]

当查询 key 值为 9 的节点时，此时查询路径为：

![62e7b1c6f8d4157bea014a44ebfa4f74.jpeg][]

![9174a612025492211be8df6a05635ca3.jpeg][]

当新增一个 key 值为 8 的节点时，首先新增一个节点到最底层的链表中，根据概率算出 level 值，再根据 level 值新建索引层，最后链接索引层的新节点。新增节点和链接索引都是基于 CAS 操作实现。

从图中我们可以看出，查找效率又有提升。当有大量的数据时，我们可以增加多级索引，其查找效率可以得到明显提升。

如果对数据有强一致要求，则需使用 Hashtable；在大部分场景通常都是弱一致性的情况下，使用 ConcurrentHashMap 即可；如果数据量在千万级别，且存在大量增删改操作，则可以考虑使用 ConcurrentSkipListMap。

Redis 使用跳跃表作为有序集合键的底层实现之一,如果一个有序集合包含的**元素数量比较多**,又或者有序集合中元素的**成员是比较长的字符串**时, Redis 就会使用跳跃表来作为有序集合健的底层实现。

## 总结 ##

![36f33c227e597e9dc5df3730fb62b864.png][]

[89c3f2f85a9840f3f4abe7813b356461.png]: https://img-blog.csdnimg.cn/img_convert/89c3f2f85a9840f3f4abe7813b356461.png
[ea74e1b5c560e51a9862a47f9c84fdd2.jpeg]: https://img-blog.csdnimg.cn/img_convert/ea74e1b5c560e51a9862a47f9c84fdd2.jpeg
[c875fd8489dfdeb380c802b897185ee5.jpeg]: https://img-blog.csdnimg.cn/img_convert/c875fd8489dfdeb380c802b897185ee5.jpeg
[62e7b1c6f8d4157bea014a44ebfa4f74.jpeg]: https://img-blog.csdnimg.cn/img_convert/62e7b1c6f8d4157bea014a44ebfa4f74.jpeg
[9174a612025492211be8df6a05635ca3.jpeg]: https://img-blog.csdnimg.cn/img_convert/9174a612025492211be8df6a05635ca3.jpeg
[36f33c227e597e9dc5df3730fb62b864.png]: https://img-blog.csdnimg.cn/img_convert/36f33c227e597e9dc5df3730fb62b864.png