【图解数据结构与算法】LRU缓存淘汰算法面试时到底该怎么写(上)

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: 链表实现的LRU缓存淘汰算法的时间复杂度是O(n),当时我也提到了,通过散列表可以将这个时间复杂度降低到O(1)。Redis的有序集合是使用跳表来实现的,跳表可以看作一种改进版的链表。Redis有序集合不仅使用了跳表,还用到了散列表。LinkedHashMap也用到了散列表和链表两种数据结构。散列表和链表都是如何组合起来使用的,以及为什么散列表和链表会经常放到一块使用。

链表实现的LRU缓存淘汰算法的时间复杂度是O(n),当时我也提到了,通过散列表可以将这个时间复杂度降低到O(1)。


Redis的有序集合是使用跳表来实现的,跳表可以看作一种改进版的链表。Redis有序集合不仅使用了跳表,还用到了散列表。


LinkedHashMap也用到了散列表和链表两种数据结构。散列表和链表都是如何组合起来使用的,以及为什么散列表和链表会经常放到一块使用。

LRU缓存淘汰算法

链表实现LRU

需要维护一个按照访问时间从大到小有序排列的链表结构。因为缓存大小有限,当缓存空间不够,需要淘汰一个数据的时候,我们就直接将链表头部的结点删除。

当要缓存某个数据的时候,先在链表中查找这个数据。如果没有找到,则直接将数据放到链表的尾部;如果找到了,我们就把它移动到链表的尾部。因为查找数据需要遍历链表,所以单纯用链表实现的LRU缓存淘汰算法的时间复杂很高,是O(n)。


一个缓存(cache)系统主要包含下面这几个操作:


往缓存中添加一个数据

从缓存中删除一个数据

在缓存中查找一个数据。

都涉及“查找”操作,如果单纯地采用链表,时间复杂度只能是O(n)。如果我们将散列表和链表两种数据结构组合使用,可以将这三个操作的时间复杂度都降低到O(1)。


具体结构:

image.png

使用双向链表存储数据,链表中的每个结点处理存储数据(data)、前驱指针(prev)、后继指针(next)之外,还新增了一个特殊的字段hnext。这个hnext有什么作用呢?


因为通过链表法解决哈希冲突,所以每个结点在两条链中:


双向链表

前驱和后继指针是为了将结点串在双向链表

散列表中的拉链

hnext指针是为了将结点串在散列表的拉链

查找

散列表中查找数据的时间复杂度接近O(1),所以通过散列表,我们可以很快地在缓存中找到一个数据。当找到数据之后,我们还需要将它移动到双向链表的尾部。

删除

需要找到数据所在的结点,然后将结点删除。借助散列表,我们可以在O(1)时间复杂度里找到要删除的结点。因为我们的链表是双向链表,双向链表可以通过前驱指针O(1)时间复杂度获取前驱结点,所以在双向链表中,删除结点只需要O(1)的时间复杂度。

添加

添加数据到缓存稍微有点麻烦,我们需要先看这个数据是否已经在缓存中。如果已经在其中,需要将其移动到双向链表的尾部;如果不在其中,还要看缓存有没有满。如果满了,则将双向链表头部的结点删除,然后再将数据放到链表的尾部;如果没有满,就直接将数据放到链表的尾部。

过程中的查找操作都可通过hash表。所以,这三个操作的时间复杂度都是O(1)。

通过散列表和双向链表的组合使用,实现了一个高效的、支持LRU缓存淘汰算法的缓存系统原型。

Redis有序集合

在有序集合中,每个成员对象有两个重要的属性,key(键值)和score(分值)。

不仅会通过score来查找数据,还会通过key来查找数据。

举个例子,比如用户积分排行榜有这样一个功能:我们可以通过用户的ID来查找积分信息,也可以通过积分区间来查找用户ID或者姓名信息。这里包含ID、姓名和积分的用户信息,就是成员对象,用户ID就是key,积分就是score。


所以,如果我们细化一下Redis有序集合的操作,那就是下面这样:


添加一个成员对象

按照键值来删除一个成员对象

按照键值来查找一个成员对象

按照分值区间查找数据,比如查找积分在[100, 356]之间的成员对象

按照分值从小到大排序成员变量;

若仅按分值将成员对象组织成跳表的结构,那按照键删除、查询成员对象就会很慢,解决方法与LRU缓存淘汰算法的解决方法类似。

可再按照键值构建一个散列表,这样按照key来删除、查找一个成员对象的时间复杂度就变成了O(1)。


Redis有序集合的操作还有另外一类,也就是查找成员对象的排名(Rank)或者根据排名区间查找成员对象。这个功能单纯用刚刚讲的这种组合结构就无法高效实现了。


目录
相关文章
|
5月前
|
人工智能 算法 NoSQL
LRU算法的Java实现
LRU(Least Recently Used)算法用于淘汰最近最少使用的数据,常应用于内存管理策略中。在Redis中,通过`maxmemory-policy`配置实现不同淘汰策略,如`allkeys-lru`和`volatile-lru`等,采用采样方式近似LRU以优化性能。Java中可通过`LinkedHashMap`轻松实现LRUCache,利用其`accessOrder`特性和`removeEldestEntry`方法完成缓存淘汰逻辑,代码简洁高效。
194 0
|
3月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
73 1
|
3月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
83 0
|
4月前
|
缓存 人工智能 算法
lru算法设计与实现
本文详细介绍了LRU(Least Recently Used,最近最少使用)缓存淘汰策略的原理与实现。LRU的核心思想是:越近被访问的数据,未来被再次访问的可能性越大。文章通过Java语言实现了一个支持O(1)时间复杂度操作的LRU缓存
140 0
|
6月前
|
缓存 NoSQL Go
【LeetCode 热题100】146:LRU 缓存(详细解析)(Go语言版)
本文详细解析了力扣 146 题——LRU 缓存机制的实现方法。通过结合哈希表与双向链表,确保 `get` 和 `put` 操作均在 O(1) 时间内完成。哈希表用于快速查找,双向链表记录访问顺序,支持最近使用数据的高效更新与淘汰。代码以 Go 语言实现,结构清晰,涵盖核心操作如节点移动、插入与删除。此题为面试高频考点,适用于数据缓存、页面置换等场景,掌握后可加深对缓存策略的理解。
279 4
|
7月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
158 3
 算法系列之数据结构-Huffman树
|
7月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
198 22
|
7天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
|
9天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
|
8天前
|
传感器 机器学习/深度学习 算法
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)