Java ConcurrentSkipListMap 实现

引言

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

ConcurrentSkipListMap

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

skip-link

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

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

use-skip-link

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

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

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

贝克街的流浪猫 wechat
您的打赏将鼓励我继续分享!
  • 本文作者: 贝克街的流浪猫
  • 本文链接: https://www.beikejiedeliulangmao.top/java/concurrent/concurrent-skip-list-map/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
  • 创作声明: 本文基于上述所有参考内容进行创作,其中可能涉及复制、修改或者转换,图片均来自网络,如有侵权请联系我,我会第一时间进行删除。