目录
一、LRU 缓存的核心诉求
二、数据结构选型与设计思路
1. 双向链表：维护访问顺序的 “时间轴”
2. 哈希表：实现 key 的 O (1) 寻址
3. 组合设计：“哈希表 + 双向链表” 的协同工作
三、代码实现
1. 类结构定义
2. get 方法实现：查询并更新访问顺序
3. put 方法实现：插入、更新与容量控制
四、复杂度与边界场景分析
1. 时间复杂度
2. 边界场景处理
五、测试验证与工程价值
六、总结
在高并发与大数据场景中，缓存是提升系统性能的关键手段，而 LRU（Least Recently Used，最近最少使用） 作为最经典的缓存淘汰策略之一，其设计与实现蕴含着深刻的工程智慧。本文将从底层原理出发，详细拆解 LRU 缓存的设计思路，并提供可直接落地的 C++ 实现。
一、LRU 缓存的核心诉求
LRU 策略的核心逻辑是：当缓存容量不足时，优先淘汰 “最久未被访问” 的缓存项。要实现这一策略，我们需要解决两个关键问题：
- 快速查询：给定
key，需在 O (1) 时间内判断是否存在并获取value。 - 快速维护访问顺序：每次访问（
get或put）后，需将缓存项标记为 “最近使用”；当容量不足时，需快速找到并淘汰 “最久未使用” 的项。
若仅用哈希表，虽能满足 “快速查询”，但无法高效维护访问顺序；若仅用链表，查询操作会退化为 O (n)，性能无法接受。因此，我们需要一种组合数据结构来突破这一困境。
二、数据结构选型与设计思路
1. 双向链表：维护访问顺序的 “时间轴”
使用双向链表存储缓存项，节点按 “最近使用” 到 “最久未使用” 的顺序排列：
- 链表头部：最近被访问的缓存项。
- 链表尾部：最久未被访问的缓存项（淘汰时的目标）。
双向链表的优势在于：
- 节点移动（标记为 “最近使用”）的时间复杂度为 O (1)（只需调整指针）。
- 淘汰操作（删除尾部节点）的时间复杂度为 O (1)。
2. 哈希表：实现 key 的 O (1) 寻址
使用 ** 哈希表（unordered_map）** 存储 key 到 “链表节点迭代器” 的映射，这样可以：
- 快速判断
key是否存在（O (1) 时间）。 - 直接定位到对应的链表节点（O (1) 时间），从而避免遍历链表的开销。
3. 组合设计：“哈希表 + 双向链表” 的协同工作
哈希表的 value 是链表节点的迭代器，这样可以在 O (1) 时间内完成：
- 查询（
get）：通过哈希表找到节点，返回value并将节点移到链表头部。 - 插入 / 更新（
put）：若key存在则更新值并移到头部；若不存在则插入新节点到头部，若容量不足则删除尾部节点。
三、代码实现
1. 类结构定义
1class LRUCache { 2public: 3 // 构造函数：初始化缓存容量 4 LRUCache(int capacity) : _capacity(capacity) {} 5 6 // 查询操作：O(1) 时间复杂度 7 int get(int key); 8 9 // 插入/更新操作：O(1) 时间复杂度 10 void put(int key, int value); 11 12private: 13 // 链表节点迭代器类型（指向存储 key-value 的双向链表节点） 14 using ListIter = std::list<std::pair<int, int>>::iterator; 15 16 std::unordered_map<int, ListIter> _hashMap; // key -> 链表节点迭代器 17 std::list<std::pair<int, int>> _lruList; // 双向链表，维护访问顺序 18 int _capacity; // 缓存最大容量 19}; 20
2. get 方法实现：查询并更新访问顺序
1int LRUCache::get(int key) { 2 auto it = _hashMap.find(key); 3 if (it == _hashMap.end()) { 4 return -1; // key 不存在 5 } 6 7 // 将节点移到链表头部（标记为最近使用） 8 _lruList.splice(_lruList.begin(), _lruList, it->second); 9 return it->second->second; // 返回 value 10} 11
splice是双向链表的核心操作，可在 O (1) 时间内将节点移动到任意位置（这里移到头部）。
3. put 方法实现：插入、更新与容量控制
1void LRUCache::put(int key, int value) { 2 auto it = _hashMap.find(key); 3 if (it != _hashMap.end()) { 4 // 情况1：key 已存在，更新 value 并标记为最近使用 5 ListIter node = it->second; 6 node->second = value; // 更新 value 7 _lruList.splice(_lruList.begin(), _lruList, node); 8 } else { 9 // 情况2：key 不存在，插入新节点 10 // 若容量已满，淘汰最久未使用的节点（链表尾部） 11 if (_lruList.size() == _capacity) { 12 auto tail = _lruList.back(); 13 _hashMap.erase(tail.first); // 从哈希表中删除 14 _lruList.pop_back(); // 从链表中删除 15 } 16 // 插入新节点到链表头部 17 _lruList.push_front({key, value}); 18 _hashMap[key] = _lruList.begin(); // 哈希表记录映射 19 } 20} 21
- 插入新节点前，若容量已满，需先删除链表尾部的 “最久未使用” 节点，并同步从哈希表中移除对应的
key。
四、复杂度与边界场景分析
1. 时间复杂度
get操作：O (1)（哈希表查询 + 链表节点移动）。put操作：O (1)（哈希表插入 / 删除 + 链表节点移动 / 删除）。
这一复杂度满足了题目中 “O (1) 平均时间复杂度” 的要求。
2. 边界场景处理
- 空缓存 / 空 key：
get操作返回 -1。 - 容量为 1：每次插入都会淘汰之前的节点，保证缓存中始终只有最新的一个项。
- 重复
put同一 key：会更新其value并将其标记为 “最近使用”。
五、测试验证与工程价值
我们通过一个典型场景验证实现的正确性：
1int main() { 2 LRUCache cache(2); // 容量为 2 的 LRU 缓存 3 cache.put(1, 1); 4 cache.put(2, 2); 5 cout << cache.get(1) << endl; // 输出 1（1 被标记为最近使用） 6 cache.put(3, 3); // 容量已满，淘汰最久未使用的 2 7 cout << cache.get(2) << endl; // 输出 -1（2 已被淘汰） 8 cache.put(4, 4); // 容量已满，淘汰最久未使用的 1 9 cout << cache.get(1) << endl; // 输出 -1（1 已被淘汰） 10 cout << cache.get(3) << endl; // 输出 3（3 被标记为最近使用） 11 cout << cache.get(4) << endl; // 输出 4（4 被标记为最近使用） 12 return 0; 13} 14
输出结果与预期完全一致，证明了实现的正确性。
六、总结
LRU 缓存的设计是 “数据结构协同作战” 的经典案例：双向链表解决了 “访问顺序维护” 的问题，哈希表解决了 “快速寻址” 的问题，二者结合让 LRU 策略在 O (1) 时间复杂度下高效运行。
这一设计思路不仅适用于算法题，更在工业级缓存系统（如 Redis 的缓存策略）中被广泛应用。理解其底层逻辑，有助于我们在复杂业务场景中设计更高效的缓存方案。
《LRU 缓存的设计与实现》 是转载文章，点击查看原文。
