LRU缓存机制（保姆级精讲）

前言

LRU（Least Recently Used，最近最少使用）缓存 是计算机领域最经典、面试必考、工程最常用的缓存淘汰算法。

几乎所有开发者都会学习 LRU，但绝大多数初学者了解代码，但不清楚底层设计逻辑、不知道为什么要用双向链表+哈希表、分不清一些细节坑点、实际落地场景。

本文将从零起步，一步步解决所有疑惑，发车！！！

一、为什么需要缓存淘汰算法？

1.那就要先知道缓存的核心作用

缓存的本质：用空间换时间。
将高频访问的热点数据，存放在读写速度极快的内存中，避免频繁查询磁盘、数据库、远程服务，大幅提升访问效率。

2.但缓存的短板也就出现了

内存空间是有限的，无法无限存放数据。
当缓存存放的数据量达到预设上限（容量）时，必须淘汰一部分旧数据，才能存入新数据。

由此衍生出多种缓存淘汰策略，最主流的三种：

1. FIFO（先进先出）：淘汰最早存入的数据，不关心是否常
2. LFU（最少使用）：淘汰被访问次数最少的数据，逻辑复杂、性能
3. LRU（最近最少使用）：淘汰最久没有被使用的数据

3 .那么为什么工业级场景首选LRU？

真实业务数据有极强的热点局部性：

• 最近被访问过的数据，未来大概率还会被访问
• 长期未被访问的数据，未来大概率不会再使用

LRU 完美贴合业务特性，实现简单、性能极高、淘汰逻辑最合理，是 Redis、操作系统、浏览器、APP 缓存的核心淘汰策略。

二、LRU的核心设计思想

思想：优先保留「最近使用」的数据，自动淘汰「最久未使用」的数据，保证缓存中永远存放热点高频数据。

排序规则：

• 链表头部：最近使用（最新热点数据）（最新热点数据）
• 链表尾部：最久未使用（优先被淘汰的冷数据）

所有操作（查询、修改、新增）只要触发数据访问，就会将数据刷新到链表头部，维持时序规则。

三、LRU的核心架构为什么是“哈希表 + 双向链表”？

有些同学看到LRU的核心架构可能会产生疑惑：为什么不能用单向链表？不能纯哈希表？不能纯链表？

LRU 的核心要求： get 、 put 操作时间复杂度必须严格 O(1)
为了实现 O(1) 极致性能，最终敲定 哈希表（寻址）+ 双向链表（维护顺序） 的黄金组合，二者各司其职、缺一不可。

各数据结构单独存在的缺陷

缺陷1：只用单向链表

• 优点：可以维护数据使用顺
• 致命问题：删除/移动中间节点需要从头遍历，时间复杂度 O(n)，不满足高性能要求

缺陷2：只用双向链表

• 优点：头尾增删、中间节点移动均为 O(1)
• 致命问题：无法快速查找指定 key 的节点，查询需要遍历链表 O(n)

缺陷3：只用哈希表

• 优点：key 寻址 O(1)，查询极快
• 致命问题：哈希表无序，无法记录数据的使用时间顺序，无法实现LRU淘汰规则

黄金组合：哈希表 + 双向链表

结论：

1. 所有缓存数据节点，全部存在同一条双向链表中
2. 哈希表不存数据，只存「key 到节点地址的快捷索引」
3. 链表管顺序和淘汰，哈希表管快速查找

四、关于LRU机制一些细节疑点深度解析

4.1为什么节点内部必须存储 key？

链表节点结构体中，我们同时存储 key 和 value ，很多新手疑惑：哈希表已经存了 key 了，节点为什么还要存一遍 key？

核心原因：淘汰尾部节点时，需要反向删除哈希表映射

1. 缓存满容量时，我们只会删除双向链表的尾节点
2. 我们只能拿到「被删除的节点对象」，无法直接获取它对应的 key
3. 节点内部存储的 key，就是用来执行 map.erase(node->key) ，删除哈希表失效映射

如果节点不存 key，哈希表残留无效数据，会导致内存溢出、逻辑错乱。

4.2 虚拟头尾哨兵节点的作用

全局固定：虚拟头head、虚拟尾tail，全程不变
所有数据节点都插在 head 和 tail 中间
新key不存在：新建双向链表节点存key、val

手写LRU统一使用虚拟头节点(head)、虚拟尾节点(tail)，不属于业务数据，全程固定不动。

解决两大痛点：

1. 彻底避免空指针判断：所有业务节点永远夹在 head 和 tail 中间，增删逻辑统一
2. 统一代码逻辑：头部插入、尾部删除、中间移动节点，不需要区分首尾特殊情况，代码极简且零bug

