内容简介:大家想必都知道,数组和链表的搜索操作的时间复杂度都是O(N)的,在数据量大的时候是非常耗时的。对于数组来说,我们可以先排序,然后使用二分搜索,就能够将时间复杂度降低到O(logN),但是有序数组的插入是一个O(N)级别的操作。而链表的插入性能相对优秀,却不能使用二分搜索快速查询。那么是否有一种数据结构,即能够像链表一样快速插入数据,又支持类似于二分搜索这样的查询算法呢?答案是肯定的。William Pugh教授在1990发表的论文跳表的核心思想是通过建立索引层来缩短链表的搜索路径,以达到快速搜索的目的。假设
大家想必都知道,数组和链表的搜索操作的时间复杂度都是O(N)的,在数据量大的时候是非常耗时的。对于数组来说,我们可以先排序,然后使用二分搜索,就能够将时间复杂度降低到O(logN),但是有序数组的插入是一个O(N)级别的操作。而链表的插入性能相对优秀,却不能使用二分搜索快速查询。那么是否有一种数据结构,即能够像链表一样快速插入数据,又支持类似于二分搜索这样的查询算法呢?答案是肯定的。William Pugh教授在1990发表的论文 《Skip Lists: A Probabilistic Alternative to Balanced Trees》 中提出的跳表就是这样一种有趣的数据结构。
跳表的结构
跳表的核心思想是通过建立索引层来缩短链表的搜索路径,以达到快速搜索的目的。
假设我们从链表中的每两个节点中提取出一个建立一级索引,然后再从每两个一级索引中提取一个建立二级索引,以此类推,就可以得到如下图所示的结构,其中绿色节点表示索引。
在William Pugh的论文中使用了数组加链表的组合来实现跳表,就如上图所示,每一列索引具有相同的key,使用一个数组来表示。还可以使用纯链表的形式来实现跳表,我觉得这种方式更有助于理解跳表的原理,如下图所示。
跳表的搜索
跳表的搜索需要从高层索引开始向下逐层搜索,每一层的搜索方式和普通链表是一样的,当后继节点的关键字大于搜索关键字时结束本层的搜索,进入下一层继续搜索。下图展示了跳表搜索关键字 22 的过程,其中红色部分就是搜索的路径。
从上图可以很直观的看出,跳表的搜索和二分搜索是一样的,其时间复杂度也是O(logN)的,我们不妨简单证明一下。
假设跳表中有N个数据节点(关键字),每m个低级索引(或数据节点)中提取出一个作为高级索引,那么
一级索引的数量 二级索引的数量 三级索引的数量 以此类推,第i级索引的数量 最高级索引的数量 所以索引的最大层级 每一层的搜索次数 所以跳表的搜索次数因为m是一个常量,因此跳表的搜索时间复杂度是O(logN)的
跳表的多层索引结构使它的搜索方式非常灵活且强大
比如我们可能有这样的需求,如果key不存在,我们需要知道这个key邻近的nearKey是什么,这用跳表很容易实现
- 搜索比key小且最接近key的关键字lowerKey,如上图所示,后继节点大于等于key时,直接返回当前节点即可
- 搜索比key大且最接近key的关键字higherKey,如上图所示,后继节点大于key时,直接返回后继节点即可
跳表还可以很容易的搜索一个关键字区间 [fromKey, toKey]
,这点和B+树很类似,先搜索fromKey,然后向后遍历链表,取出所有小于等于toKey的数据即可
跳表的插入
到现在为止,本文描述的都是理想状态下的跳表,事实上,我们不会严格的为跳表的每m个低级索引建立高级索引,因为这样做复杂而且低效。所以William Pugh在他的论文中采用一种随机算法来为每个新增的节点随机建立索引,下面是我用 Java 实现的版本。
int randomLevel(int m, int maxLevel) { ThreadLocalRandom r = ThreadLocalRandom.current(); int level = 1; while (r.nextInt(m) == 0 && level < maxLevel) level++; return level; } 复制代码
,这正好符合我们前面提到的索引层的性质。
Doug Lea大佬在Java的ConcurrentSkipListMap
中使用了另外一种更加炫酷的随机算法的实现方式,使用随机数末尾连续为1的位数作为索引的等级,显然这种方式生成第i级索引的概率为
,代码如下所示。
int rn = ThreadLocalRandom.current().nextInt(); // 只有最高位和最低位都为0时,才建立索引,相当于为4个node建立一个索引 if ((rn & 0x80000001) == 0) { int level = 1; // 建立索引的等级等于rn末尾连续为1的位数 while (((rn >>>= 1) & 1) != 0) level++; } 复制代码
通过随机函数生成一个随机的索引等级之后,创建一个新的索引列,并将每一层的新索引链接到它的前驱索引的后面,如果生成的随机等级大于当前跳表的最大索引等级,需要添加一层新的索引。如下图所示,其中红色虚线箭头表示重新建立的链接。
跳表的删除
跳表的删除操作比较简单,先查询删除的关键字,如果在索引层匹配到了关键字,就向下删除所有的索引和数据节点,如果没有匹配到索引,只需要删除数据节点即可。其中有一点需要注意的是,在删除索引后需要检测一下,如果当前层的HEAD索引的后继索引为NIL,则表示这一层已经没有索引了,需要删除这个索引层。如下图所示,红色箭头表示重新建立的链接。
跳表的实现
跳表的实现相对AVL树、红黑树等平衡二叉树来说简单了很多,William Pugh的论文 《Skip Lists: A Probabilistic Alternative to Balanced Trees》 中提供了使用数组加链表实现跳表的伪代码,我写了一个Java版本的纯链表实现的跳表,并上传到了 我的GitHub 上,有兴趣的朋友可以看一下。如果你需要在开发中使用跳表的话, java.util.concurrent.ConcurrentSkipListMap
是一个强大的实现,而且它还是线程安全的。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- 数据结构 – 用于构建文件系统的数据结构?
- 荐 用Python解决数据结构与算法问题(三):线性数据结构之栈
- 数据结构和算法面试题系列-C指针、数组和结构体
- 请问二叉树等数据结构的物理存储结构是怎样的?
- 数据结构——单链表
- 常用数据结构
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
锋利的jQuery
单东林、张晓菲、魏然 / 人民邮电出版社 / 2009-6 / 39.00元
《锋利的jQuery》循序渐进地对jQuery的各种函数和方法调用进行了介绍,读者可以系统地掌握jQuery的DOM操作、事件监听和动画、表单操作、AJAX以及插件方面等知识点,并结合每个章节后面的案例演示进行练习,达到掌握核心知识点的目的。为使读者更好地进行开发实践,《锋利的jQuery》的最后一章将前7章讲解的知识点和效果进行了整合,打造出一个非常有个性的网站,并从案例研究、网站材料、网站结构......一起来看看 《锋利的jQuery》 这本书的介绍吧!