java并发容器-ConcurrentSkipListMap(跳表)

对于正常的链表来说,如果需要查找某个数据时,需要从头到尾遍历链表,效率比较低。
而跳表就同时维护了多个链表,并且这些链表是分层的,用来快速查找数据。

最底层的链表维护了跳表内所有的元素,每上面一层链表都是下面一层链表的子集,
链表越往上数据越少。

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

因为持有多个链表,也就是说使用了空间换取时间的算法。

附上一张图片,来源于网络
查找18这个元素时的查找路径

跳表.jpeg
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 除了同步控制,线程池等基本工具以外,JDK还准备了一大批好用的容器类。 1.1 并发集合 JDK提供的这些容器大部...
    AaronSimon阅读 4,599评论 0 3
  • Redis为什么用跳表而不用平衡树? 本文是《Redis内部数据结构详解》系列的第六篇。在本文中,我们围绕一个Re...
    meng_philip123阅读 9,442评论 0 26
  • Java提供的并发容器基本都在java.util.concurrent包中。比较常用的有ConcurrentHas...
    夏与清风阅读 2,890评论 0 0
  • 早上我挤上牙膏准备刷牙,一不小心,切把牙膏吞下去了,感觉凉凉的。
    李昊宇_8ebc阅读 1,170评论 0 0
  • 第一次听说 WFH 是在上家公司进第二个项目的时候。项目本身是个美国项目,团队里面的 PM,BA 和 TL 都在美...
    ForBravo阅读 14,673评论 2 3