动力节点旗下在线教育品牌  |  咨询热线:400-8080-105 学Java全栈,上蛙课网
首页 > 文章

跳表的原理及其在JDK中的实现

06-23 18:18 245浏览
举报 T字号
  • 大字
  • 中字
  • 小字

实际上,JDK并发包中有很多的数据结构,最常用的有链表,哈希表等等,除了这些数据结构之外,还有一种特殊的数据结构跳表,可能大多数人都不太了解,故本文主要介绍跳表的原理以及在JDK中的实现

跳表Skip list)是一种可以代替平衡树的随机化的数据结构,基于并联的链表,默认是按照Key值升序的。Skip list让已排序的数据分布在多层链表中,以0-1随机数决定一个数据的向上攀升与否,通过“空间来换取时间”的一个算法,在每个节点中增加了向前的指针,在插入、删除、查找时可以忽略一些不可能涉及到的结点,从而提高了效率。

跳表实际上是链表的一种,只不过它在链表的基础上增加了跳跃功能,正是这个跳跃的功能,使得在查找元素时,跳表能够提供O(log n)的时间复杂度。红黑树等这样的平衡数据结构查找的时间复杂度也是O(log n),并且相对于红黑树这样的平衡二叉树skiplist的优点是更好的支持并发操作,但是要实现像红黑树这样的数据结构并非易事,但是只要你熟悉链表的基本操作,再加之对跳表原理的理解,实现一个跳表数据结构就是一个很自然的事情了。从概率上保持数据结构的平衡比显示的保持数据结构平衡要简单的多。对于大多数应用,用  Skip list要比用树算法相对简单。由于Skip list比较简单,实现起来会比较容易,虽然和平衡树有着相同的时间复杂度(O(logn)),但是skip list的常数项会相对小很多。Skip list在空间上也比较节省。一个节点平均只需要1.333个指针(甚至更少)。

那么跳表具体的结构到底是怎么样的呢?下图是跳表数据结构的原理图:

可以明显看到,跳表就是一种典型的以空间换时间的数据结构。跳表的算法与哈希算法的另一个区别就是:哈希算法不会保存数据的顺序,而跳表内的所有元素都是排序的。因此对于跳表进行遍历会得到一组有序的数据。

JDK内部,也使用了这种便利的数据结构比如:

ConcurrentSkipListMap,ConcurrentSkipListSet等。下面我们主要介绍ConcurrentSkipListMap。说到ConcurrentSkipListMap,我们就应该比较HashMap,ConcurrentHashMap,ConcurrentSkipListMap这三个类来讲解。它们都是以键值对的方式来存储数据的。HashMap是线程不安全的,而ConcurrentHashMap和ConcurrentSkipListMap是线程安全的,它们内部都使用无锁CAS算法实现了同步。ConcurrentHashMap中的元素是无序的,ConcurrentSkipListMap中的元素是有序的。它们三者的具体区别可以参考具体的资料,下面主要讲解ConcurrentSkipListMap的实现原理。

理解了跳表的原理,ConcurrentSkipListMap的原理不难理解,在它的内部有几个重要的数据结构,首先是Node,一个Node表示一个节点,里面含有两个重要的元素key和value,还有一个next指向Node的节点表示下一个节点。

 

对于Node的所有方法,使用了CAS方法,因此是线程安全的。

上面两个方法一个是设置value,另一个是设置next的,具体实现可以查看源代码。

 

另外一个重要的数据结构就是Index,从上面跳表的结构可以看出,我们需要知道要一个元素在哪一层,哪一个节点,因此都需要Index来管理。

Index中封装了Node,并且有一个向右和向下的引用。此外,还有一个数据结构也很重要,HeadIndex,它记录每一层的表头处于哪一层,它继承自Index。

上面就简单介绍完了ConcurrentSkipListMap的内部重要数据结构,重点是了解跳表数据结构,理解跳表是掌握ConcurrentSkipListMap的关键。

跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。相信我们在看完本文以后,对跳表的了解也更深了一个层次,对这种数据结构的运用也更加得心应手,在以后的编程和运算中能够用的恰到好处。

0人推荐
共同学习,写下你的评论
0条评论
HHADA
程序员HHADA

3篇文章贡献16991字

作者相关文章更多>

推荐相关文章更多>

Java数据结构

HelloWorld10-31 08:24

浅谈MySQL中SQL优化的常用方法

军哥08-12 23:29

五分钟读懂UML类图

江湖人称小李白12-10 10:41

MyBatis开发框架的四大核心

IT逐梦者08-17 21:43

一次搞定continue,break和return

HelloWorld11-06 11:19

发评论

举报

0/150

取消