公司网站主要几方面,广告公司网站首页设计页面,微信链接的微网站怎么做的,东营刚刚发生在并发编程中#xff0c;我们经常会用到容器。今天我要和你分享的话题就是#xff1a;在不同场景下我们该如何选择最优容器。
1、并发场景下的 Map 容器
假设我们现在要给一个电商系统设计一个简单的统计商品销量 TOP 10 的功能。常规情况下#xff0c;我们是用一个哈希表…在并发编程中我们经常会用到容器。今天我要和你分享的话题就是在不同场景下我们该如何选择最优容器。
1、并发场景下的 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 的特点是存取平均时间复杂度是 Ologn适用于大数据量存取的场景最常见的是基于跳跃表实现的数据量比较大的缓存。
回归到开始的案例再看一下如果这个电商系统的商品总量不是特别大的话我们可以用 Hashtable 或 ConcurrentHashMap 来实现哈希表的功能。
2、Hashtable ConcurrentHashMap
更精准的话我们可以进一步对比看看以上两种容器。
在数据不断地写入和删除且不存在数据量累积以及数据排序的场景下我们可以选用 Hashtable 或 ConcurrentHashMap。
Hashtable 使用 Synchronized 同步锁修饰了 put、get、remove 等方法因此在高并发场景下读写操作都会存在大量锁竞争给系统带来性能开销。
相比 HashtableConcurrentHashMap 在保证线程安全的基础上兼具了更好的并发性能。在 JDK1.7 中ConcurrentHashMap 就使用了分段锁 Segment 减小了锁粒度最终优化了锁的并发操作。
到了 JDK1.8ConcurrentHashMap 做了大量的改动摒弃了 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 是弱一致性的因此有可能会导致某次读无法马上获取到写入的数据。
3、ConcurrentHashMap ConcurrentSkipListMap
我们再看一个案例我上家公司的操作系统中有这样一个功能提醒用户手机卡实时流量不足。主要的流程是服务端先通过虚拟运营商同步用户实时流量再通过手机端定时触发查询功能如果流量不足就弹出系统通知。
该功能的特点是用户量大并发量高写入多于查询操作。这时我们就需要设计一个缓存用来存放这些用户以及对应的流量键值对信息。那么假设让你来实现一个简单的缓存你会怎么设计呢
你可能会考虑使用 ConcurrentHashMap 容器但我在 07 讲中说过该容器在数据量比较大的时候链表会转换为红黑树。红黑树在并发情况下删除和插入过程中有个平衡的过程会牵涉到大量节点因此竞争锁资源的代价相对比较高。
而跳跃表的操作针对局部需要锁住的节点少因此在并发场景下的性能会更好一些。你可能会问了在非线程安全的 Map 容器中我并没有看到基于跳跃表实现的 SkipListMap 呀这是因为在非线程安全的 Map 容器中基于红黑树实现的 TreeMap 在单线程中的性能表现得并不比跳跃表差。
因此就实现了在非线程安全的 Map 容器中用 TreeMap 容器来存取大数据在线程安全的 Map 容器中用 SkipListMap 容器来存取大数据。
那么 ConcurrentSkipListMap 是如何使用跳跃表来提升容器存取大数据的性能呢我们先来了解下跳跃表的实现原理。
3.1、什么是跳跃表
跳跃表是基于链表扩展实现的一种特殊链表类似于树的实现跳跃表不仅实现了横向链表还实现了垂直方向的分层索引。
一个跳跃表由若干层链表组成每一层都实现了一个有序链表索引只有最底层包含了所有数据每一层由下往上依次通过一个指针指向上层相同值的元素每层数据依次减少等到了最顶层就只会保留部分数据了。
跳跃表的这种结构是利用了空间换时间的方法来提高了查询效率。程序总是从最顶层开始查询访问通过判断元素值来缩小查询范围。我们可以通过以下几张图来了解下跳跃表的具体实现原理。
首先是一个初始化的跳跃表 当查询 key 值为 9 的节点时此时查询路径为 当新增一个 key 值为 8 的节点时首先新增一个节点到最底层的链表中根据概率算出 level 值再根据 level 值新建索引层最后链接索引层的新节点。新增节点和链接索引都是基于 CAS 操作实现。 当删除一个 key 值为 7 的结点时首先找到待删除结点将其 value 值设置为 null之后再向待删除结点的 next 位置新增一个标记结点以便减少并发冲突然后让待删结点的前驱节点直接越过本身指向的待删结点直接指向后继结点中间要被删除的结点最终将会被 JVM 垃圾回收处理掉最后判断此次删除后是否导致某一索引层没有其它节点了并视情况删除该层索引 。 通过以上两个案例我想你应该清楚了 Hashtable、ConcurrentHashMap 以及 ConcurrentSkipListMap 这三种容器的适用场景了。
如果对数据有强一致要求则需使用 Hashtable在大部分场景通常都是弱一致性的情况下使用 ConcurrentHashMap 即可如果数据量在千万级别且存在大量增删改操作则可以考虑使用 ConcurrentSkipListMap。
4、并发场景下的 List 容器
下面我们再来看一个实际生产环境中的案例。在大部分互联网产品中都会设置一份黑名单。例如在电商系统中系统可能会将一些频繁参与抢购却放弃付款的用户放入到黑名单列表。想想这个时候你又会使用哪个容器呢
首先用户黑名单的数据量并不会很大但在抢购中需要查询该容器快速获取到该用户是否存在于黑名单中。其次用户 ID 是整数类型因此我们可以考虑使用数组来存储。那么 ArrayList 是否是你第一时间想到的呢
我讲过 ArrayList 是非线程安全容器在并发场景下使用很可能会导致线程安全问题。这时我们就可以考虑使用 Java 在并发编程中提供的线程安全数组包括 Vector 和 CopyOnWriteArrayList。
Vector 也是基于 Synchronized 同步锁实现的线程安全Synchronized 关键字几乎修饰了所有对外暴露的方法所以在读远大于写的操作场景中Vector 将会发生大量锁竞争从而给系统带来性能开销。
相比之下CopyOnWriteArrayList 是 java.util.concurrent 包提供的方法它实现了读操作无锁写操作则通过操作底层数组的新副本来实现是一种读写分离的并发策略。我们可以通过以下图示来了解下 CopyOnWriteArrayList 的具体实现原理。 回到案例中我们知道黑名单是一个读远大于写的操作业务我们可以固定在某一个业务比较空闲的时间点来更新名单。
这种场景对写入数据的实时获取并没有要求因此我们只需要保证最终能获取到写入数组中的用户 ID 就可以了而 CopyOnWriteArrayList 这种并发数组容器无疑是最适合这类场景的了。
5、总结
在并发编程中我们经常会使用容器来存储数据或对象。Java 在 JDK1.1 到 JDK1.8 这个漫长的发展过程中依据场景的变化实现了同类型的多种容器。我将今天的主要内容为你总结了一张表格希望能对你有所帮助也欢迎留言补充。 6、思考题
在抢购类系统中我们经常会使用队列来实现抢购的排队等待如果要你来选择或者设计一个队列你会怎么考虑呢