4.3 容量判定逻辑：size 和 capacity 的区别

1. capacity ：缓存最大容量，是用户初始化时设定的固定值（最多能存多少条数据）
2. size ：当前实时数据条数，动态变化

满容量触发淘汰的核心逻辑：

• 每新增一个全新key， size++
• 当 size > capacity 时，触发淘汰机制
• 更新已有key、查询key，不会改变size，不会触发淘汰

重点误区：
不是链表物理空间满了，是数据条目数超过设定容量；且一次只淘汰1个最久未使用节点，不会批量淘汰。

4.4 为什么必须是双向链表？

双向链表自带 prev 前驱指针和 next 后继指针：

1. 删除任意中间节点时，可直接通过 prev 和 next 对接前后节点，O(1) 完成删除
2. 单向链表没有前驱指针，删除中间节点必须从头遍历找前驱，性能暴跌至 O(n)

4.5 为什么用 unordered_map 不用 map？

1. unordered_map ：底层哈希表，平均查询 O(1)，适配LRU高性能需求
2. map ：底层红黑树，查询 O(logn)，性能更低，工业级LRU一律使用 unordered_map

五、LRU两大核心操作完整流程推演

5.1 get(key) 查询操作

规则：只要查询命中，就算一次使用，必须刷新为最近使用（移到链表头部）

完整步骤：

1. 判断哈希表中是否存在该 key
2. 不存在：直接返回 -1
3. 存在：
   • 通过哈希表 O(1) 取出对应链表节点
   • 将该节点从原链表位置删除
   • 将该节点插入链表头部（刷新为最近使用）
   • 返回节点的 value 值

5.2 put(key, value) 新增/更新操作

分两种场景：key已存在、key不存在

场景1：哈希表已存在该key（更新数据）

1. 通过哈希表找到对应节点
2. 更新节点的 value 值
3. 将节点移动到链表头部（刷新使用时间）
4. size不变，不新增节点，不触发淘汰

场景2：哈希表无该key（新增数据）

1. 新建双向链表节点，存入 key、value
2. 哈希表建立映射： key -> 新节点指针
3. 将新节点插入链表头部（最新使用）
4. 实时数据条数 size++
5. 判断是否超容量：
   • 未超：流程结束
   • 超容量：删除链表尾部最久未使用节点 → 通过节点key删除哈希表映射 → size–

六、一些LRU实际落地场景

1.Redis 缓存淘汰策略

Redis 内存满后，默认开启 allkeys-lru 策略：
优先淘汰最近最少使用的key，保留高频热点缓存，是后端服务的核心保障。

2.操作系统内存页面置换

电脑/手机物理内存不足时，操作系统通过 LRU 算法：
将长期未运行的进程页面置换到磁盘，腾出内存给活跃进程，保证系统流畅。

3.浏览器缓存优化

浏览器缓存网页资源、图片、脚本：

• 近期访问页面：常驻内存，秒开
• 长期未访问页面：LRU自动清理内存缓存

4.移动端APP资源缓存

短视频、朋友圈、电商APP的图片/视频缓存：
自动清理长期未浏览的旧资源，避免手机存储溢出。

5.数据库热点数据缓存

业务系统将高频查询的用户、商品、订单数据缓存：
长期无人查询的冷数据自动淘汰，减轻数据库查询压力。

6.后端业务临时缓存

直播间、在线房间、会话缓存：
自动清理长时间无互动的闲置房间/会话，节省服务器内存。

七、拓展

基础LRU存在缺陷：偶尔访问的冷门数据会淘汰长期高频数据
企业级优化方案：

1. 2Q-LRU：双队列缓存，区分冷热数据，避免瞬时热点冲刷
2. LRU-K：统计K次访问记录，降低偶然访问数据的优先级
3. TTL+LRU：结合过期时间，主动清理过期缓存

八、总结

LRU核心思想是基于时间局部性原理，保留最近使用数据，淘汰最久未使用数据。

数据结构设计采用哈希表+双向链表，哈希表实现O(1)快速寻址，双向链表维护使用时序、实现头尾O(1)增删。

其中虚拟哨兵节点简化判空逻辑，节点存储key用于反向清理哈希映射，size动态统计数据量，超容量淘汰尾部冷数据。

操作逻辑：查询命中刷新头部、未命中返回-1；更新key刷新位置、新增key超容淘汰尾部。

价值：贴合业务热点数据特性，高性能、低损耗，广泛用于Redis、操作系统、各类终端缓存场景。