【每日阅读】2020年10月19日-ConcurrentSkipListMap的跳表数据结构

真诚的希望您能留言与我交流,这会对我有非常大的帮助!

文章

《Java高并发程序设计 第2版》第144-146页。

新得

Java内部又一个跳表为数据结构的Map,ConcurrentSkipListMap,听名字就知道,这种Map是为了在高并发情况下使用的。

这种Map的数据结构是跳表。本文我就主要记录一下什么是跳表。

看了这个书之后,对跳表有了一定的了解。跳表的结构其实就是在链表的基础上扩充了下,使用空间换时间。并且跳表中的元素是有序的。

我们知道的链表是一根链,跳表其实就是好几条链表,然后这些链表之间是有关系的。比如一个跳表有3层链,则代表这个跳表有3层。第1层的元素最少,第1层是第2层的子集。第2层元素个数稍多,第2层是第3层的子集。第3层是满元素。然后这3层链不是完全独立的3条,其中1、2层之间,2、3层之间是有指针关联起来的。

有了上述的这种跳表,就可以加速元素的查找过程。比如下图,从上到下总共4层。

【每日阅读】2020年10月19日-ConcurrentSkipListMap的跳表数据结构

如果我们只有普通的一条链表的话(也就是最底下的那条链),那只能从左向右一个个查找元素。效率是很低的,有了跳表之后,就可以做到根据上层元素少的链表来跳过一些元素的目的。甚至如果上层链表包含我们需要的数据,还可以直接在上层链表就查找出数据,不一定需要到最底层。

总结

可以看出,跳表内看似维护了一个网状的数据结构,但其实只是链表的扩充,是多条链表组合在一起。每条链表都是有序的,高层链表是底层链表的子集。这样可以在查找过程中跳过一些元素,不用全部遍历,达到提高效率的目的。

相关文件下载地址
*该资源需回复评论后下载,马上去发表评论?
©下载资源版权归作者所有;本站所有资源均来源于网络,仅供学习使用,请支持正版!

原创文章,作者:geekgao,如若转载,请注明出处:https://www.geekgao.cn/archives/2611

发表评论

登录后才能评论
GitHub
分享本页
返回顶部