LRU CacheLeast Recently Used最近最少使用缓存算得上是C面试里出镜率最高的手写题之一但同时也是工程里真正派得上用场的东西。它不是让你背一个玄学的算法而是把一个很朴素的直觉变成代码当空间不够的时候优先淘汰掉最久没人碰的数据。这篇文章我会从问题本身的定义讲起把“哈希表加双向链表”这套组合为什么成立、完整代码怎么写、运行时会踩哪些坑全部讲透。适合三类人看准备C面试的人、需要给项目加缓存的人以及想通过这个小项目把数据结构和算法真正串起来的初学者。1. LRU Cache是什么一个缓存淘汰问题两个核心操作1.1 真实世界里的LRU从浏览器标签页到数据库缓冲池先别看代码想想日常场景。你用手机刷应用后台任务列表里总是显示最近用过的应用如果你开了一大堆应用系统就会把最久没打开的那个收掉。再比如你翻开一本厚字典常查的几页贴了标签偶尔翻到一页很久没看的内容过段时间整理时最先被拿掉的就是那些长期没人碰的页。这就是LRU的直觉——最近用过的数据接下来也很有可能再用很久没人碰的大概率以后也用不上了。这个直觉在真实系统里到处可见。数据库的缓冲池用来缓存热数据页Redis作为内存缓存时就有LRU淘汰策略操作系统的页面置换也借鉴了类似的思想浏览器缓存那些图片和脚本资源时同样会限制容量并淘汰旧内容。与其反复从慢速存储里取数据不如把高频数据留在内存里用LRU来决定“谁该滚蛋”。理解了这一点你就知道LRU Cache并不是一道孤立的面试题而是缓存设计里最经典的地基。1.2 算法本质get和put背后的那套时序规则LRU Cache对外就是个键值对容器但比普通的std::map多了一套约束核心操作只有两个get(key)根据key取value。如果key存在这个key就变成“最近使用过的”返回值。put(key, value)写入或更新键值对。新写入的key同样变成“最近使用过的”。如果容器已经满了要把“最久未使用”的那个键值对淘汰掉。难点在于“维护时序”。普通哈希表或树形Map只管数据的存放和查找不管谁先来谁后来LRU则必须把访问顺序记录下来而且这个维护动作不允许拖慢速度。下面这条要求是这类题目的灵魂要求get和put的平均时间复杂度都是O(1)。这是整个实现方案设计的出发点。所有结构选型、代码细节都是为了同时满足“查找快”和“维护顺序”这两个需求。2. 数据结构选型为什么这个经典组合是“哈希表 双向链表”2.1 只用哈希表行不通std::unordered_map可以在平均O(1)内完成查找和插入听起来很合适。但它内部存储是无序的你无法回答“哪个key最久没被访问”。有人会说可以给每个节点加一个时间戳每次访问都更新它的时间满了以后遍历一遍找最小时间戳删除。这个方案的问题是删除时得遍历全部数据复杂度是O(n)而且时间戳只能表示“先后”不能方便地做到“把最近访问的挪到最前面”。哈希表适合解决“按名字找人”的问题却不擅长解决“谁最久没出现”的顺序问题。所以LRU需要另一个数据结构专门承担时序职责。2.2 只用链表也差点意思双向链表可以很好地表达顺序头部代表最近使用尾部代表最久未使用。插入新节点放头部是O(1)满了删尾部也是O(1)。可是如果要淘汰某个key链表本身无法快速定位这个节点——除非从头到尾遍历一遍这又是O(n)。恰恰是这个问题哈希表擅长。哈希表负责通过key快速找到链表中的节点链表负责维护准确的时序两者互补缺一不可。2.3 组合之后的完整工作链路当get(key)发生时在哈希表里查key拿到对应的链表节点指针O(1)。如果节点不在链表头部就把节点从当前链表位置摘下来插到链表头部。返回节点里的value。当put(key, value)发生时在哈希表里查key。如果key已存在更新节点的value然后把节点挪到链表头部。这里注意哈希表的key不需要变化因为key本身没变只是值变了。如果key不存在先检查链表是否已满。如果满了就把链表尾部的节点摘下来同时把哈希表里对应的key删掉然后创建新节点插入链表头部再放进哈希表。这里有一个关键选择为什么非要用双向链表单向不行吗因为要从链表中删除任意一个节点需要知道它的前驱节点。单向链表拿到当前节点后无法O(1)拿到前驱只能从头重新遍历双向链表每个节点都保存着前驱和后继摘除自身天然就是O(1)。2.4 关于复杂度需要诚实一点整个方案的平均时间复杂度是O(1)这里的“平均”是基于哈希表std::unordered_map的平均行为。极端情况下如果哈希函数写得特别差大量key碰撞到同一个桶里查找会退化成O(n)。工程里这种情况很罕见面试时如果能主动点出“平均O(1)、最坏O(n)”会显得你对哈希表的理解更扎实。空间复杂度方面哈希表存一份key和指针链表存一份key和value总体是O(capacity)。3. 手写实现一个能用、能过面试的C LRU Cache3.1 第一步设计节点和类接口面试手写如果用std::list会省很多事但为了把数据结构讲明白我先给出手写双向链表版本这也是最能展示指针基本功的写法。我们定义一个模板类key和value都交给模板参数决定。template typename K, typename V class LRUCache { private: struct Node { K key; V value; Node* prev; Node* next; Node(const K k, const V v) : key(k), value(v), prev(nullptr), next(nullptr) {} }; std::unordered_mapK, Node* table; Node* head; // 哨兵节点head-next 指向最近使用的节点 Node* tail; // 哨兵节点tail-prev 指向最久未使用的节点 int capacity_; int size_ 0; };用哨兵节点是减少边界判断的经典技巧。如果不用哨兵当头节点或者尾节点为空时每次插入删除都要写一堆判断。用head和tail两个哨兵节点后空链表里的首尾操作和中间操作逻辑完全一样。3.2 第二步链表核心操作——摘除、挂头、淘汰链表相关的原子操作有三个先把它们封装好后面的get和put就是组合调用。// 把某个节点从链表中摘除 void remove(Node* node) { node-prev-next node-next; node-next-prev node-prev; } // 把节点挂到链表头部即 head 与 head-next 之间 void addToFront(Node* node) { node-next head-next; node-prev head; head-next-prev node; head-next node; } // 节点已在链表里则摘除后重新挂头部 void moveToFront(Node* node) { if (node-prev head) { return; // 已经在头部不做无意义操作 } remove(node); addToFront(node); }这三个函数都不涉及哈希表纯粹是链表的指针操作。写指针操作时最容易犯的错误就是更新顺序错乱后面第6节我会专门讲。这里只需要记住一个原则先处理旧指针关系再接新指针并且每个节点的prev和next都要被正确赋值。淘汰最久未使用的节点就是取tail-prev先从链表摘除再从哈希表删除最后释放节点内存Node* removeLast() { if (tail-prev head) { return nullptr; // 链表为空 } Node* victim tail-prev; remove(victim); return victim; }3.3 第三步get与put的完整逻辑get的逻辑核心是哈希表查找加链表前移V get(const K key) { auto it table.find(key); if (it table.end()) { return V{}; } Node* node it-second; moveToFront(node); return node-value; }这里有个约定问题key不存在时返回什么C不像Java有Optional最简单的做法是返回值类型的默认构造对象V{}。但对于int这类类型返回0可能和缓存里真实的0值混淆所以生产级代码建议后面用std::optional或者把接口改成bool get(const K, V)。基础版本先保持简洁我会在面试追问那节展开。put的逻辑要区分“key已存在”和“key不存在”两条路径同时处理容量限制void put(const K key, const V value) { if (capacity_ 0) { return; } auto it table.find(key); if (it ! table.end()) { Node* node it-second; node-value value; moveToFront(node); return; } if (size_ capacity_) { Node* victim removeLast(); if (victim) { table.erase(victim-key); delete victim; --size_; } } Node* node new Node(key, value); table[key] node; addToFront(node); size_; }这里有个容易被忽略的细节更新已存在的key时千万不要把旧节点从哈希表里erase掉再重建新节点。直接改节点里的value字段就行因为哈希表里存储的是Node*指针节点还是那个节点只是内容变了哈希表无需任何变化。3.4 完整代码与复杂度说明把构造函数、析构函数和拷贝控制补上就是一个能直接编译运行的完整版本#include unordered_map #include algorithm template typename K, typename V class LRUCache { private: struct Node { K key; V value; Node* prev; Node* next; Node(const K k, const V v) : key(k), value(v), prev(nullptr), next(nullptr) {} }; std::unordered_mapK, Node* table; Node* head; Node* tail; int capacity_; int size_ 0; void remove(Node* node) { node-prev-next node-next; node-next-prev node-prev; } void addToFront(Node* node) { node-next head-next; node-prev head; head-next-prev node; head-next node; } void moveToFront(Node* node) { if (node-prev head) return; remove(node); addToFront(node); } Node* removeLast() { if (tail-prev head) return nullptr; Node* victim tail-prev; remove(victim); return victim; } public: LRUCache(int capacity) : capacity_(std::max(0, capacity)) { head new Node(K{}, V{}); tail new Node(K{}, V{}); head-next tail; tail-prev head; } ~LRUCache() { Node* cur head; while (cur) { Node* next cur-next; delete cur; cur next; } } LRUCache(const LRUCache) delete; LRUCache operator(const LRUCache) delete; V get(const K key) { auto it table.find(key); if (it table.end()) { return V{}; } Node* node it-second; moveToFront(node); return node-value; } void put(const K key, const V value) { if (capacity_ 0) return; auto it table.find(key); if (it ! table.end()) { Node* node it-second; node-value value; moveToFront(node); return; } if (size_ capacity_) { Node* victim removeLast(); if (victim) { table.erase(victim-key); delete victim; --size_; } } Node* node new Node(key, value); table[key] node; addToFront(node); size_; } };关于析构函数这里用的是手动遍历释放。更优雅的做法可以用std::unique_ptr管理节点但手写链表加裸指针是面试最常见的要求所以保留原始版本。拷贝构造函数我直接删掉了因为涉及深拷贝实现起来啰嗦且容易出错真实工程里如果非要用再单独实现拷贝和赋值。复杂度回顾get是哈希表查找O(1)加链表移动O(1)put是查找O(1)加上最多一次节点删除和头部插入都是O(1)。4. STL版本更工程化的写法4.1 基于std::list的精简实现手写链表的代码能让你彻底掌握指针操作但生产环境里我更推荐直接用std::list。它的优点是实现短、可读性好、内存管理交给标准库不易出错。核心思路是用std::list保存键值对用unordered_map保存key到list迭代器的映射#include list #include unordered_map template typename K, typename V class LRUCacheSTL { private: std::liststd::pairK, V items; std::unordered_mapK, typename std::liststd::pairK, V::iterator table; size_t capacity_; public: LRUCacheSTL(size_t capacity) : capacity_(capacity) {} V get(const K key) { auto it table.find(key); if (it table.end()) { return V{}; } // splice 把节点整体挪到链表头部O(1) items.splice(items.begin(), items, it-second); return it-second-second; } void put(const K key, const V value) { auto it table.find(key); if (it ! table.end()) { it-second-second value; items.splice(items.begin(), items, it-second); return; } if (items.size() capacity_) { auto last items.end(); --last; table.erase(last-first); items.erase(last); } items.emplace_front(key, value); table[key] items.begin(); } };std::list::splice是这里的关键它可以在常数时间内把指定迭代器指向的元素转移到另一个list的指定位置不需要复制和销毁节点。配合unordered_map里保存的迭代器整体逻辑和手写链表版本完全一致代码却短了将近一半。4.2 手写版 vs STL版到底怎么选直接说结论。如果场景是面试答题我建议会手写双向链表版因为它能展示你对内存管理和指针操作的理解很多面试官就是想看这个。如果场景是写生产代码我会用STL版本因为它足够正确、不容易有内存错误而且维护成本低。对比维度手写双向链表版std::list版代码量长约100行短约50行内存管理手动new/delete容易泄漏标准库自动管理性能略好可精细控制接近splice本身是O(1)出错概率指针操作容易翻车低面试展示加分项也可以但显得不够底层实际性能上两者差异不大因为核心操作都是固定的指针搬移。手写版多出来的优势只是少了一层迭代器封装的内存开销但这点开销通常可忽略。所以我的建议是面试用手写版上线用STL版两者都值得掌握。5. 面试追问与生产级改造5.1 面试官爱问的几个细节这部分是我总结的实战经验每个问题背后都对应一个真实的设计决策。第一个问题为什么get一个不存在的key时返回V{}不安全如果你缓存的是查询结果value是int、std::string这类类型V{}构造出来的0或空字符串看起来和真实缓存值完全一样调用方无法区分“缓存没命中”和“缓存命中了但值就是0”。工程上更健壮的接口是bool get(const K, V value_out)或者返回std::optionalV。面试时能主动讨论这个设计缺陷比背出代码更让面试官认可。第二个问题容量为0怎么处理我的代码里在构造函数中capacity_ std::max(0, capacity)并且put里直接判断capacity_ 0就返回。如果没有这个判断某次put会先走“链表满”分支试图从空链表里淘汰节点最终导致空指针问题。第三个问题更新已有key时哈希表需要重新处理吗不需要。哈希表存的是节点指针节点还是同一个只是value改了哈希值取决于keykey没变就不用管。这正是“哈希表负责定位链表负责排序”这个分工的体现。第四个问题为什么不把链表和哈希表的角色互换比如用std::list存key用unordered_map存key到value以及位置的映射这种做法也可以代码实现略有不同本质思路一样。面试时只要能把“哈希表定位、链表排序”的分工讲清楚用什么具体方案是次要的。5.2 线程安全不能直接裸奔基础版没有考虑多线程在多线程环境下两个线程同时put可能让链表指针错乱甚至崩溃。最直接的做法是加一把互斥锁#include mutex template typename K, typename V class ThreadSafeLRUCache { // 复用前面的 LRUCache mutable std::mutex mtx_; public: V get(const K key) { std::lock_guardstd::mutex lock(mtx_); return cache_.get(key); } void put(const K key, const V value) { std::lock_guardstd::mutex lock(mtx_); cache_.put(key, value); } private: LRUCacheK, V cache_; };简单加锁的代价是并发度低所有读写都串行化。读多写少场景可以把std::mutex换成std::shared_mutex允许多个读线程并发写线程独占。无锁方案不是不能做但涉及到并发哈希表和无锁链表的组合正确性验证非常复杂工程里绝大多数LRU Cache加一把锁就够了。5.3 给缓存加上过期时间TTLLRU只解决容量问题不解决数据时效问题。比如缓存的用户信息5分钟后失效即使容量没满也得让旧数据自动过期。最常见的做法是在节点里加一个时间戳字段struct Node { K key; V value; Node* prev; Node* next; std::chrono::steady_clock::time_point expire_at; };get时检查当前时间是否超过expire_at超了就当作key不存在顺手删掉节点并返回未命中。这就是“惰性过期”——不主动扫描遇到才清理。如果过期数据量很大想主动控制内存可以加一个后台线程定期清理或者限制每次put时顺带清理少量过期节点。这个设计在Redis、Java Caffeine里都有类似影子作为面试题升华非常好用。5.4 还能再优化什么第一个优化方向是减少内存分配。频繁new和delete结点会导致内存碎片和性能抖动工程上可引入简单的节点对象池复用被淘汰节点的内存。第二个方向是提前reserve哈希表容量避免插入时频繁rehash。第三个方向是针对特定场景换淘汰策略比如LRU-K统计访问次数达到K次才进入缓存能避免一次性数据污染整个缓存2Q算法和ARC也都是对LRU的改进。普通LRU适合“访问局部性明显”的场景如果你的数据是一次性流量特别大基础LRU反而可能把热点数据冲掉。6. 常见陷阱、调试技巧与我的实操经验6.1 指针操作里最容易翻车的几个地方我写这个题目的次数不下20次翻车记录主要集中在三处。第一处是moveToFront时忘记判断节点是否已经在头部。没有这个判断每次get都会执行一次“先摘除再挂头”逻辑结果没错但少了一次多余操作。更重要的问题是如果head-next正好就是该节点remove把它的前后指针关系重新接线再加addToFront会形成自循环肉眼很难发现。第二处是哨兵节点的处理。以前我不用哨兵结果每次都要判断head nullptr、tail nullptr代码长了三倍还容易漏判断。用了两个哨兵节点之后所有边界情况都统一了这个经验强烈推荐。第三处是淘汰节点后忘记从哈希表删除。链表里节点被删除了但哈希表还留着那个key后面再来访问就会拿到野指针。写put的时候table.erase(victim-key)这行绝不能省。6.2 内存泄漏排查与工具使用手写链表版本最容易出的问题就是内存泄漏。如果只delete了淘汰的节点但是析构函数里忘了遍历释放剩余节点整个缓存销毁时就会泄漏一整片内存。排查时建议用AddressSanitizerg -fsanitizeaddress -g -O0 lru_cache.cpp -o lru_test跑一遍测试用例ASAN会直接报告内存泄漏和越界读写。另一个实用技巧是在链表关键操作后打印一次全链表的key顺序验证顺序是否符合预期。比如依次执行put(1,1), put(2,2), get(1), put(3,3)预期链表顺序是3、1、2打印出来一眼就能看出问题。6.3 性能上的一点实测心得我在一个后端模块里用STL版LRU缓存数据库查询结果容量设为2000缓存命中后读取耗时从几毫秒降到微秒级。这里有个很现实的取舍容量不是越大越好。LRU的淘汰粒度是单条key而哈希表扩容、链表节点内存分配都是成本。容量太小命中率上不去容量太大占用内存过多还可能因为rehash导致偶发延迟。实际调参时我习惯先统计业务访问的key总量再按“热点数据占总量约20%”来估算容量上线后持续观察命中率曲线再微调。调试地址Sanitizer这一类工具很多人平时不用但在手写链表题目上真的救命。我建议每个C开发者都把这个工具养成肌肉记忆写链表必开ASAN跑一遍能省下排查指针错误的大量时间。最后再分享一个小技巧。你写LRU时的第一个版本不要先去背代码而是先画一个朴素的双向链表加哈希表的示意图然后把get和put的每一步操作对应到图上。这张图画明白了代码怎么写都不会乱。我第一次踏实掌握LRU就是从画了半小时图开始的比反复抄十遍代码都管用。C的世界里结构想清楚剩下的只是把思想翻译成语言而已。