20丨散列表（下）：为什么散列表和链表经常会一起使用？1
需积分: 0 93 浏览量
2022-08-03
11:49:00
上传
评论
收藏 2.07MB PDF 举报
20 | 散列表（下）：为什么散列表和链表经常会一起使用？
2018-11-05 王争
数据结构与算法之美
进入课程
讲述：修阳
时长 11:39 大小 5.34M
我们已经学习了 20 节内容，你有没有发现，有两种数据结构，散列表和链表，经常会被放
在一起使用。你还记得，前面的章节中都有哪些地方讲到散列表和链表的组合使用吗？我带
你一起回忆一下。
在链表那一节，我讲到如何用链表来实现 LRU 缓存淘汰算法，但是链表实现的 LRU 缓存
淘汰算法的时间复杂度是 O(n)，当时我也提到了，通过散列表可以将这个时间复杂度降低
到 O(1)。
在跳表那一节，我提到 Redis 的有序集合是使用跳表来实现的，跳表可以看作一种改进版
的链表。当时我们也提到，Redis 有序集合不仅使用了跳表，还用到了散列表。
下载APP
剩余13页未读，继续阅读
资源评论
