算法

数据结构:跳表

言七墨 · 12月29日 · 2019年 · 1378次已读

前言

本文主要总结下自己学习跳表时的一些笔记,主要包含跳表的由来、时空复杂度、增删改查和具体应用四个方面。

跳表的由来

二分查找的数据结构是数组,利用数组随机访问查找的时间复杂度是 O(lohttps://qimok.cngn)。如果数据结构是链表,可七墨博客以达到这样的速度吗?答案是可以的,只是需要对链表进行改造,改造之后的结构就是跳表(又名跳跃表),是一种动态数据结构,可以支持快速的插入、删除、查找、按范围查找,功能类似于红黑树,Redis 中的有序集合使用的就是跳表(后文会说)。

跳表(skiplist)

从图中可以看到, 跳跃表主要由以下部分构成:

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

其实,上面的介绍一般会在算法相关的课程中引入,不过跳表真正是由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出, 跳表以有序的方式在层次化的链表中保言七墨存元素, 效率和平衡树媲美 -> 查找、删除、添加等操作都可以在对数期望时间下完成, 并且比起平衡树来说, 七墨博客跳表的实现要简单直观得多。

跳表(skiplist)是对链表这种数据结构进行了升维操作,由原来的一维升级成二维,这样一来,占用的空间也变多了,这就是所谓的空间换时间的操作。

跳表的 时间 & 空间 复杂度

  • 时间复杂度

我们知道单链表查询的时间复杂度为 O(n),而插入、删除操作需要先找到对应的位置,所以插入、删除的时间复杂度也是 O(n)。

那么,跳表的时间复杂度是多少呢?

如果按照标准的跳表(每两个元素向上提取一个元素)来看的话,每一级索引减少 k/2 个元素(k 为其下面一级索引的个数),那么整个跳表的高度就是 logn。学习过平衡二叉树的同学都知道,它的时间复杂度与树的高度成正比,即 O(logn)。所以,跳表的时间复杂度也是 O(logn)。(这里不一步步推倒了,只要记住,查询时每次减少一半的元素的时间复杂度都是O(logn),如二叉树的查找、二分法查找、归并排序、快速排序)

  • 空间复杂度

还是以标准的跳表来分析,每两个元素向上提取一个元素,那么,最后额外需要的空间就是:

n/2 + (n/2)^2 + (n/2)^3 + … + 8 + 4 + 2 = n – 2

所以,跳表的空间复杂度是 O(n)。

跳表的增删改查

  • 查找元素

跳表允许快速查询一个有序连续元素的数据链表,它的平均查找和插入时间复杂度都是 O(logn),优于普通队列的 O(n)。快速查询是通过维护一个多层次的链表,且上层链表中的元素是下层链表元素的子集。一开始时,算法在最稀疏的层次进行搜索,直至需要查找的元素在该层两个相邻的元素中间,这时,算法将跳转到下一个层次,重复刚才的搜索,直到找到需要查找的元素为止。跳过元素的方法可以是随机性选择或确定性选择,其中前者更为常见。

  • 插入或 更新元素

由于跳表数据结构整体上是有序的,所以在插入时,需要首先查找到合适的位置,然后就是修改指针(和链表中操作类似),然后更新跳表的 level 变量。(更新同理,先找到要更新的元素,更新元素内容,并维护被更新节点的指针域和 level 变量)

  • 删除元素

和插入是相同的,首先需要查找待删除的节点,如果找到了该节点的话,那么只需要更新指针域和 level 变量。

跳表的应用(Redis 的 ZSet)

首先来对比下跳表和红黑树:

跳表会经常被用来跟平衡树,尤其是红黑树来比较,这是因为跳表和红黑树能做的事几乎相同。

  • 跳表比红黑树更容易实现
  • 跳表占用的存储空间比红黑树大,但也大不了多少
  • 查询效率而言,红黑树更稳定,但绝大多数情况下区别不大
  • 跳表数据存放是紧凑的,也就是顺序递增的,这样就非常适合范围查找,红黑树的范围查找就不怎么样了

像 Redis 中的 ZSet 数据结构是用跳表来实现的,而 JDK 中的 TreeMap 使用红黑树来实现的。

好了,主要说下跳表的具体应用:

Redis 的 ZSet 结构同时包含一个字典和一个跳表,字典保存着从 member 到 score 的映射,跳表将指向有序集的score值和member域的指针作为元素, 并以score值为索引, 对有序集元素进行排序,这两种结构通过指针共享相同元素的 member 和 score,不会浪费额外内存。

举个例子, 以下代码创建了一个带有 3 个元素的有序集:

redis> ZADD s 6 x 10 y 15 z
(integer) 3
redis> ZRANGE s 0 -1 WITHSCORES
1) "x"
2) "6"
3) "y"
4) "10"
5) "z"
6) "15"

在底层实现中, Redis 为xyz三个member分别创建了三个字符串, 值分别为double类型的61015, 然后用跳表将这些指针有序地保存起来, 形成这样一个跳跃表:

在上图中我们直接将memberscore值包含在表节点中, 但是在实际的定义中, 因为跳表要和字典分享memberscore值, 所以跳跃表只保存指向memberscore的指针。

参考

  • https://cyningsun.github.io/06-18-2018/skiplist.html
  • https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html
  • https://blog.51cto.com/14267003/2377507
0 条回应