SkipList 跳跃表(1) ——基本介绍

本节内容:跳跃列表(也称跳表)是一种随机化数据结构,基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要$O(log\ n)$平均时间)。 基本上,跳跃列表是对有序的链表增加上附加的前进链接,增加是以随机化的方式进行的,所以在列表中的查找可以快速的跳过部分列表,因此得名,所有操作都以对数随机化的时间进行。

SkipList主要思想

对于我们熟悉的binary search来说,我们需要能够做到random access才行。但是在普通的link这种数据结构中却不能做到。而这种情况下我们有很多类似的工具比如heap,tree,b tree,red-black tree等等类似的都是来自AVL的变种。它们实现起来复杂,需要各种旋转,调整来保持平衡,此外,跳表在当前热门的开源项目中也有很多应用,比如LevelDB的核心数据结构memtable是用跳表实现的,redis的sorted set数据 结构也是有跳表实现的。

SkipList主要思想是,对于一个给定的有序链表,每隔一段数据对其进行索引,这样的索引可以建立多次,这是一种通过“空间来换取时间”的一个算法,通过在每个节点中增加了向前的指针(即层),从而提升查找的效率。

图1

如图1, 原始的链表L1是已经排好序的,但我们不能随机查找某一项,因而增加一个链表L2,这个链表跳过一些元素,减少不必要的比较。具体来说,比较次数为L2中数据的个数加上跳过的数据个数,即$L = L2 + L1/L2$, 要让L最小,需要$L2=L1/L2$,设原始链表长度为n,则总的访问次数为$2\sqrt n$.

图2

如果想继续优化,则可以在L2上再添加一个L3链表,同理可推导出$L3=L2/L3=L1/L2$时,比较次数最少$3\sqrt[3]{n}$.

假设链表有k层,访问次数为$k\sqrt[k]{n}$,取$k=\log_2 n$,得访问次数$\log_2{n} \cdot n^{\frac{1}{\log_2 n}} = 2\log_2{n}$, 相当于一颗二叉搜索树。

SkipList基本结构

基本结构

SkipList

从上图可知,跳跃表主要由以下几部分组成:

  • 表头(head):负责维护跳跃表的节点指针。
  • 跳跃表节点:保存着元素值,以及多个层。
  • 层:保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针,为了提高查找的效率,程序总是从高层先开始访问,然后随着元素值范围的缩小,慢慢降低层次。
  • 表尾:全部由 NULL 组成,表示跳跃表的末尾。

建立算法

  1. 给定一个有序的链表
  2. 选择连表中最大和最小的元素,然后从其他元素中按照一定算法(随机)随即选出一些元素,将这些元素组成有序链表。这个新的链表称为一层,原链表称为其下一层
  3. 为刚选出的每个元素添加一个指针域,这个指针指向下一层中值同自己相等的元素,Top指针指向该层首元素
  4. 重复2、3步,直到不再能选择出除最大最小元素以外的元素。