一、项目背景详细介绍
在现代软件系统中，缓存（Cache）是提升系统性能最重要的手段之一。
无论是：
Web 服务
数据库系统
操作系统
分布式系统
中间件框架
都大量使用缓存来解决以下问题：
磁盘 I/O 慢
网络访问延迟高
重复计算成本大
然而，缓存的空间通常是有限的，当缓存满了以后，必须有一套合理的淘汰策略，决定哪些数据应该被移除。
常见缓存淘汰算法包括：
FIFO（先进先出）
LFU（最少使用）
LRU（最近最少使用，最经典）
ARC / LIRS（复杂优化版本）
其中，LRU（Least Recently Used）是：
工程实践中使用最广泛
思想最直观
面试和实战出现频率最高
LRU 的核心思想可以概括为一句话：
如果一个数据最近被访问过，那么将来被访问的概率也更高
本项目目标是：
使用 C++ 从零实现一个高效的 LRU 缓存结构，做到 O(1) 时间复杂度
二、项目需求详细介绍
2.1 功能需求
实现一个通用的LRU 缓存类
支持以下核心操作：
get(key)：获取缓存数据put(key, value)：插入或更新缓存数据
当缓存容量满时：
自动淘汰最近最少使用的数据
缓存操作时间复杂度：
O(1)
2.2 技术要求
编程语言：C++
使用 STL：
unordered_maplist
不允许使用暴力遍历
强调数据结构设计思想
代码可读性强、注释详尽
2.3 设计要求
面向教学设计
所有代码：
集中在一个代码块
使用注释模拟文件结构
方法职责清晰
适合作为：
面试讲解模板
系统设计入门示例
三、相关技术详细介绍
3.1 LRU 算法核心思想
LRU（Least Recently Used）算法的本质是：
淘汰“最近最久未被访问”的数据
关键问题在于：
如何快速判断“最近使用”
如何在容量满时快速删除“最久未使用”
这两个问题决定了数据结构的选型。
3.2 为什么单一数据结构不够？
仅使用数组 / 链表
查找慢（O(n)）
不满足性能要求
仅使用哈希表
无法维护访问顺序
无法判断“最近 / 最久”
3.3 LRU 的经典组合结构
LRU 的最优解是：
双向链表 + 哈希表
| 数据结构 | 作用 |
|---|---|
| 双向链表 | 维护访问顺序 |
| 哈希表 | O(1) 查找数据 |
3.4 双向链表的作用
链表头部：最近访问
链表尾部：最久未访问
删除 / 插入节点：O(1)
3.5 哈希表的作用
key → 链表节点
支持 O(1) 定位
避免链表遍历
四、实现思路详细介绍
4.1 整体架构设计
LRUCache 主要包含以下成员：
缓存容量
capacity双向链表
list哈希表
unordered_map
4.2 核心操作流程
1️⃣ get(key)
如果 key 不存在：
返回失败
如果 key 存在：
将该节点移动到链表头部
返回 value
2️⃣ put(key, value)
如果 key 已存在：
更新 value
移动到链表头部
如果 key 不存在：
如果缓存已满：
删除链表尾部节点
同步删除哈希表
插入新节点到链表头部
4.3 时间复杂度分析
| 操作 | 时间复杂度 |
|---|---|
| get | O(1) |
| put | O(1) |
五、完整实现代码
/**************************************************** * 文件名：LRUCache.cpp * 描述：C++ 实现 LRU 缓存（O(1) 时间复杂度） ****************************************************/ #include <iostream> #include <unordered_map> #include <list> using namespace std; /**************************************************** * LRU 缓存类 ****************************************************/ class LRUCache { public: // 构造函数 LRUCache(int cap) : capacity(cap) {} /************************************************ * 获取缓存数据 ************************************************/ int get(int key) { auto it = cacheMap.find(key); if (it == cacheMap.end()) { // 未命中 return -1; } // 命中：移动到链表头部（最近使用） cacheList.splice(cacheList.begin(), cacheList, it->second); return it->second->second; } /************************************************ * 插入或更新缓存数据 ************************************************/ void put(int key, int value) { auto it = cacheMap.find(key); if (it != cacheMap.end()) { // 已存在：更新值并移动到头部 it->second->second = value; cacheList.splice(cacheList.begin(), cacheList, it->second); } else { // 不存在：检查容量 if (cacheList.size() >= capacity) { // 淘汰最久未使用节点（链表尾） int oldKey = cacheList.back().first; cacheList.pop_back(); cacheMap.erase(oldKey); } // 插入新节点到链表头部 cacheList.emplace_front(key, value); cacheMap[key] = cacheList.begin(); } } private: int capacity; // 双向链表：key-value list<pair<int, int>> cacheList; // 哈希表：key -> 链表迭代器 unordered_map<int, list<pair<int, int>>::iterator> cacheMap; }; /**************************************************** * 测试示例 ****************************************************/ int main() { LRUCache cache(2); cache.put(1, 10); cache.put(2, 20); cout << cache.get(1) << endl; // 10 cache.put(3, 30); // 淘汰 key=2 cout << cache.get(2) << endl; // -1 cout << cache.get(3) << endl; // 30 return 0; }六、代码详细解读（仅解读方法作用）
LRUCache：封装整个缓存逻辑get：访问缓存并更新访问顺序put：插入 / 更新数据并处理淘汰逻辑list：维护访问时间顺序unordered_map：提供 O(1) 查找能力
七、项目详细总结
通过该项目，你已经系统掌握：
LRU 算法的核心思想
双向链表 + 哈希表的经典组合
O(1) 缓存设计技巧
工程级缓存淘汰策略
面试与实战通用实现模板
这是：
数据结构 → 系统设计 → 性能优化
的关键连接点。
八、项目常见问题及解答
Q1：为什么必须用双向链表？
A：单向链表无法 O(1) 删除中间节点。
Q2：为什么不用 vector？
A：vector 删除中间元素是 O(n)。
Q3：LRU 线程安全吗？
A：当前实现不是，需加锁或使用并发结构。
九、扩展方向与性能优化
模板化支持任意 key / value 类型
增加线程安全（mutex / RWLock）
支持过期时间（TTL）
实现 LFU / ARC 算法
用于数据库 / HTTP 缓存系统
