文档章节

ConcurrentSkipListMap/ConcurrentSkipListSet

Faye_Cai
 Faye_Cai
发布于 2016/07/06 16:19
字数 804
阅读 71
收藏 3

转关于ConcurrentSkipListMap 和 ConcurrentSkipListSet 的深度好文, 终于明白了skip List (跳表)的含义

http://www.cnblogs.com/skywang12345/p/3498634.html

http://www.cnblogs.com/skywang12345/p/3498556.html

 =====

ConcurrentSkipListMap介绍

ConcurrentSkipListMap是线程安全的有序的哈希表,适用于高并发的场景。
ConcurrentSkipListMap和TreeMap,它们虽然都是有序的哈希表。但是,第一,它们的线程安全机制不同,TreeMap是非线程安全的,而ConcurrentSkipListMap是线程安全的。第二,ConcurrentSkipListMap是通过跳表实现的,而TreeMap是通过红黑树实现的。
关于跳表(Skip List),它是平衡树的一种替代的数据结构,但是和红黑树不相同的是,跳表对于树的平衡的实现是基于一种随机化的算法的,这样也就是说跳表的插入和删除的工作是比较简单的。

 

ConcurrentSkipListMap原理和数据结构

ConcurrentSkipListMap的数据结构,如下图所示:

说明

先以数据“7,14,21,32,37,71,85”序列为例,来对跳表进行简单说明。

跳表分为许多层(level),每一层都可以看作是数据的索引,这些索引的意义就是加快跳表查找数据速度。每一层的数据都是有序的,上一层数据是下一层数据的子集,并且第一层(level 1)包含了全部的数据;层次越高,跳跃性越大,包含的数据越少。
跳表包含一个表头,它查找数据时,是从上往下,从左往右进行查找。现在“需要找出值为32的节点”为例,来对比说明跳表和普遍的链表。

情况1:链表中查找“32”节点
路径如下图1-02所示:

需要4步(红色部分表示路径)。

 

情况2:跳表中查找“32”节点
路径如下图1-03所示:

忽略索引垂直线路上路径的情况下,只需要2步(红色部分表示路径)。


下面说说Java中ConcurrentSkipListMap的数据结构。
(01) ConcurrentSkipListMap继承于AbstractMap类,也就意味着它是一个哈希表。
(02) Index是ConcurrentSkipListMap的内部类,它与“跳表中的索引相对应”。HeadIndex继承于Index,ConcurrentSkipListMap中含有一个HeadIndex的对象head,head是“跳表的表头”。
(03) Index是跳表中的索引,它包含“右索引的指针(right)”,“下索引的指针(down)”和“哈希表节点node”。node是Node的对象,Node也是ConcurrentSkipListMap中的内部类。

=========

ConcurrentSkipListSet介绍

ConcurrentSkipListSet是线程安全的有序的集合,适用于高并发的场景。
ConcurrentSkipListSet和TreeSet,它们虽然都是有序的集合。但是,第一,它们的线程安全机制不同,TreeSet是非线程安全的,而ConcurrentSkipListSet是线程安全的。第二,ConcurrentSkipListSet是通过ConcurrentSkipListMap实现的,而TreeSet是通过TreeMap实现的。

 

ConcurrentSkipListSet原理和数据结构

ConcurrentSkipListSet的数据结构,如下图所示:

说明
(01) ConcurrentSkipListSet继承于AbstractSet。因此,它本质上是一个集合。
(02) ConcurrentSkipListSet实现了NavigableSet接口。因此,ConcurrentSkipListSet是一个有序的集合。
(03) ConcurrentSkipListSet是通过ConcurrentSkipListMap实现的。它包含一个ConcurrentNavigableMap对象m,而m对象实际上是ConcurrentNavigableMap的实现类ConcurrentSkipListMap的实例。ConcurrentSkipListMap中的元素是key-value键值对;而ConcurrentSkipListSet是集合,它只用到了ConcurrentSkipListMap中的key!

 

本文转载自:http://www.cnblogs.com/skywang12345/p/3498634.html

Faye_Cai
粉丝 0
博文 28
码字总数 5590
作品 0
海淀
高级程序员
私信 提问
java集合之ConcurrentSkipListSet源码分析——Set大汇总

java集合之ConcurrentSkipListSet源码分析——Set大汇总 问题 (1)ConcurrentSkipListSet的底层是ConcurrentSkipListMap吗? (2)ConcurrentSkipListSet是线程安全的吗? (3)ConcurrentS...

优惠券活动
04/19
0
0
Java并发编程之JUC容器概述

今天开始学习JUC容器。JUC提供了用于多线程上下文中的Collection实现与高效的、可伸缩的、线程安全的非阻塞FIFO队列。参考JDK1.8,画出下图。 List JUC容器中List的实现只有CopyOnWriteArra...

潘威威的博客
2017/12/21
0
0
JAVA并发容器-ConcurrentSkipListMap,ConcurrentSkipListSet

ConcurrentSkipListMap其实是TreeMap的并发版本。TreeMap使用的是红黑树,并且按照key的顺序排序(自然顺序、自定义顺序),但是他是非线程安全的,如果在并发环境下,建议使用ConcurrentHas...

xiaolyuh
07/31
0
0
并发容器学习—ConcurrentSkipListMap与ConcurrentSkipListSet

一、ConcurrentSkipListMap并发容器 1.ConcurrentSkipListMap的底层数据结构 要学习ConcurrentSkipListMap,首先要知道什么是跳表或跳跃表(SkipList),跳表链表的升级版,且是有序的,另外...

宁听
04/18
11
0
3.JUC线程高级-同步容器 ConcurrentHashMap

Java5.0 在java.util.concurrent 包中提供了多种并发容器类来改进同步容器的性能。 ConcurrentHashMap 同步容器类是Java5 增加的一个线程安全的哈希表。对于多线程的操作,介于HashMap与Has...

潘天涯
2018/09/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Flink Graph生成及Hash生成分析

222

MrPei
8分钟前
1
0
[译]Android Activity 和 Fragment 状态保存与恢复的最佳实践

https://blog.csdn.net/growing_tree/article/details/53759564 https://blog.csdn.net/u013588712/article/details/54691791...

shzwork
9分钟前
1
0
调用第三方快递鸟物流单号查询接口API代码示例

最近进行网站后台开发,需要实现物流的即时查询,发现之前集成的 快递100物流查询 API ——【PHP 快递查询源码资源】 已经不能正常使用了; 为了方便以后的业务需求,经过比较,最后选择使用...

程序的小猿
16分钟前
2
0
java Poi 操作执行excel 文件中函数问题

poi 读取excel 文件,当excel 有函数时,poi直接读取返回的是excel 函数,并不能返回函数计算结果: 解决步骤: sheet.setForceFormulaRecalculation(true); 判断该列格式是否为...

早a
24分钟前
3
0
js模拟实现输入框input事件

直接修改value值是无法触发对应元素的事件的。 通过发送输入框input事件了, 可以触发。 这里简单封装了一个方法. window.inputValue = function (dom, st) { var evt = new InputEvent('i...

開援带碼
25分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部