146.LRU缓存这道题在力扣热题100里算是一道“面试分水岭”题目。题目标注是中等难度但我实际面试下来能在十五分钟内写对代码、又能把原理讲清楚的人比例真的不高。最常见的情况是模板背得很熟一被追问“为什么哈希表的值要存节点”“为什么必须是双向链表而不是单向链表”就开始含糊其辞。这篇文章就冲着这两个关键问题来先把缓存淘汰的业务直觉讲清楚再从复杂度和数据结构设计的角度把原因拆透最后给出C和Python两版可直接运行的完整实现顺带整理我在刷题和面试过程中沉淀下来的坑和追问。无论你是在准备求职面试还是单纯想把这套经典设计真正吃透这篇应该都能给你一些启发。1. LRU缓存到底在考你什么先理解业务再谈数据结构1.1 从真实的缓存淘汰场景说起LRULeast Recently Used最近最少使用说白了就是“优先淘汰最久没被访问的数据”。这个策略在真实系统里太常见了Redis 内存满了之后怎么选择淘汰哪些 key操作系统做页面置换时用哪种算法浏览器缓存了大量图片和脚本空间不够先清谁这些场景里 LRU 都是非常普遍的选择。背后的直觉依据是局部性原理刚被访问过的数据大概率接下来还会被访问而很长时间没碰过的数据再次被访问的概率就低得多。所以缓存容量不够时把“最久未使用”的踢出去通常是最划算的。力扣146题就是把这套策略抽象成两个接口get(key) 和 put(key, value)。get 命中时返回 value同时要把这个 key 标记为“最近刚被访问”put 时如果 key 已存在就更新 value不存在则插入新键值对一旦缓存容量已满就先淘汰那个“最久未被访问”的 key。逻辑听起来并不复杂难点全在复杂度限制上。1.2 O(1) 是硬指标为什么不能用红黑树或数组题目明确要求 get 和 put 都必须在 O(1) 平均时间复杂度内完成。注意这里不是 O(log n)也不是“尽量快一点”而是严格的常数时间。这就是为什么这道题不能用 map 这种基于红黑树的结构——哪怕红黑树的查找已经是 O(log n) 了在大容量和高并发场景下依然和 O(1) 差着一个数量级。这个约束之所以重要是因为缓存本身就是性能敏感组件。get 和 put 是缓存最核心的高频操作如果每次命中缓存还要额外付出对数级的查找代价那缓存带来的性能收益就被吃掉了一大半。实际工程里Redis 的内存淘汰、CPU 的 TLB 替换都是希望用尽可能接近常数的时间完成差一点点都会直接反映在线上响应速度上。所以刷这道题的时候脑子里要绷紧一根弦一切设计都为了让 get 和 put 保持 O(1)。1.3 哈希表和链表各自的局限组合拳才能补短板要满足 O(1) 的 get哈希表几乎是唯一选择。但哈希表有一个天生的短板它只负责“根据 key 找 value”完全不关心数据之间的先后顺序。反过来链表天然维护了顺序可以轻松知道谁在前谁在后但想在链表里查找一个 key 的位置就得从头遍历O(n)。于是很自然的思路就是把两者拼起来哈希表负责快速定位链表负责记录访问顺序。这就是“哈希表 双向链表”组合的出发点。理解了这一点后面两个“为什么”其实是同一个大问题的两面——如何在组合结构里把每个操作都维持在 O(1)。我先说第一个为什么哈希表的值不存 int而要存链表节点。2. 为什么哈希表的值必须是节点而不是 value 本身2.1 先看一个“看着能行”的错误方案很多新手第一版会写成 unordered_mapint, int再额外开一个队列记录 key 的访问顺序。get 的时候查哈希表返回 value然后把 key 重新入队put 的时候如果满了就不断从队尾尝试淘汰。这个方案看上去好像有点道理实际上到处是漏洞。举个最简单的例子get 一个已经存在的 key 之后这个 key 变成了“最近访问”需要把它挪到访问顺序的最前面。队列能做到吗做不到。队列只支持从队尾入、队首出你没法把队列中间的元素抽出来放到队首。就算不用队列改用 vector 或普通数组删除中间元素需要整体移位又是 O(n)。这条路本质上是走不通的。还有一层隐藏问题如果哈希表只存 value那么当链表需要删除某个节点时你手里只有 value 没有 key怎么从哈希表里把对应的键值对删掉理论上可以遍历哈希表找“value 等于 xxx 的 key”但 value 很可能重复而且遍历哈希表是 O(n)。所以哈希表里存的映射必须能同时拿到 key 和节点位置——最自然的做法就是让哈希表直接指向链表节点节点里同时携带 key 和 value。2.2 哈希表存节点解决的三个核心问题定位、移动、回删我把“为什么哈希表的值是节点”拆成三个具体需求缺一个都不行。第一件事是定位。get(key) 命中后必须在 O(1) 内找到这个 key 在链表中的位置。如果哈希表存的是节点指针直接 mp[key] 就拿到了节点这个节点的 prev 和 next 就在手边。如果存的只是 value你还得在链表里重新找一遍才能定位到对应节点这直接破坏了 O(1)。第二件事是移动。LRU 的灵魂操作是“把刚被访问的节点移到链表头部”。这个操作要修改节点自身的 prev、next也要修改它前驱节点的 next、后继节点的 prev。做这些操作的前提是你手里拿着节点本身而不是一个孤立的值。哈希表存节点到这一步就顺理成章了。第三件事是回删。容量满的时候要淘汰链表尾部的节点同时从哈希表里删掉对应的 key。链表尾部节点就是 tail-prev直接能拿到。可这个节点对应哪个 key如果节点结构体里存了 key 字段直接 node-key 就是答案。这也是为什么 LRU 的链表节点里必须同时存 key 和 value——value 是给 get 返回用的key 是给淘汰时回删哈希表用的。2.3 换个视角哈希表里存的其实是“节点句柄”有人又会问那我不手写链表用 C STL 的 listpairint, int哈希表存 list 的迭代器行不行答案是完全可以而且很多简洁写法就是这么干的unordered_mapint, listpairint, int::iterator。迭代器本质上就是一个“节点句柄”和手写 Node 结构体存指针是同一个思路只不过 STL 帮你把链表细节封装好了。所以解决问题的关键不是“到底存对象还是存迭代器”而是哈希表里必须保存一个“能 O(1) 定位到链表中某个节点”的句柄。这个句柄指向的一定是链表节点而不是裸的 value。一句话总结哈希表的值是节点是因为只有通过节点句柄才能在 O(1) 时间内完成定位、移动、回删这三个高频操作。理解了这一点你就不会被各种实现版本绕晕了。顺带提一个热词相关的小知识力扣上用 Python 刷题时大家习惯说 dict用 C 说 unordered_map其实它们都是哈希表的不同语言实现。Python 的 dict 在 3.7 之后虽然能维护插入顺序但 LRU 需要的是精确的“访问顺序”而不是“插入顺序”所以依然不能只用 dict必须靠链表来掌控顺序。3. 为什么必须用双向链表单向链表到底卡在哪3.1 单向链表的致命伤删除节点需要找到前驱很多人觉得链表删除节点天生是 O(1)但这个印象有一个隐藏前提——你删除的是当前节点本身或者你已经掌握了它的前驱节点。对单向链表来说每个节点只有 next 指针没有 prev想删除链表中任意一个节点必须让前驱节点的 next 跳过这个节点。可前驱怎么找只能从头开始遍历复杂度 O(n)。还有人会想到一个经典 trick删除单向链表的当前节点时不找前驱而是把后继节点的 key/value 复制到当前节点然后删除后继节点。这个技巧在部分场景下确实有效但用在 LRU 上就麻烦了。moveToHead 是要把指定节点移到头部复制数据会改变节点的“身份”哈希表里的 key 到底指向谁就乱了如果被移动的节点恰好是尾节点根本连后继都没有。所以这条路在 LRU 场景下走不通。我见过有人尝试用“单向链表 额外保存前驱指针”来绕过这个问题那就等于自己造了个不完整的双向链表指针维护反而更复杂更容易出错。与其这样不如直接上标准的双向链表。3.2 双向链表把删除和移动都变成常数时间双向链表的每个节点有 prev 和 next 两个指针删除任意节点只需要四行代码让前驱的 next 指向后继让后继的 prev 指向前驱。整个过程完全不依赖遍历O(1) 搞定。再看 moveToHead本质就是“先删除再插入头部”两个 O(1) 操作组合起来整体还是 O(1)。这个优势在 LRU 场景里是决定性的。因为 get 和 put 一旦命中都要触发 moveToHead容量满时又要删除尾部节点。如果这些操作退化成 O(n)那么在最坏情况下一次 put 可能要遍历整条链表容量越大性能越差。用双向链表每个操作的时间都是确定的、可预期的这才符合缓存组件对性能稳定性的要求。3.3 哑节点的设计用两个哨兵换掉所有边界判断写链表代码最烦的事情之一就是头尾空指针判断。链表为空时怎么办删除头节点怎么办这些边界逻辑写多了不仅代码丑还容易埋雷。LRU 缓存这里有一个非常经典的技巧在链表真正的最前面加一个虚拟头节点 dummyHead最后面加一个虚拟尾节点 dummyTail它们只当哨兵不存真实业务数据。有了这两个哑节点链表永远不会为空操作任意真实节点时都可以放心地访问 node-prev 和 node-next。插入头部时固定插在 dummyHead 和 dummyHead-next 之间删除尾部时固定删 dummyTail-prev。所有判空逻辑都被删掉了代码简化很多也少了一大类边界 bug。这道题里哑节点不是可选项而是我强烈推荐的做法。3.4 为什么不选数组、队列、堆或树我经常被问到“用数组加时间戳扫一遍找最小的行不行”“用优先队列行不行”。我把常用结构做了一张对照表看起来更直观数据结构查找指定 key删除中间元素把中间元素移到头部是否满足 O(1) 要求数组 / vectorO(1)O(n) 必须移位O(n)否单向链表O(n)O(n) 需找前驱O(n)否双向链表O(n)需配合哈希表O(1)O(1)是哈希表负责定位队列O(n)不支持不支持否堆 / 优先队列O(log n)不支持精确删除不支持精确调整否红黑树 mapO(log n)O(log n)O(log n)否所以结论很清楚唯一能在哈希表 O(1) 定位基础上、把“顺序调整”也做到 O(1) 的结构组合就是哈希表 双向链表。单向链表、数组、队列、堆都会让某个关键操作退化。这也是为什么这道题被设计成“哈希表 双向链表”的经典模板不是随便选的。4. 完整实现C 和 Python 两版逐步拆解4.1 C 手写双向链表版本先上我推荐的 C 手写版本。为什么不用 STL 的 list因为面试场景下手写双向链表能直观展示你对指针和链表结构的理解而且不少面试官会特意要求别用 STL。平时自己练习也应该手写一遍再用 STL 写一遍做对比。下面是完整代码struct Node { int key; int val; Node* prev; Node* next; Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {} }; class LRUCache { private: int cap; unordered_mapint, Node* mp; Node* dummyHead; Node* dummyTail; // 把节点从链表中摘除 void removeNode(Node* node) { node-prev-next node-next; node-next-prev node-prev; } // 把节点插到虚拟头节点后面即链表最前面 void addToHead(Node* node) { node-prev dummyHead; node-next dummyHead-next; dummyHead-next-prev node; dummyHead-next node; } // 摘除 插入 移动到头部 void moveToHead(Node* node) { removeNode(node); addToHead(node); } public: LRUCache(int capacity) : cap(capacity) { dummyHead new Node(-1, -1); dummyTail new Node(-1, -1); dummyHead-next dummyTail; dummyTail-prev dummyHead; } int get(int key) { if (mp.find(key) mp.end()) return -1; Node* node mp[key]; moveToHead(node); return node-val; } void put(int key, int value) { if (mp.find(key) ! mp.end()) { Node* node mp[key]; node-val value; moveToHead(node); } else { if (mp.size() cap) { Node* toRemove dummyTail-prev; removeNode(toRemove); mp.erase(toRemove-key); delete toRemove; } Node* newNode new Node(key, value); mp[key] newNode; addToHead(newNode); } } };几个关键点展开说一下。removeNode 里为什么可以直接 node-prev-next因为有哑节点兜底任何真实节点都有前驱和后继不需要判空。addToHead 里的四行顺序也讲究先把 node 的 prev 和 next 分别指向 dummyHead 和 dummyHead-next再把 dummyHead-next 的 prev 指向 node最后把 dummyHead-next 指向 node。这个顺序如果写乱容易出现指针悬空。put 里容量满时先拿 dummyTail-prev 作为淘汰对象然后依次执行 removeNode、mp.erase、delete。delete 是 C 特有的千万别漏——new 出来的节点不释放反复 put 会持续内存泄漏。力扣判题通常看不出这个问题但面试官一问“这里有没有内存泄漏”没答出来就很掉分。4.2 Python 版本对象引用与自动内存管理Python 写这道题结构几乎一模一样只是不需要手动管理内存代码更清爽一些class DLinkedNode: def __init__(self, key0, value0): self.key key self.value value self.prev None self.next None class LRUCache: def __init__(self, capacity: int): self.capacity capacity self.size 0 self.cache {} self.head DLinkedNode() self.tail DLinkedNode() self.head.next self.tail self.tail.prev self.head def _remove_node(self, node): node.prev.next node.next node.next.prev node.prev def _add_to_head(self, node): node.prev self.head node.next self.head.next self.head.next.prev node self.head.next node def _move_to_head(self, node): self._remove_node(node) self._add_to_head(node) def get(self, key: int) - int: if key not in self.cache: return -1 node self.cache[key] self._move_to_head(node) return node.value def put(self, key: int, value: int) - None: if key in self.cache: node self.cache[key] node.value value self._move_to_head(node) else: if self.size self.capacity: removed self.tail.prev self._remove_node(removed) del self.cache[removed.key] self.size - 1 new_node DLinkedNode(key, value) self.cache[key] new_node self._add_to_head(new_node) self.size 1Python 版最需要注意的是对象引用语义。dict 里存的 value 是 DLinkedNode 对象引用修改 node.value 修改的是对象本身链表里的数据自然同步更新。del self.cache[removed.key] 则是把哈希表里对应的引用关系删掉。这个版本我实测能覆盖所有场景包括容量为 1 的边界情况和 C 版逻辑完全等价。4.3 为什么把操作拆成四个辅助方法这道题的代码核心其实是四个辅助动作removeNode、addToHead、moveToHead以及直接取 tail-prev 作为淘汰节点。把它们拆成独立方法get 和 put 的逻辑就会非常扁平面试时也容易边说边写。很多新手喜欢把链表操作内联到 get/put 里结果代码越写越长指针关系越理越乱。特别强调 moveToHead它是 removeNode 和 addToHead 的组合。不要试图在 get 里手动“先记住位置再插头”越绕越容易错。先摘除再插入是标准的 O(1) 移动方式也是双向链表相对单向链表最直观的优势。写代码时只要保证这四个辅助方法各自正确业务方法就是你抄答案一样简单。5. 实战中容易踩的坑和面试追问实录5.1 高频 Bug 清单我自己踩过的坑第一个坑是哈希表与链表不同步。最常见的是 put 新节点时只 addToHead 却忘了 mp[key] newNode或者淘汰尾部节点时只 removeNode 却忘了 mp.erase。一旦不同步下次 get 就会命中一个已经不在链表里的孤儿节点导致逻辑错乱。这个 bug 特别隐蔽因为小数据量测试往往跑不出来容量稍微大一点、操作稍微复杂一点才暴露。第二个坑是 C 内存泄漏。前面说过new 出来的节点在 removeNode 之后如果不 delete反复 put 会持续泄漏。正确的淘汰顺序是“先摘链表、再删哈希表、再释放内存”顺序反了容易访问已释放的内存直接 UB。第三个坑是操作顺序混乱。容量满时有人先 delete 再 removeNode或者先 mp.erase 再 removeNode这些都会出问题。delete 之后节点内存已经释放再去访问它的 prev/next 就是读野指针。所以顺序必须固定先摘出链表再从哈希表移除映射最后释放内存。Python 虽然没有手动释放的烦恼但 del 的顺序同样建议先链表后 dict逻辑上更清晰。第四个坑是容量为 1 的边界情况。此时链表中只有一个真实节点它的 prev 是 dummyHeadnext 是 dummyTail。任何操作都要保证 dummyHead 和 dummyTail 永远不会被当作真实节点处理。用哑节点可以天然规避这类问题但如果有人用朴素链表手写这个边界特别容易崩。写完代码后我建议第一件事就是用容量 1 和容量 2 各跑一遍手动模拟几次 get、put、淘汰很多问题当场就能暴露。5.2 面试官常问的后续追问“为什么不用 map 而用 unordered_map” map 底层是红黑树查找 O(log n)unordered_map 是哈希表平均 O(1)。题目硬性要求 O(1)所以只能选哈希表家族。“Python 的 dict 本身有序为什么还要链表” dict 维护的是插入顺序不是访问顺序。LRU 要求每次 get 都把 key 挪到最新位置单靠 dict 没办法在 O(1) 内调整已有键的顺序。链表存在的意义就是精确记录和调整访问顺序。“用 STL 的 list 实现的话怎么写” 思路一样unordered_mapint, listpairint, int::iteratorlist 用 splice 操作把迭代器对应的节点移到头部。这并没有改变“哈希表的值是节点句柄”的核心只是换了一套封装。“改成 LFU最不经常使用怎么做” LFU 需要“频率桶 每个频率桶内维护一个 LRU 链表”的结构比 LRU 复杂不少但哈希表 链表的组合思想依然贯穿其中。能答到这一层面试官一般就比较满意了。5.3 这道题背后的通用设计思想“哈希表 链表”的组合本质是空间换时间在 O(1) 查找的基础上用链表补上“顺序维护”能力。这种设计在真实工程里被反复复用——数据库的 LRU 缓冲池、操作系统页表管理、消息队列里的索引结构底层都能看到这个影子。以后你遇到“既要快速查找、又要维护顺序”的需求第一反应就应该是这个组合。另外强调一个容易忽略的细节链表节点里必须存 key。很多人写节点只存 value缓存淘汰时就傻了——从 tail-prev 拿到尾节点却不知道它在哈希表里对应哪个 key没法完成回删。这个细节再一次说明节点不只是数据载体它同时是哈希表与链表之间的桥梁key、value、prev、next 四者缺一不可。我在实际刷这道题的时候第一版也是 unordered_mapint, int 配一个队列结果改来改去把自己绕晕了。后来静下心来把“为什么要存节点”“为什么要双向链表”这两个问题彻底想明白了代码几乎一遍写过。所以如果你现在也卡在这道题上我的建议是别急着看题解先试着自己回答这两个“为什么”答不上来再回头看。理解之后再写代码你甚至会觉得这道题简单到配不上“热题100”的称号。最后再分享一个小技巧刷题时不要只盯着代码能否通过花点时间手动模拟一次完整流程。比如容量 2依次 put(1,1)、put(2,2)、get(1)、put(3,3)把每一步链表中节点的前后关系、哈希表里的映射都画出来。你能把这张流程图画明白LRU 的思路就真正刻进脑子里了后面不管面试官怎么变着花样追问你都能稳得住。