20 | 散列表（下）：为什么散列表和链表经常会一起使用？
王争
该思维导图由 AI 生成，仅供参考
我们已经学习了 20 节内容，你有没有发现，有两种数据结构，散列表和链表，经常会被放在一起使用。你还记得，前面的章节中都有哪些地方讲到散列表和链表的组合使用吗？我带你一起回忆一下。
在链表那一节，我讲到如何用链表来实现 LRU 缓存淘汰算法，但是链表实现的 LRU 缓存淘汰算法的时间复杂度是 O(n)，当时我也提到了，通过散列表可以将这个时间复杂度降低到 O(1)。
在跳表那一节，我提到 Redis 的有序集合是使用跳表来实现的，跳表可以看作一种改进版的链表。当时我们也提到，Redis 有序集合不仅使用了跳表，还用到了散列表。
除此之外，如果你熟悉 Java 编程语言，你会发现 LinkedHashMap 这样一个常用的容器，也用到了散列表和链表两种数据结构。
今天，我们就来看看，在这几个问题中，散列表和链表都是如何组合起来使用的，以及为什么散列表和链表会经常放到一块使用。
LRU 缓存淘汰算法
在链表那一节中，我提到，借助散列表，我们可以把 LRU 缓存淘汰算法的时间复杂度降低为 O(1)。现在，我们就来看看它是如何做到的。
首先，我们来回顾一下当时我们是如何通过链表实现 LRU 缓存淘汰算法的。
我们需要维护一个按照访问时间从大到小有序排列的链表结构。因为缓存大小有限，当缓存空间不够，需要淘汰一个数据的时候，我们就直接将链表头部的结点删除。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
散列表和链表是常用的数据结构，它们经常被放在一起使用。本文从LRU缓存淘汰算法和Redis有序集合两个实际应用场景出发，详细介绍了散列表和链表的组合使用。在LRU缓存淘汰算法中，通过将散列表和双向链表结合使用，实现了高效的缓存系统，将查找、删除和添加数据的时间复杂度都降低到O(1)。而在Redis有序集合中，通过将成员对象组织成跳表的结构，并结合散列表来按照键值进行删除和查找，实现了高效的操作。文章通过实际应用场景的介绍，生动地展示了散列表和链表的组合使用的重要性和优势，为读者提供了深入理解和应用这一技术的指导。 此外，文章还介绍了Java中的LinkedHashMap，它通过双向链表和散列表组合实现，支持按照插入顺序和访问顺序遍历数据，甚至实现了LRU缓存淘汰策略。这些例子展示了散列表和链表结合使用的重要性，散列表虽然高效，但无法支持按顺序快速遍历数据，而链表的加入解决了这一问题。 总之，散列表和链表的组合使用在实际应用中具有重要意义，能够提高数据操作的效率，并且在实现缓存系统等方面发挥重要作用。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《数据结构与算法之美》，新⼈⾸单¥68
《数据结构与算法之美》，新⼈⾸单¥68
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(278)
- 最新
- 精选
Smallfly通过这 20 节课学习下来，个人感觉其实就两种数据结构，链表和数组。 数组占据随机访问的优势，却有需要连续内存的缺点。 链表具有可不连续存储的优势，但访问查找是线性的。 散列表和链表、跳表的混合使用，是为了结合数组和链表的优势，规避它们的不足。 我们可以得出数据结构和算法的重要性排行榜：连续空间 > 时间 > 碎片空间。 PS：跟专业的书籍相比，老师讲的真的是通俗易懂不废话，篇篇是干货。如果这个课程学不下去，学其它的会更加困难。暂时不懂的话反复阅读复习，外加查阅，一定可以的！作者回复: 👍 大牛
2018-11-05261029- Smallfly1. 在删除一个元素时，虽然能 O(1) 的找到目标结点，但是要删除该结点需要拿到前一个结点的指针，遍历到前一个结点复杂度会变为 O(N），所以用双链表实现比较合适。 （但其实硬要操作的话，单链表也是可以实现 O(1) 时间复杂度删除结点的）。 iOS 的同学可能知道，YYMemoryCache 就是结合散列表和双向链表来实现的。 2. 以积分排序构建一个跳表，再以猎头 ID 构建一个散列表。 1）ID 在散列表中所以可以 O(1) 查找到这个猎头； 2）积分以跳表存储，跳表支持区间查询； 3）这点根据目前学习的知识暂时无法实现，老师文中也提到了。
作者回复: 👍 其他同学可以看看这条留言
2018-11-0544449 
HunterYuan看好些人询问LRU中设计的到pre，next和hnext的具体含义，将自己的理解说下，pre和next组成双向链表，这个链表是按照缓存的时间由大到小，组成的一个缓存队列；对于hnext作用是，在最新时间插入缓存数据时，通过哈希函数得出的冲突，用其连接。 总结：在双向链表中，时间是从大到小；在hnext组成的拉链中，时间从左到右依次变小。 核心：数据结构的设计，一定是建立应用场景之上，根据最新时间加入缓存。 这是自己的见解，若是有错误，希望争哥不吝赐教，thanks作者回复: 对的 👍
2019-04-151871
Keep-MovingLRU查找数据，查找到之后，不是应该把数据放到链表的头部吗？为什么这里说是尾部？作者回复: 两种方式都可以的
2018-11-05845
莫问流年怎么判断缓存已满，是要维护一个计数变量吗作者回复: 是的
2018-11-0538
邸志惠我不是科班出身，三年前准备学数据结构，却从没坚持下来，一度怀疑自己的智商有问题，但是看了老师的课程，篇篇都不由自主点赞啊，真是通俗易懂，鞭辟入里啊！感恩老师！作者回复: 多谢赞美啊😁
2019-10-08230
P@tricK老师我想问下，散列表和双向链表结构中的散列值，是用链表中的data哈希的吗？因为这样才能用O(1)查找… 那问题来了，那我要在链表尾部插入数据时，根据什么方法用O(1)定位到尾部呢？作者回复: 需要维护一个尾指针的
2018-11-071027
微秒通过散列表遍历后不用在遍历双向链表了，那怎么以o(1)的时间查找定位链表中的节点？？？除非，散列表的尺寸很大，使得散列表的节点中只有少量数据的链表？？？？作者回复: 是的 理论上散列表查找数据的时间复杂度是O（1）
2018-11-06419
ITACHI第一个图我是这样理解的，不知道对不对： 通俗地将，浅色的线（对应pre、next指针）维系的是链表中用于存储缓存数据的节点位置关系。 而黑色的线（对应hnext指针）维系的是添加节点时发生冲突后，在某个桶的节点位置关系。 比如第一个桶的最后一个节点，应该是在添加时，发现有冲突，且应属于第一个桶，所以用hnext指针和第一个桶的最后一个节点连起来了。 而它又是链表的最后一个节点，所以同时也是和第五个桶的最后一个节点通过pre、next连在一起的。 也就是说实际上只有一个双向链表，灰色线（pre、next指针）维系节点在链表中的位置，新指针hnext维系的是发生冲突的节点在某个桶中的位置。 （这个理解比较笨，而且可能不准确，不过感觉这么想能说通这个图，请问大佬们，这样对么。。。）作者回复: 你理解的完全正确哈。你可以看下这篇文章： https://mp.weixin.qq.com/s/PdvdZoa-SGk_Ojkv2pC2tQ
2019-09-12817
Zeng Shine“一个节点会存在两条拉链中，一条是双向链表，另一条是散列表中的拉链”，这句话描述的结构，怎么都想不明白。。作者回复: 图能不能看懂呢 你结合图看下
2018-11-061715
收起评论
