前言
LRU（Least Recently Used，最近最少使用）缓存 是计算机领域最经典、面试必考、工程最常用的缓存淘汰算法。
几乎所有开发者都会学习 LRU，但绝大多数初学者了解代码，但不清楚底层设计逻辑、不知道为什么要用双向链表+哈希表、分不清一些细节坑点、实际落地场景。
本文将从零起步，一步步解决所有疑惑，发车！！！
一、为什么需要缓存淘汰算法？
1.那就要先知道缓存的核心作用
缓存的本质：用空间换时间。
将高频访问的热点数据，存放在读写速度极快的内存中，避免频繁查询磁盘、数据库、远程服务，大幅提升访问效率。
2.但缓存的短板也就出现了
内存空间是有限的，无法无限存放数据。
当缓存存放的数据量达到预设上限（容量）时，必须淘汰一部分旧数据，才能存入新数据。
由此衍生出多种缓存淘汰策略，最主流的三种：
- FIFO（先进先出）：淘汰最早存入的数据，不关心是否常
- LFU（最少使用）：淘汰被访问次数最少的数据，逻辑复杂、性能
- 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淘汰规则
黄金组合：哈希表 + 双向链表
| 数据结构 | 职责 | 时间复杂度 |
|---|---|---|
| 哈希表 unordered_map | 建立 key -> 链表节点指针 映射，O(1) 精准定位任意节点 | O(1) |
| 双向链表 | 维护数据使用时序，实现头部插入、尾部淘汰、节点移动 | O(1) |
结论：
- 所有缓存数据节点，全部存在同一条双向链表中
- 哈希表不存数据，只存「key 到节点地址的快捷索引」
- 链表管顺序和淘汰，哈希表管快速查找
四、关于LRU机制一些细节疑点深度解析
4.1为什么节点内部必须存储 key？
链表节点结构体中，我们同时存储 key 和 value ，很多新手疑惑：哈希表已经存了 key 了，节点为什么还要存一遍 key？
核心原因：淘汰尾部节点时，需要反向删除哈希表映射
- 缓存满容量时，我们只会删除双向链表的尾节点
- 我们只能拿到「被删除的节点对象」，无法直接获取它对应的 key
- 节点内部存储的 key，就是用来执行 map.erase(node->key) ，删除哈希表失效映射
如果节点不存 key，哈希表残留无效数据，会导致内存溢出、逻辑错乱。
4.2 虚拟头尾哨兵节点的作用
全局固定：虚拟头head、虚拟尾tail，全程不变
所有数据节点都插在 head 和 tail 中间
新key不存在：新建双向链表节点存key、val
手写LRU统一使用虚拟头节点(head)、虚拟尾节点(tail)，不属于业务数据，全程固定不动。
解决两大痛点：
- 彻底避免空指针判断：所有业务节点永远夹在 head 和 tail 中间，增删逻辑统一
- 统一代码逻辑：头部插入、尾部删除、中间移动节点，不需要区分首尾特殊情况，代码极简且零bug
4.3 容量判定逻辑：size 和 capacity 的区别
- capacity ：缓存最大容量，是用户初始化时设定的固定值（最多能存多少条数据）
- size ：当前实时数据条数，动态变化
满容量触发淘汰的核心逻辑：
- 每新增一个全新key， size++
- 当 size > capacity 时，触发淘汰机制
- 更新已有key、查询key，不会改变size，不会触发淘汰
重点误区：
不是链表物理空间满了，是数据条目数超过设定容量；且一次只淘汰1个最久未使用节点，不会批量淘汰。
4.4 为什么必须是双向链表？
双向链表自带 prev 前驱指针和 next 后继指针：
- 删除任意中间节点时，可直接通过 prev 和 next 对接前后节点，O(1) 完成删除
- 单向链表没有前驱指针，删除中间节点必须从头遍历找前驱，性能暴跌至 O(n)
4.5 为什么用 unordered_map 不用 map？
- unordered_map ：底层哈希表，平均查询 O(1)，适配LRU高性能需求
- map ：底层红黑树，查询 O(logn)，性能更低，工业级LRU一律使用 unordered_map
五、LRU两大核心操作完整流程推演
5.1 get(key) 查询操作
规则：只要查询命中，就算一次使用，必须刷新为最近使用（移到链表头部）
完整步骤：
- 判断哈希表中是否存在该 key
- 不存在：直接返回 -1
- 存在：
- 通过哈希表 O(1) 取出对应链表节点
- 将该节点从原链表位置删除
- 将该节点插入链表头部（刷新为最近使用）
- 返回节点的 value 值
5.2 put(key, value) 新增/更新操作
分两种场景：key已存在、key不存在
场景1：哈希表已存在该key（更新数据）
- 通过哈希表找到对应节点
- 更新节点的 value 值
- 将节点移动到链表头部（刷新使用时间）
- size不变，不新增节点，不触发淘汰
场景2：哈希表无该key（新增数据）
- 新建双向链表节点，存入 key、value
- 哈希表建立映射： key -> 新节点指针
- 将新节点插入链表头部（最新使用）
- 实时数据条数 size++
- 判断是否超容量：
- 未超：流程结束
- 超容量：删除链表尾部最久未使用节点 → 通过节点key删除哈希表映射 → size–
六、一些LRU实际落地场景
1.Redis 缓存淘汰策略
Redis 内存满后，默认开启 allkeys-lru 策略：
优先淘汰最近最少使用的key，保留高频热点缓存，是后端服务的核心保障。
2.操作系统内存页面置换
电脑/手机物理内存不足时，操作系统通过 LRU 算法：
将长期未运行的进程页面置换到磁盘，腾出内存给活跃进程，保证系统流畅。
3.浏览器缓存优化
浏览器缓存网页资源、图片、脚本：
- 近期访问页面：常驻内存，秒开
- 长期未访问页面：LRU自动清理内存缓存
4.移动端APP资源缓存
短视频、朋友圈、电商APP的图片/视频缓存：
自动清理长期未浏览的旧资源，避免手机存储溢出。
5.数据库热点数据缓存
业务系统将高频查询的用户、商品、订单数据缓存：
长期无人查询的冷数据自动淘汰，减轻数据库查询压力。
6.后端业务临时缓存
直播间、在线房间、会话缓存：
自动清理长时间无互动的闲置房间/会话，节省服务器内存。
七、拓展
基础LRU存在缺陷：偶尔访问的冷门数据会淘汰长期高频数据
企业级优化方案：
- 2Q-LRU：双队列缓存，区分冷热数据，避免瞬时热点冲刷
- LRU-K：统计K次访问记录，降低偶然访问数据的优先级
- TTL+LRU：结合过期时间，主动清理过期缓存
八、总结
LRU核心思想是基于时间局部性原理，保留最近使用数据，淘汰最久未使用数据。
数据结构设计采用哈希表+双向链表，哈希表实现O(1)快速寻址，双向链表维护使用时序、实现头尾O(1)增删。
其中虚拟哨兵节点简化判空逻辑，节点存储key用于反向清理哈希映射，size动态统计数据量，超容量淘汰尾部冷数据。
操作逻辑：查询命中刷新头部、未命中返回-1；更新key刷新位置、新增key超容淘汰尾部。
价值：贴合业务热点数据特性，高性能、低损耗，广泛用于Redis、操作系统、各类终端缓存场景。
