Java ConcurrentSkipListMap 实现

简介: 本文目前只是简单地介绍了 Java 并发容器中 ConcurrentSkipListMap 的实现方式,后续会考虑拓展本文,从源码的角度进行详细的分析。

引言

本文目前只是简单地介绍了 Java 并发容器中 ConcurrentSkipListMap 的实现方式,后续会考虑拓展本文,从源码的角度进行详细的分析。所有关于 Java 并发的文章均收录于<Java并发系列文章>

ConcurrentSkipListMap

对于一个单链表,即使链表是有序的,如果我们想要在其中查找某个数据,也只能从头到尾遍历链表,这样效率自然就会很低。而跳表是在这个单链表的基础上同时维护了多个链表,并且链表是分层的。

skip-link

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

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

use-skip-link

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

使用跳表实现Map 和使用哈希算法实现Map的另外一个不同之处是:哈希并不会保存元素的顺序,而跳表内所有的元素都是排序的。因此在对跳表进行遍历时,你会得到一个有序的结果。

在 JDK 的 ConcurrentSkipListMap 实现中,没有使用到锁,而是通过 CAS 来进行数据的修改,当插入数据时,通过 CAS 修改最下层列表的内容,然后再逐层向上维护各级列表(各层列表的修改都是通过 CAS 完成),这两个过程是独立的,因为上层列表维护的数据少也只会影响查找数据的速度,而不会影响到数据的准确性,因为添加与查找数据都以最下层列表内容为准

文章说明

更多有价值的文章均收录于贝贝猫的文章目录

stun

版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!

创作声明: 本文基于下列所有参考内容进行创作,其中可能涉及复制、修改或者转换,图片均来自网络,如有侵权请联系我,我会第一时间进行删除。

参考内容

[1] linux 2.6 互斥锁的实现-源码分析
[2] 深入解析条件变量(condition variables)
[3] Linux下Condition Vairable和Mutext合用的小细节
[4] 从ReentrantLock的实现看AQS的原理及应用
[5] 不可不说的Java“锁”事
[6] 从源码层面解析yield、sleep、wait、park
[7] LockSupport中的park与unpark原理
[8] Thread.sleep、Object.wait、LockSupport.park 区别
[9] 从AQS到futex-二-JVM的Thread和Parker
[10] Java的LockSupport.park()实现分析
[11] JVM源码分析之Object.wait/notify实现
[12] Java线程源码解析之interrupt
[14] Java CAS 原理剖析
[15] 源码解析 Java 的 compareAndSwapObject 到底比较的是什么
[16] 《Java并发编程的艺术》
[17] 《实战 Java 高并发程序设计》
[18] volatile关键字深入学习
[19] 为什么Netty的FastThreadLocal速度快
[20] 线程池ThreadPoolExecutor实现原理
[21] 深入理解Java线程池:ThreadPoolExecutor
[22] ConcurrentHashMap 详解一
[23] ConcurrentHashMap 详解二
[24] JUC中Atomic class之lazySet的一点疑惑
[25] The JSR-133 Cookbook for Compiler Writers
[26] 就是要你懂Java中volatile关键字实现原理

相关文章
|
SQL 缓存 分布式计算
SparkSQL与Hive metastore Parquet转换
Spark SQL为了更好的性能,在读写Hive metastore parquet格式的表时,会默认使用自己的Parquet SerDe,而不是采用Hive的SerDe进行序列化和反序列化
SparkSQL与Hive metastore Parquet转换
|
10月前
|
前端开发 JavaScript 搜索推荐
前端小白也能学会的高大上技巧:如何让你的网页支持暗黑模式?
【10月更文挑战第30天】随着现代网页设计的发展,暗黑模式已成为一种流行趋势,提升了用户的阅读体验并增强了网页的适应性。本文介绍了如何通过简单的HTML、CSS和JavaScript实现网页的暗黑模式。首先,定义两种主题的CSS样式;然后,使用JavaScript实现模式切换逻辑,并自动检测系统主题。通过这些步骤,前端小白也能轻松掌握暗黑模式的实现,提升网页的用户体验和个性化水平。
572 4
|
11月前
|
安全 程序员 编译器
【C++篇】继承之韵:解构编程奥义,领略面向对象的至高法则
【C++篇】继承之韵:解构编程奥义,领略面向对象的至高法则
170 11
|
11月前
|
运维 API 计算机视觉
深度解密协程锁、信号量以及线程锁的实现原理
深度解密协程锁、信号量以及线程锁的实现原理
167 2
|
人工智能 运维 Devops
《AIGC+软件开发新范式》--01.当「软件研发」遇上 AI 大模型(3)
在AI 热度持续上升的当下,阿里云推出AI智能编码助手—通义灵码。通义灵码是一款基于阿里云通义代码大模型打造的智能编码助手,基于海量优秀开源代数据集和编程教科书训练,为开发者带来高效、流畅的编码体验。
280 1
|
Cloud Native 物联网 持续交付
未来科技浪潮:区块链、物联网与虚拟现实的融合创新云原生技术:重塑IT架构的未来
【5月更文挑战第31天】在信息技术飞速发展的今天,新兴技术如区块链、物联网和虚拟现实等正成为推动社会进步的重要力量。本文将探讨这些技术的发展趋势及其在各领域的应用前景,揭示它们如何相互融合,共同塑造一个智能化、互联的未来世界。 【5月更文挑战第31天】本文深入探讨了云原生技术的兴起及其对传统IT架构的颠覆性影响。通过分析云原生的核心概念,如微服务、容器化、以及持续集成/持续部署(CI/CD),文章揭示了这些技术如何促进更高效、灵活和可扩展的软件开发实践。同时,本文还讨论了企业在采用云原生技术时面临的挑战与机遇,并展望了云原生技术在未来IT领域的发展趋势。
|
存储 C语言 数据格式
用二进制方式向文件读写一组数据
用二进制方式向文件读写一组数据
126 1
|
分布式计算 DataWorks 调度
DataWorks常见问题之设置好调度时间的任务运行后查看运行日志报错如何解决
DataWorks是阿里云提供的一站式大数据开发与管理平台,支持数据集成、数据开发、数据治理等功能;在本汇总中,我们梳理了DataWorks产品在使用过程中经常遇到的问题及解答,以助用户在数据处理和分析工作中提高效率,降低难度。
182 0
|
编译器 C语言
C 输入 & 输出
C 输入 & 输出。
139 1
|
Oracle Java 关系型数据库
Java是什么?
Java是什么?
1579 0

热门文章

最新文章