前言LRULeast 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 中间增删逻辑统一统一代码逻辑头部插入、尾部删除、中间移动节点不需要区分首尾特殊情况代码极简且零bug4.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 不用 mapunordered_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次访问记录降低偶然访问数据的优先级TTLLRU结合过期时间主动清理过期缓存八、总结LRU核心思想是基于时间局部性原理保留最近使用数据淘汰最久未使用数据。数据结构设计采用哈希表双向链表哈希表实现O(1)快速寻址双向链表维护使用时序、实现头尾O(1)增删。其中虚拟哨兵节点简化判空逻辑节点存储key用于反向清理哈希映射size动态统计数据量超容量淘汰尾部冷数据。操作逻辑查询命中刷新头部、未命中返回-1更新key刷新位置、新增key超容淘汰尾部。价值贴合业务热点数据特性高性能、低损耗广泛用于Redis、操作系统、各类终端缓存场景。