数据结构与算法之美
王争
前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 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

20 | 散列表(下):为什么散列表和链表经常会一起使用?

王争 2018-11-05
我们已经学习了 20 节内容,你有没有发现,有两种数据结构,散列表和链表,经常会被放在一起使用。你还记得,前面的章节中都有哪些地方讲到散列表和链表的组合使用吗?我带你一起回忆一下。
在链表那一节,我讲到如何用链表来实现 LRU 缓存淘汰算法,但是链表实现的 LRU 缓存淘汰算法的时间复杂度是 O(n),当时我也提到了,通过散列表可以将这个时间复杂度降低到 O(1)。
在跳表那一节,我提到 Redis 的有序集合是使用跳表来实现的,跳表可以看作一种改进版的链表。当时我们也提到,Redis 有序集合不仅使用了跳表,还用到了散列表。
除此之外,如果你熟悉 Java 编程语言,你会发现 LinkedHashMap 这样一个常用的容器,也用到了散列表和链表两种数据结构。
今天,我们就来看看,在这几个问题中,散列表和链表都是如何组合起来使用的,以及为什么散列表和链表会经常放到一块使用。

LRU 缓存淘汰算法

在链表那一节中,我提到,借助散列表,我们可以把 LRU 缓存淘汰算法的时间复杂度降低为 O(1)。现在,我们就来看看它是如何做到的。
首先,我们来回顾一下当时我们是如何通过链表实现 LRU 缓存淘汰算法的。
我们需要维护一个按照访问时间从大到小有序排列的链表结构。因为缓存大小有限,当缓存空间不够,需要淘汰一个数据的时候,我们就直接将链表头部的结点删除。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(158)

  • Smallfly
    通过这 20 节课学习下来,个人感觉其实就两种数据结构,链表和数组。

    数组占据随机访问的优势,却有需要连续内存的缺点。

    链表具有可不连续存储的优势,但访问查找是线性的。

    散列表和链表、跳表的混合使用,是为了结合数组和链表的优势,规避它们的不足。

    我们可以得出数据结构和算法的重要性排行榜:连续空间 > 时间 > 碎片空间。

    PS:跟专业的书籍相比,老师讲的真的是通俗易懂不废话,篇篇是干货。如果这个课程学不下去,学其它的会更加困难。暂时不懂的话反复阅读复习,外加查阅,一定可以的!

    作者回复: 👍 大牛

    2018-11-05
    7
    424
  • Smallfly
    1.

    在删除一个元素时,虽然能 O(1) 的找到目标结点,但是要删除该结点需要拿到前一个结点的指针,遍历到前一个结点复杂度会变为 O(N),所以用双链表实现比较合适。

    (但其实硬要操作的话,单链表也是可以实现 O(1) 时间复杂度删除结点的)。

    iOS 的同学可能知道,YYMemoryCache 就是结合散列表和双向链表来实现的。

    2.

    以积分排序构建一个跳表,再以猎头 ID 构建一个散列表。

    1)ID 在散列表中所以可以 O(1) 查找到这个猎头;
    2)积分以跳表存储,跳表支持区间查询;
    3)这点根据目前学习的知识暂时无法实现,老师文中也提到了。

    作者回复: 👍 其他同学可以看看这条留言

    2018-11-05
    10
    191
  • 姜威
    带着问题去学习:
    1.为什么散列表和链表经常放在一起使用?
    2.散列表和链表如何组合起来使用?
    一、为什么散列表和链表经常放在一起使用?
    1.散列表的优点:支持高效的数据插入、删除和查找操作
    2.散列表的缺点:不支持快速顺序遍历散列表中的数据
    3.如何按照顺序快速遍历散列表的数据?只能将数据转移到数组,然后排序,最后再遍历数据。
    4.我们知道散列表是动态的数据结构,需要频繁的插入和删除数据,那么每次顺序遍历之前都需要先排序,这势必会造成效率非常低下。
    5.如何解决上面的问题呢?就是将散列表和链表(或跳表)结合起来使用。
    二、散列表和链表如何组合起来使用?
    1.LRU(Least Recently Used)缓存淘汰算法
    1.1.LRU缓存淘汰算法主要操作有哪些?主要包含3个操作:
    ①往缓存中添加一个数据;
    ②从缓存中删除一个数据;
    ③在缓存中查找一个数据;
    ④总结:上面3个都涉及到查找。
    1.2.如何用链表实现LRU缓存淘汰算法?
    ①需要维护一个按照访问时间从大到小的有序排列的链表结构。
    ②缓冲空间有限,当空间不足需要淘汰一个数据时直接删除链表头部的节点。
    ③当要缓存某个数据时,先在链表中查找这个数据。若未找到,则直接将数据放到链表的尾部。若找到,就把它移动到链表尾部。
    ④前面说了,LRU缓存的3个主要操作都涉及到查找,若单纯由链表实现,查找的时间复杂度很高为O(n)。若将链表和散列表结合使用,查找的时间复杂度会降低到O(1)。
    1.3.如何使用散列表和链表实现LRU缓存淘汰算法?
    ①使用双向链表存储数据,链表中每个节点存储数据(data)、前驱指针(prev)、后继指针(next)和hnext指针(解决散列冲突的链表指针)。
    ②散列表通过链表法解决散列冲突,所以每个节点都会在两条链中。一条链是双向链表,另一条链是散列表中的拉链。前驱和后继指针是为了将节点串在双向链表中,hnext指针是为了将节点串在散列表的拉链中。
    ③LRU缓存淘汰算法的3个主要操作如何做到时间复杂度为O(1)呢?
    首先,我们明确一点就是链表本身插入和删除一个节点的时间复杂度为O(1),因为只需更改几个指针指向即可。
    接着,来分析查找操作的时间复杂度。当要查找一个数据时,通过散列表可实现在O(1)时间复杂度找到该数据,再加上前面说的插入或删除的时间复杂度是O(1),所以我们总操作的时间复杂度就是O(1)。
    2.Redis有序集合
    2.1.什么是有序集合?
    ①在有序集合中,每个成员对象有2个重要的属性,即key(键值)和score(分值)。
    ②不仅会通过score来查找数据,还会通过key来查找数据。
    2.2.有序集合的操作有哪些?
    举个例子,比如用户积分排行榜有这样一个功能:可以通过用户ID来查找积分信息,也可以通过积分区间来查找用户ID。这里用户ID就是key,积分就是score。所以,有序集合的操作如下:
    ①添加一个对象;
    ②根据键值删除一个对象;
    ③根据键值查找一个成员对象;
    ④根据分值区间查找数据,比如查找积分在[100.356]之间的成员对象;
    ⑤按照分值从小到大排序成员变量。
    这时可以按照分值将成员对象组织成跳表结构,按照键值构建一个散列表。那么上面的所有操作都非常高效。
    3.Java LinkedHashMap
    和LRU缓存淘汰策略实现一模一样。支持按照插入顺序遍历数据,也支持按照访问顺序遍历数据。
    三、课后思考
    1.上面所讲的几个散列表和链表组合的例子里,我们都是使用双向链表。如果把双向链表改成单链表,还能否正常工作?为什么呢?
    2.假设猎聘网有10万名猎头,每个猎头可以通过做任务(比如发布职位)来积累积分,然后通过积分来下载简历。假设你是猎聘网的一名工程师,如何在内存中存储这10万个猎头的ID和积分信息,让它能够支持这样几个操作:
    1)根据猎头ID查收查找、删除、更新这个猎头的积分信息;
    2)查找积分在某个区间的猎头ID列表;
    3)查找按照积分从小到大排名在第x位到第y位之间的猎头ID列表。
    2018-11-16
    1
    39
  • Keep-Moving
    LRU查找数据,查找到之后,不是应该把数据放到链表的头部吗?为什么这里说是尾部?

    作者回复: 两种方式都可以的

    2018-11-05
    23
  • 莫问流年
    怎么判断缓存已满,是要维护一个计数变量吗

    作者回复: 是的

    2018-11-05
    16
  • HunterYuan
    看好些人询问LRU中设计的到pre,next和hnext的具体含义,将自己的理解说下,pre和next组成双向链表,这个链表是按照缓存的时间由大到小,组成的一个缓存队列;对于hnext作用是,在最新时间插入缓存数据时,通过哈希函数得出的冲突,用其连接。
    总结:在双向链表中,时间是从大到小;在hnext组成的拉链中,时间从左到右依次变小。
    核心:数据结构的设计,一定是建立应用场景之上,根据最新时间加入缓存。
    这是自己的见解,若是有错误,希望争哥不吝赐教,thanks

    作者回复: 对的 👍

    2019-04-15
    5
    15
  • Zeng Shine
    “一个节点会存在两条拉链中,一条是双向链表,另一条是散列表中的拉链”,这句话描述的结构,怎么都想不明白。。

    作者回复: 图能不能看懂呢 你结合图看下

    2018-11-06
    4
    11
  • hot
    一个链是刚刚我们提到的双向链表,另一个链是散列表中的拉链
    就是结合你的图也看不懂啊 ,老铁
    2018-11-13
    2
    9
  • 微秒
    通过散列表遍历后不用在遍历双向链表了,那怎么以o(1)的时间查找定位链表中的节点???除非,散列表的尺寸很大,使得散列表的节点中只有少量数据的链表????

    作者回复: 是的 理论上散列表查找数据的时间复杂度是O(1)

    2018-11-06
    9
  • P@tricK
    老师我想问下,散列表和双向链表结构中的散列值,是用链表中的data哈希的吗?因为这样才能用O(1)查找…
    那问题来了,那我要在链表尾部插入数据时,根据什么方法用O(1)定位到尾部呢?

    作者回复: 需要维护一个尾指针的

    2018-11-07
    2
    8
  • 虢白
    看到很多人都在问,为什么老师说的,一条链是双向链表的链,一条链是拉链没看明白。
    其实就是散列表为了解决散列冲突,所以得到同一个hash值的时候,将同一个hash值的用一个链表来存放了,而在图上面就是双链表中的hnext所串连起来的链表。个人是这么理解的。
    2019-01-31
    1
    7
  • 牧民牛仔
    1.双联表改成单链表,依然可以工作。可以用一个变量存储遍历到的节点的前驱指针。
    2.可以把猎聘网的猎头的信息存储在 散列表和链表(跳表)组合使用的容器中,其中按照猎头id建立散列表,按照猎头的积分建立一个跳表。这样,无论是按照id查用户,还是按照积分进行排序和区间查找都会很高效。
    2018-11-05
    6
  • chenlong321
    lru算法,缓存中,如果能查找到节点a,那么需要先删除a,再将a移动到双向链表的尾端,那这不就改变了节点a的hash bucket,下次怎么还能通过hash快速查找到节点a,请老师指教,谢谢

    作者回复: 双向链表,跟散列表没有任何关系。这里的双向链表不是散列表中的链表。

    不管是双向链表还是散列表,你都可以把它当做一种索引结构。里面存储的都是指向真实缓存对象的内存地址。

    改变双向链表的结点结构,并不会影响散列表。

    2019-04-16
    2
    5
  • MrTrans
    老师,hnext是解决散列冲突的链表,而双向链表是维护插入元素顺序的表。两条链是不一样的,一个hnext是维护散列冲突的,一个双向链表是维护插入元素的顺序的。那么查找,删除,添加就要维护这两个链表。老师这样理解是不是很对。
    2018-12-21
    5
  • 猫头鹰爱拿铁
    1.可以通过单链表和散列表实现,但是删除和添加的时间复杂度就变成了O(n),因为需要遍历一次链表将前驱节点找到,再进行删除。
    2.猎头问题:每个猎头对象由node构成(pre,next,hnext,data)将id作为键值建立类似hashmap的结构来存放猎头的对象,同时再将每个节点使用双向链表按照积分大小(快排排序)链接起来。根据id查找、删除、添加时间复杂度为O(1),查找排名的时间复杂度为O(n),如果想提高查找排名的时间复杂度,可以再和跳表结合一块,根据积分建立索引,查找排名的时间复杂度将提升为O(logn)
    2018-11-05
    5
  • Lucus
    老师我有一点不明白,双向链表中节点要移动到尾部还有找到链表头节点应该都需要遍历链表吧,平均时间复杂度应该是O(n)啊?

    作者回复: 链表头、尾指针是已经记录好的了。移动到尾部,就是先删除,再添加的过程。

    2019-04-08
    4
  • Fstar
    老师,你那个 LRU 的删除和添加操作,貌似没有说要更新拉链的链表呢?我觉得删除操作时,还要保存匹配节点在拉链中的上一个节点,通过hnext移除匹配节点;添加操作时,也要记录匹配拉链的最后一个节点k,且只有在发现数据不存在时,并将其添加到双链表末尾时,再让这个k指向这个新建的元素,不知道这样对不对?

    作者回复: 你说的没错。

    2019-02-07
    4
  • 小智e
    想请问一下,如何使用跳表来解决哈希冲突呢?没想通

    作者回复: 就是把散列表中的链表换成跳表 其他不变

    2018-12-07
    4
  • Tensor
    老师,您好,你讲的那个LRU算法中的,散列表加上双向链表的图没有看懂,能不能再讲详细点儿啊(不好意思,基础太差了)?还有不理解的是为什么查找哈希表中双向链表某一节点的时间复杂度是o(1)???首先在哈希表中遍历为1,但确定了哈希表的位置后,还要遍及节点,这个跟链表的规模有关吧???
    2018-11-11
    1
    4
  • Uncle.席
    10万个猎头,走眼看成了猪头,也许是猪肉太贵了吧!
    2019-11-28
    3
收起评论
99+
返回
顶部