我挖掘了一个巨牛的 人工智能 学习网站通俗易懂风趣幽默忍不住分享一下给大家。点击跳转到网站前言面试算法题里LRU 缓存几乎是“题单必备”。它听起来不难——把最近最少用到的踢出去剩下的留着——可真到白板手写很多人会卡在一个点上get 和 put 都要求 O(1)。于是常见的画面是背过答案的人能默写“哈希表 双向链表”没背过的人只能从“用数组用 map”现场试错越试越乱。这篇文章想把真正的考点讲清楚不是记住这个数据结构而是理解为什么非得是这两个结构拼在一起。然后再往前走一步把评论区最常被追问的“如果每个键还要带过期时间呢”一起讲掉——这是把 LRU 从一道题升级成生产级缓存的经典 follow-up。1、先搞清楚题目到底在考什么力扣 146 的题干很简短设计 LRUCache实现 get(key) 和 put(key, value)容量 capacity 固定两个操作都要求 O(1)。当容量满了淘汰“最久没被用到”的那个键。表面看考点是“最近最少使用”这个语义。但它的真实约束是两个 O(1)get 要 O(1)不能靠遍历找 keyput 要 O(1)插入、更新、淘汰都不能变成 O(n)。单独用数组按 key 定位快但删除或移动要挪动元素O(n)。单独用链表插入删除快但按 key 查找要遍历O(n)。两个 O(1) 想同时成立单一数据结构都做不到所以答案注定是“组合”。2、为什么答案必须是“哈希表 双向链表”分工一句话哈希表负责“O(1) 找到节点”双向链表负责“O(1) 调整顺序”。哈希表 unordered_mapkey, 节点指针 让 get 能 O(1) 定位双向链表维护访问顺序——头是最新用到的尾是最久没用的。三个核心动作get 命中 → 把节点移到头部读到就算“刚用过”put 新键 → 插入头部超容量就删尾部put 已存在 → 更新值并移到头部。为什么必须是双向不能是单向要 O(1) 删除“任意位置”的节点单向链表每个节点只知道后一个next、不知道前一个prev删中间或尾部的节点就得从头找前驱退化成 O(n)。双向链表每个节点都有 prev删谁都一样快。为什么加哨兵节点头尾各放一个不存数据的 dummy 节点让“删头、删尾、插头”都不用判空代码干净很多也不容易出边界 bug。3、C 完整实现原题下面这版是面试里最好背、也最好讲的手写版节点带 prev 和 next哈希表存 key 到节点指针哨兵头尾兜底。#include unordered_map class LRUCache { private: struct Node { int key, val; Node *prev, *next; Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {} }; int cap; Node *head, *tail; // 哨兵节点 std::unordered_mapint, Node* mp; void removeNode(Node* n) { // 从链表中摘除 n-prev-next n-next; n-next-prev n-prev; } void addToHead(Node* n) { // 头插 n-prev head; n-next head-next; head-next-prev n; head-next n; } void moveToHead(Node* n) { removeNode(n); addToHead(n); } public: LRUCache(int capacity) : cap(capacity) { head new Node(0, 0); tail new Node(0, 0); head-next tail; tail-prev head; } int get(int key) { auto it mp.find(key); if (it mp.end()) return -1; Node* n it-second; moveToHead(n); // 读到就算“最近使用” return n-val; } void put(int key, int value) { auto it mp.find(key); if (it ! mp.end()) { // 已存在更新值并移到头部 Node* n it-second; n-val value; moveToHead(n); return; } Node* n new Node(key, value); mp[key] n; addToHead(n); if ((int)mp.size() cap) { // 超容量淘汰最久未用尾部 Node* lru tail-prev; removeNode(lru); mp.erase(lru-key); delete lru; } } };复杂度get、put 都是 O(1)空间 O(capacity)。一句话记住做法命中就移到头满了就删尾。注意删除的时候不仅要删除结点还要将hash表中的key-value也要对应着删除4、面试官通常追着问的四件事为什么必须是双向链表——要 O(1) 删任意节点必须有前驱指针单向做不到02 已展开。为什么 get 也要移动节点——这正是 LRU 的语义只要被访问过就算“最近使用”。很多实现 get 只返回值、不动顺序样例能过但语义是错的。你主动点出这一点通常会被认为是真懂。容量是 0 怎么办——哨兵节点不进 map所以 put 时 mp.size() 不会因哨兵虚增但要注意别在链表只剩哨兵时去删“尾部”那会误删哨兵。更稳妥是构造时对 capacity 先做合法性处理。并发怎么办——最直接是整棵结构加一把互斥锁锁 get 和 put。想细一点用分段锁再进一步真实系统常常用近似方案换并发度见 05。5、进阶版带过期时间的 LRU 缓存评论区里被问得最多的 follow-up就是把 LRU 升级成“带过期时间”的缓存——很多缓存库其实同时做淘汰和过期这两件事。题目大致是在 get/put 都是 O(1) 的基础上每个键有一个 TTL存活时长键过期后 get 返回 -1并当作不存在。设计要点拆成四步节点里多加一个 expireAt过期时间戳在写入或更新时设为 now ttl删除策略先用“惰性删除”get 时顺手检查过期就删掉、返回 -1。不用专门起线程最省事面试先讲这个put 满的时候尾部正好过期就顺手清否则淘汰 LRU尾部。注意惰性删除的代价——过期的键在被访问或被淘汰之前还会占着容量。这一点主动跟面试官点出来说明你懂它的 trade-off过期语义有两种固定 TTL从上次写入起算写入即续期和滑动 TTL每次访问都顺延。先说固定 TTL 最标准滑动版就是在 get 命中时顺带更新 expireAt。什么时候必须加主动清扫过期键很多、又长期不被访问时会一直占容量直到把新键挤出去。真要上生产再补一个后台线程或定时器周期清理或在 put 满时先扫一遍过期的再淘汰。#include unordered_map #include chrono using Clock std::chrono::steady_clock; class LRUCacheWithTTL { private: struct Node { int key, val; long long expireAt; // 过期时间戳毫秒 Node *prev, *next; Node(int k, int v, long long e) : key(k), val(v), expireAt(e), prev(nullptr), next(nullptr) {} }; int cap; long long ttl; // 每个键的存活时长毫秒 Node *head, *tail; std::unordered_mapint, Node* mp; static long long nowMs() { return std::chrono::duration_caststd::chrono::milliseconds( Clock::now().time_since_epoch()).count(); } bool isExpired(Node* n) { return nowMs() n-expireAt; } void removeNode(Node* n) { n-prev-next n-next; n-next-prev n-prev; } void addToHead(Node* n) { n-prev head; n-next head-next; head-next-prev n; head-next n; } void moveToHead(Node* n) { removeNode(n); addToHead(n); } public: LRUCacheWithTTL(int capacity, long long ttlMs) : cap(capacity), ttl(ttlMs) { head new Node(0, 0, 0); tail new Node(0, 0, 0); head-next tail; tail-prev head; } int get(int key) { auto it mp.find(key); if (it mp.end()) return -1; Node* n it-second; if (isExpired(n)) { // 惰性删除命中但已过期 removeNode(n); mp.erase(key); delete n; return -1; } moveToHead(n); return n-val; } void put(int key, int value) { long long now nowMs(); auto it mp.find(key); if (it ! mp.end()) { // 更新续期并移到头部 Node* n it-second; n-val value; n-expireAt now ttl; moveToHead(n); return; } Node* n new Node(key, value, now ttl); mp[key] n; addToHead(n); if ((int)mp.size() cap) { // 超容量淘汰尾部可能已过期 Node* lru tail-prev; removeNode(lru); mp.erase(lru-key); delete lru; } } };这版用的是固定 TTL 惰性删除 尾淘汰结构和原题几乎一致只是节点多了个时间戳。6、进阶版容易踩的坑时间戳类型别用 int毫秒级时间戳很容易超范围用 long long计时器优先用 std::chrono::steady_clock它单调递增不受系统改时间影响。get 命中但已过期先删节点再返回 -1千万不要把它移到头部——它都不该存在了。过期节点仍算容量这是惰性删除的代价前面说过如果只删不勤容量可能被一堆“死键”占满。更新 key 时记得刷新 expireAt 并移到头部否则新值很快“过期”行为不符合预期。删节点时 map 和链表要同步删漏掉 map.erase 会让 key 一直能查到漏掉链表删除会让链表残留脏指针。结尾以后遇到缓存题先问自己三件事把这两版讲完其实你已经掌握了一套可迁移的判断而不是背下来的答案。以后遇到缓存、淘汰、限流这类题先问自己三件事要不要 O(1)要基本就是“哈希表 某种有序结构”的组合有没有过期时间有加时间戳 惰性删除起步再谈主动清扫并发重不重要重就接受“近似”——像 Redis 那样牺牲一点精确度换吞吐。把这三问想清楚LRU 就不再是一道孤立题。下次面试官换着花样问 LFU、带过期的缓存、分布式缓存你至少知道该从哪里下手。