专栏首页happyJaredConcurrentSkipListMap

ConcurrentSkipListMap

为了引出 ConcurrentSkipListMap,先来简单理解下什么是跳表。

对于单链表,即使链表是有序的,如果想要在其中查找某个数据,也只能从头到尾遍历链表,这样效率自然就会很低,跳表就不一样了。跳表是一种可以用来快速查找的数据结构,有点类似于平衡树。它们都可以对元素进行快速的查找。但一个重要的区别是:对平衡树的插入和删除往往很可能导致平衡树进行一次全局的调整;而对跳表的插入和删除,只需要对整个数据结构的局部进行操作即可。这样带来的好处是:在高并发的情况下,需要一个全局锁,来保证整个平衡树的线程安全;而对于跳表,则只需要部分锁即可。这样,在高并发环境下,就可以拥有更好的性能。就查询的性能而言,跳表的时间复杂度是 O(logn), 所以在并发数据结构中,JDK 使用跳表来实现一个 Map。

跳表的本质,是同时维护了多个链表,并且链表是分层的

2级索引跳表

最低层的链表,维护了跳表内所有的元素,每上面一层链表,都是下面一层的子集。

跳表内所有链表的元素都是排序的。查找时,可以从顶级链表开始找。一旦发现被查找的元素大于当前链表中的取值,就会转入下一层链表继续找。这也就是说在查找过程中,搜索是跳跃式的。如上图所示,在跳表中查找元素18。

在跳表中查找元素18

查找18 的时候,原来需要遍历 18 次,现在只需要 7 次即可。针对链表长度比较大的时候,构建索引,查找效率的提升就会非常明显。

从上面很容易看出,跳表是一种利用空间换时间的算法

使用跳表实现 Map,和使用哈希算法实现 Map 的另外一个不同之处是:哈希并不会保存元素的顺序,而跳表内所有的元素都是排序的。因此,在对跳表进行遍历时,你会得到一个有序的结果。所以,如果你的应用需要有序性,那么跳表就是你不二的选择,JDK 中实现这一数据结构的类是 ConcurrentSkipListMap

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • ConcurrentSkipListMap原理

    为了引出 ConcurrentSkipListMap,先带着大家简单理解一下跳表。

    黑洞代码
  • 跳表(SkipList) 和 ConcurrentSkipListMap

    对于单链表,即使链表是有序的,如果想要在其中查找某个数据,也只能从头到尾遍历链表,这样效率自然就会很低,跳表就不一样了。跳表是一种可以用来快速查找的数据结构,有...

    JMCui
  • ConcurrentSkipListMap跳表原理解析

    内部结构如下(图片来源于网络),这里面Node其实就是HeadIndex中的level1,level2,level3中的一个个绿点。

    算法之名
  • SkipList和java中ConcurrentSkipListMap的实现

    一开始听说SkipList我是一脸懵逼的,啥?还有SkipList?这个是什么玩意。

    子润先生
  • 【死磕Java并发】-----J.U.C之Java并发容器:ConcurrentSkipListMap

    到目前为止,我们在Java世界里看到了两种实现key-value的数据结构:Hash、TreeMap,这两种数据结构各自都有着优缺点。 Hash表:插入、查找最...

    用户1655470
  • 基于跳跃表的 ConcurrentSkipListMap 内部实现(Java 8)

    我们知道 HashMap 是一种键值对形式的数据存储容器,但是它有一个缺点是,元素内部无序。由于它内部根据键的 hash 值取模表容量来得到元素的存储位置,所以...

    Single
  • 死磕 java集合之ConcurrentSkipListMap源码分析——发现个bug

    (3)HeadIndex,头索引节点,继承自Index,并扩展一个level字段,用于记录索引的层级;

    彤哥
  • 聊聊java中的哪些Map:(八)ConcurrentSkipListMap源码分析

    ConcurrentSkipListMap也是java并发包下面的重要容器,其类的继承结构如下:

    冬天里的懒猫
  • 跳表(skiplist)的原理及concurrentskiplistmap的源码学习

    本文分为两个部分,第一个是对跳表(SKipList)这种数据结构的介绍,第二部分则是对Java中ConcurrentSkilListMap的源码解读.

    呼延十

扫码关注云+社区

领取腾讯云代金券