图 1：本文封面，点明题目与核心技术组合。
先说明属性：这是一篇经典题解析，题目出自本地历史面试与笔试资料（见文末来源说明），与任何公司的当前招聘无关。缓存淘汰是后端面试的常驻考点，而 LRU 是其中被考得最多的一个。
想象面试现场，面试官写下要求：设计一个缓存，容量固定，支持 get 和 put；容量满了要淘汰「最久未被使用」的条目；两个操作都要尽量快。
第一步，审题。
题目里有三个硬约束。一是容量有限，必然涉及淘汰；二是淘汰规则明确——最久未使用（Least Recently Used）；三是「尽量快」，隐含目标是 O(1)。第三点才是真正的考题：策略本身一句话就能说清，难的是用什么数据结构把它做到常数时间。
第二步，基础回答：为什么是哈希表加双向链表。
逐个排除常见方案。只用一个哈希表：查找 O(1)，但不知道谁最久没用，淘汰时要全表扫描，O(n)。只用一个数组或队列维护使用顺序：淘汰时取队尾是 O(1)，但 get 命中后要把这个元素挪到队首，数组里移动是 O(n)。单链表能 O(1) 把头节点摘下来，但删除中间节点需要前驱指针，单链表拿不到前驱。
组合起来就顺了：哈希表负责「按 key 直接定位到节点」，O(1)；双向链表负责「维护新旧顺序」，节点带 prev 和 next 两个指针，删除和移动到头部都是改几根指针的事，O(1)。两个结构各管一件事，合起来两个操作都是常数时间。
图 2：LRU 的数据结构组合——哈希表定位，双向链表排序，头部最新、尾部最旧。
第三步，把两个操作说清楚。
get(key)：查哈希表，没有就返回未命中；有就把对应节点从链表当前位置摘下、插到头部，返回 value。摘和插都是 O(1)。
put(key, value)：key 已存在则更新值并移到头部；不存在则新建节点插到头部，同时检查容量——超了就删掉尾节点（链表尾部即最久未用），并把它的 key 从哈希表移除。写代码时给链表加头尾两个哨兵节点，可以消掉大量空指针判断，这是面试加分的工程细节。
一个值得动手验证的细节：get 虽然只是「读」，但它会把命中节点挪到头部，从数据结构角度看它同样修改了链表——所以在并发讨论里不能把它当纯读操作对待，读锁之类的乐观方案在这里并不够用。
第四步，可能的追问。
「除了 LRU 还知道哪些淘汰策略？」缓存淘汰是一个家族：理论最优但不可实现的 OPT（淘汰未来最久不用的，常作对照基准）、先进先出的 FIFO、按访问频率淘汰的 LFU、以及用时钟指针近似 LRU 的 Clock 算法。能横向对比，说明你不是背题。「并发环境下怎么办？」标准答案要加锁或改用分片锁，竞争激烈的场景会换用近似的分段 LRU。「为什么不用语言内置的有序字典？」可以用，但面试官想看的恰恰是你能不能从指针层面自己搭出来。
第五步，工程应用与 AI 关联。
LRU 不是题库游戏：操作系统的页面置换、HTTP 缓存、数据库缓冲池都是它的变体。对 AI 工程岗位，关联更直接——推理服务大量依赖缓存：embedding 结果缓存、会话上下文缓存、推理结果缓存，淘汰策略直接决定命中率和延迟；而 LLM 推理的 KV Cache 同样有容量上限，什么时候留、什么时候丢，正是 LRU 教给我们的那套取舍直觉。
易错点清单。
一，get 命中后忘记把节点移到头部，淘汰顺序就错了。二，更新已存在的 key 时只改值、不调整位置。三，淘汰尾节点后忘了从哈希表里删 key，造成脏数据。四，不用哨兵节点，在空表、单节点等边界上写出空指针。五，容量为 0 或负数的非法输入没有校验。完整可运行的参考实现见同主题 B 站专栏版。
回到面试现场，建议的答题节奏：先复述约束确认 O(1) 目标，再讲选型排除过程，然后写出带哨兵节点的核心操作，最后主动聊并发与淘汰策略家族。思路、编码、工程意识，三层都覆盖到了。
如果面试官追问「要支持按过期时间淘汰（TTL），LRU 结构要怎么改」，你会加什么数据结构？欢迎写出你的方案。
参考资料
- Node.js v22.x 官方 API 文档（运行环境说明） — https://nodejs.org/docs/latest-v22.x/api/