个人主页Milestone-里程碑❄️个人专栏: 力扣hot100 CLinuxGitMySQL心向往之行必能至LRULeast Recently Used最近最少使用缓存是操作系统、数据库和后端开发中的经典缓存淘汰策略也是面试中高频手撕算法题。本文将从设计思路、数据结构选型到代码实现一步步拆解让你彻底掌握 LRU 缓存的核心逻辑。一、什么是 LRU 缓存LRU 缓存的核心思想是当缓存容量不足时优先删除最近最少使用的数据保证热点数据始终留在缓存中。它需要满足两个核心操作get(key)查询 key 对应的 value若不存在则返回 -1若存在将该数据标记为「最近使用」。put(key, value)插入或更新 key-value 对若缓存已满先删除「最近最少使用」的数据再插入新数据。性能要求get和put操作的时间复杂度必须为O(1)否则无法满足高并发场景下的性能需求。二、数据结构选型为什么是「双向链表 哈希表」要实现 O (1) 复杂度单一数据结构无法满足需求我们需要组合使用两种结构表格数据结构作用优势双向链表 (std::list)维护数据的「使用时序」头部存最近使用数据尾部存最久未使用数据支持 O (1) 时间内移动节点、删除尾部节点、头部插入节点哈希表 (std::unordered_map)快速定位数据以 key 为键存储对应链表节点的迭代器实现 O (1) 时间查找任意节点为什么不用单向链表单向链表无法在 O (1) 时间内删除中间节点需要遍历找到前驱节点而双向链表可以直接通过节点指针找到前驱完美适配「移动节点到头部」和「删除尾部节点」的操作。为什么哈希表要存迭代器迭代器是指向链表节点的「指针」移动节点时迭代器不会失效因此无需更新哈希表直接复用即可保证了操作的高效性。三、C 代码实现可直接用于面试cpp运行#include list #include unordered_map using namespace std; class LRUCache { private: // 双向链表存储 key, value 对头部 最近使用尾部 最久未使用 listpairint, int cache_list; // 哈希表key - 链表节点迭代器O(1) 定位节点 unordered_mapint, listpairint, int::iterator cache_map; // 缓存最大容量 int capacity; public: // 构造函数初始化缓存容量 LRUCache(int cap) : capacity(cap) {} int get(int key) { // 1. 在哈希表中查找 key auto it cache_map.find(key); // 2. 若不存在返回 -1 if (it cache_map.end()) return -1; // 3. 若存在将节点移动到链表头部标记为最近使用 cache_list.splice(cache_list.begin(), cache_list, it-second); // 4. 返回对应 value return it-second-second; } void put(int key, int value) { // 1. 先查找 key 是否存在 auto it cache_map.find(key); if (it ! cache_map.end()) { // 1.1 存在更新 value并移动到头部 it-second-second value; cache_list.splice(cache_list.begin(), cache_list, it-second); return; } // 2. 不存在插入新节点到链表头部 cache_list.emplace_front(key, value); // 2.1 在哈希表中记录节点迭代器 cache_map[key] cache_list.begin(); // 3. 检查容量是否超限超限则删除最久未使用的节点链表尾部 if (cache_map.size() capacity) { // 3.1 先删除哈希表中的映射通过尾部节点的 key cache_map.erase(cache_list.back().first); // 3.2 再删除链表尾部节点 cache_list.pop_back(); } } };四、核心 API 深度解析1.get(int key)查询 刷新使用时序查找通过cache_map.find(key)快速定位节点时间复杂度 O (1)。不存在直接返回 -1。存在调用splice函数将节点从当前位置移动到链表头部标记为「最近使用」。splice是 O (1) 操作仅修改指针无数据拷贝效率极高。返回节点的 value。2.put(int key, int value)插入 / 更新 淘汰逻辑分两种场景处理场景 1key 已存在更新节点的 value。调用splice将节点移动到头部刷新使用时序。场景 2key 不存在在链表头部插入新节点(key, value)。在哈希表中记录 key 对应的节点迭代器。容量检查若缓存大小超过容量先删除哈希表中尾部节点的 key 映射再删除链表尾部节点最久未使用数据。五、关键细节与面试考点1. 为什么链表要存 key淘汰尾部节点时需要通过节点的 key 去哈希表中删除对应的映射否则会导致哈希表中存在无效键值对造成内存泄漏。2.splice函数的妙用cpp运行cache_list.splice(cache_list.begin(), cache_list, it-second);第一个参数目标位置链表头部。第二个参数源链表当前链表自身。第三个参数要移动的节点迭代器。效果将节点从原位置移动到头部迭代器不会失效无需更新哈希表。3. 淘汰顺序的保证链表尾部始终是「最近最少使用」的数据因此pop_back()直接删除尾部节点完美符合 LRU 策略。4. 时间复杂度分析get哈希表查找 O (1) 节点移动 O (1) → 总复杂度 O (1)。put哈希表查找 O (1) 节点插入 / 移动 O (1) 容量检查 O (1) → 总复杂度 O (1)。六、常见易错点迭代器失效问题移动节点时迭代器不会失效因此哈希表无需更新删除节点时必须先删除哈希表映射再删除链表节点。key 丢失问题链表节点必须存储 key否则无法在淘汰时删除哈希表映射。容量判断判断缓存是否超限应使用cache_map.size()与链表大小完全一致避免逻辑错误。