数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

17 | 跳表:为什么Redis一定要用跳表来实现有序集合?

王争 2018-10-29
上两节我们讲了二分查找算法。当时我讲到,因为二分查找底层依赖的是数组随机访问的特性,所以只能用数组来实现。如果数据存储在链表中,就真的没法用二分查找算法了吗?
实际上,我们只需要对链表稍加改造,就可以支持类似“二分”的查找算法。我们把改造之后的数据结构叫作跳表(Skip list),也就是今天要讲的内容。
跳表这种数据结构对你来说,可能会比较陌生,因为一般的数据结构和算法书籍里都不怎么会讲。但是它确实是一种各方面性能都比较优秀的动态数据结构,可以支持快速的插入、删除、查找操作,写起来也不复杂,甚至可以替代红黑树(Red-black tree)。
Redis 中的有序集合(Sorted Set)就是用跳表来实现的。如果你有一定基础,应该知道红黑树也可以实现快速的插入、删除和查找操作。那 Redis 为什么会选择用跳表来实现有序集合呢? 为什么不用红黑树呢?学完今天的内容,你就知道答案了。

如何理解“跳表”?

对于一个单链表来讲,即便链表中存储的数据是有序的,如果我们要想在其中查找某个数据,也只能从头到尾遍历链表。这样查找效率就会很低,时间复杂度会很高,是 O(n)。
那怎么来提高查找效率呢?如果像图中那样,对链表建立一级“索引”,查找起来是不是就会更快一些呢?每两个结点提取一个结点到上一级,我们把抽出来的那一级叫作索引索引层。你可以看我画的图。图中的 down 表示 down 指针,指向下一级结点。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(170)

  • 张先生
    为什么评论区的都这么优秀,为什么我这么菜,我该怎么办😱
    2018-11-26
    11
    246
  • leo
    跳表是我非常喜欢的数据结构,之前写过一篇文章,希望大家斧正(https://cloud.tencent.com/developer/article/1353762)。另外,严格来讲,Redis的对象系统中的每种对象实际上都是基于使用场景选择多种底层数据结构实现的,比如ZSET就是基于【压缩列表】或者【跳跃表+字典】(这也跟之前排序中提到的Sort包实现的思想一样,基于数据规模选择合适的排序算法),体现了Redis对于性能极致的追求。

    作者回复: 👍

    2018-10-29
    1
    141
  • Liam
    看了下老师github上的实现(java版本),不是很理解,尤其是数组Node forward[]的作用,能多加些注释或讲解一下吗
    2018-10-29
    1
    78
  • 董航
    redis有序集合是跳跃表实现的,直接这么说有失偏驳,他是复合数据结构,准确说应该是由一个双hashmap构成的字典和跳跃表实现的,不知道我说的有问题吗😊

    作者回复: 后面还会讲 你说的没错 👍

    2018-10-29
    1
    48
  • escray
    如果每三个或者五个节点提取一个节点作为上级索引,那么对应的查询数据时间复杂度,应该也还是 O(logn)。

    假设每 5 个节点提取,那么最高一层有 5 个节点,而跳表高度为 log5n,每层最多需要查找 5 个节点,即 O(mlogn) 中的 m = 5,最终,时间复杂度为 O(logn)。

    空间复杂度也还是 O(logn),虽然省去了一部分索引节点,但是似乎意义不大。

    不知道在一般的生产系统,跳表的提取是按照多少个节点来实现?还是每个系统根据实际情况,都不一样。

    看了跳表的 Java 实现,查找部分的代码真是漂亮,插入部分看了半天才看明白。

    作者回复: 👍

    2018-10-29
    2
    42
  • 姜威
    总结:
    一、什么是跳表?
    为一个值有序的链表建立多级索引,比如每2个节点提取一个节点到上一级,我们把抽出来的那一级叫做索引或索引层。如下图所示,其中down表示down指针,指向下一级节点。以此类推,对于节点数为n的链表,大约可以建立log2n-1级索引。像这种为链表建立多级索引的数据结构就称为跳表。
    二、跳表的时间复杂度?
    1.计算跳表的高度
    如果链表有n个节点,每2个节点抽取抽出一个节点作为上一级索引的节点,那第1级索引的节点个数大约是n/2,第2级索引的节点个数大约是n/4,依次类推,第k级索引的节点个数就是n/(2^k)。假设索引有h级别,最高级的索引有2个节点,则有n/(2^h)=2,得出h=log2n-1,包含原始链表这一层,整个跳表的高度就是log2n。
    2.计算跳表的时间复杂度
    假设我们在跳表中查询某个数据的时候,如果每一层都遍历m个节点,那在跳表中查询一个数据的时间复杂度就是O(m*logn)。那这个m是多少呢?如下图所示,假设我们要查找的数据是x,在第k级索引中,我们遍历到y节点之后,发现x大于y,小于后面的节点z,所以我们通过y的down指针,从第k级下降到第k-1级索引。在第k-1级索引中,y和z之间只有3个节点(包含y和z),所以,我们在k-1级索引中最多只需要遍历3个节点,以此类推,每一级索引都最多只需要遍历3个节点。所以m=3。因此在跳表中查询某个数据的时间复杂度就是O(logn)。
    三、跳表的空间复杂度及如何优化?
    1.计算索引的节点总数
    如果链表有n个节点,每2个节点抽取抽出一个节点作为上一级索引的节点,那每一级索引的节点数分别为:n/2,n/4,n/8,…,8,4,2,等比数列求和n-1,所以跳表的空间复杂度为O(n)。
    2.如何优化时间复杂度
    如果链表有n个节点,每3或5个节点抽取抽出一个节点作为上一级索引的节点,那每一级索引的节点数分别为(以3为例):n/3,n/9,n/27,…,27,9,3,1,等比数列求和n/2,所以跳表的空间复杂度为O(n),和每2个节点抽取一次相比,时间复杂度要低不少呢。
    四、高效的动态插入和删除?
    跳表本质上就是链表,所以仅插作,插入和删除操时间复杂度就为O(1),但在实际情况中,要插入或删除某个节点,需要先查找到指定位置,而这个查找操作比较费时,但在跳表中这个查找操作的时间复杂度是O(logn),所以,跳表的插入和删除操作的是时间复杂度也是O(logn)。
    五、跳表索引动态更新?
    当往跳表中插入数据的时候,可以选择同时将这个数据插入到部分索引层中,那么如何选择这个索引层呢?可以通过随机函数来决定将这个节点插入到哪几级索引中,比如随机函数生成了值K,那就可以把这个节点添加到第1级到第K级索引中。
    2018-10-31
    1
    31
  • 小情绪
    王老师:跳表的思想讲的非常好,但是我总觉得应该把跳表的具体实现讲一下吧,毕竟来这里的大部分算法能力不是很强,而跳表的实现还是有一定难度的。
    2018-11-29
    25
  • 德尼
    看评论很多人说对github的代码不理解,我来说下自己的理解吧。整个代码的实现思想就是老师说的那样。每个节点的forward里存的是当前节点的所有索引层的下一跳,forward[ 0 ]对应的是原链表里的下一跳,forward[ 1 ]是最后一层节点的下一跳位置,以此类推,也就是说访问head的forward[ levelCount-1 ]表示第一层索引的头结点。head是一个头结点,它的forward里存的是原链表以及索引层的头结点。
    2018-12-09
    20
  • MG
    王老师的Java实现版本,有几个关键点理解到了,基本上就明白是怎么实现的了:
    1.每次插入数据的时候随机产生的level:决定了新节点的层数;
    2.数组update的作用:用以存储新节点所有层数上,各自的前一个节点的信息;
    3.节点内的forwards数组:用以存储该节点所有层的下一个节点的信息;
    4.当所有节点的最大层级变量maxlevel=1的时候,跳表退化成一个普通链表
    2018-12-25
    17
  • k
    看了下留言 好像有人对等比数列求和有想法 老师的n-2并不是估算解 是精确解
    n/2, n/4, .., 2 这个数列中一共有log2(n/2)项
    套进等比数列求和公式
    S = a0(1-q^n)/(1-q), 其中a0表示首项,n表示项数
    这里的a0=n/2, 项数=log2(n/2), q=1/2
    S = n/2(1-2/n)/(1-1/2) = n-2
    2018-11-20
    1
    10
  • 許敲敲
    我是机械行业打算换行的,不知道应该怎么把这些知识掌握的扎实一点,今天课里面的红黑树不了解.

    作者回复: 后面会讲 不急

    2018-10-29
    1
    8
  • 安南寸暖🤕
    talk is cheap, show your code
    2019-01-30
    5
  • CathyLin
    思考题:
    每 3 个结点提取一个结点作为上级索引,时间复杂度是 4log3N ,用大 O 表示法为 O(logn)
    同理,每 5 个结点提取一个结点作为上级索引的时间复杂度是 6log5N,用大 O 表示法为 O(logn)。

    github 上的代码看的有点没太看懂,还得慢慢啃,加油💪
    2018-12-30
    5
  • Smallfly
    老师想问下文章中出现的等比数列求和怎么算的,因为整数除法是取整的,所以公式好像不好使……,用数据代入老师的公式又是正确的,希望能指点一下。

    作者回复: 整数除法是取取整的是什么意思啊

    2018-10-29
    1
    5
  • Uper
    仍然是logn 不过底数是间隔结点个数
    2018-10-29
    5
  • 长期规划
    感觉跳表跟B+树有些像,父节点会出现在子节点中,而且B+的叶节点也是链接起来的。不同的是跳表每个结点只有一个子结点,而且除叶结点相连外,每层内都相连。从结构上来,很像树的变种,层内相连。老师,跳表是受树的启发两来的吗?

    作者回复: 有可能是的。

    2019-07-25
    4
  • kakasi
    感觉github上的实现好难理解,希望老师有时间能解释下。
    我有一个思路:定义两个数据结构,一个是普通的单链表Node,一个索引类Index。索引类中两个域:单链表节点Node, 下一个Index引用。用Index数组表示1 - level索引层。
    这样数据结构里就不会出现数组了,不知这样的思路是否正确。

    作者回复: 你的方法也可以 我的实现思路比较有技巧 是不容易看懂 建议不要纠结实现了

    2018-11-12
    4
  • andavid
    关于 GitHub 上跳表的 Java 代码实现,本人仔细研读后,按自己的理解加上了注释,并写了一个测试程序打印跳表每一层的结点,以及每个结点在各层的下一跳结点。希望对大家理解跳表有所帮助。如果理解有不恰当的地方,还请指正,多谢~

    https://github.com/andavid/ds-algo-java/blob/master/src/main/java/com/github/andavid/ds/datastructure/skiplist/SkipList.java

    https://github.com/andavid/ds-algo-java/blob/master/src/test/java/com/github/andavid/ds/datastructure/skiplist/SkipListTest.java

    2019-08-17
    2
    3
  • 刘涛涛
    github上的代码,我理解的p=p.forwars[i]代表第i层的下一结点,不知道对不对

    作者回复: 对的!👍

    2019-02-17
    1
    3
  • Pluto
    学到了,这个厉害了,不过实现还是没有看的太懂

    作者回复: 实现确实不好看懂 我也看了很久

    2018-11-05
    3
收起评论
99+
返回
顶部