在并发编程中，我们经常会用到 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 将链表锁定，再执行接下来的操作。

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

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

ConcurrentHashMap与ConcurrentSkipListMap

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

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

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

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

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

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

什么是跳跃表

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

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

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

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

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

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

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

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

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

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

总结