题干与适用场景
实现 LRUCache(capacity)，其中 capacity 是正整数，键和值都是非负整数。get(key) 返回对应值，键不存在时返回 -1；put(key, value) 插入或更新键。成功的 get 和每次 put 都要把该键标记为最近使用。缓存已满时插入新键，只淘汰一个最近最少使用的键。两个公开操作都要达到期望 O(1)。
本题是在单进程、单线程内完成的数据结构编码；分布式缓存设计、TTL、持久化、按大小计费和并发访问都不在范围内。“期望 O(1)”依赖哈希表操作的常见平均性能假设；链表指针修改本身是最坏 O(1)。
完整答案要从约束推导两种结构为什么缺一不可，明确映射与链表的不变量，处理已有键更新时不能误淘汰，并在每次操作后验证使用顺序。
面试官考察点
第一项信号是能否把需求翻译成操作。按键查找不能扫描，所以需要哈希表；最近使用顺序又要求把任意命中节点移动到最近端，并从另一端删除最旧节点。只要哈希表已经给出节点，双向链表就能用固定次数的指针修改完成这两件事。
第二项信号是能否把两个结构视为一份状态。哈希表不能只保存值，而要把每个键映射到链表节点。每个真实链表节点必须恰好有一个映射项，每个映射项也必须指向链表中的一个真实节点。淘汰时要从两个结构中删除同一个键。
第三项信号是指针操作是否稳定。哨兵头尾节点让所有真实节点都处于链表中间，删除和插入不再为首节点、尾节点或唯一节点写分支。编码前应先约定哪一侧代表最近使用，并保持到底。
最后看测试能否验证完整顺序。仅检查返回值会遗漏链表状态错误；容量为 1、满容量时更新已有键、反复读取一个键、miss 后再插入等用例，能暴露单个正常样例发现不了的问题。
回答前需要澄清的问题
get会更新最近使用顺序吗？ 本题会。若另有只读peek，它才不移动节点。- 更新已有键会占用新容量吗？ 不会。
put只修改同一个条目的值和顺序，不能淘汰其他键。 - miss 返回什么？ 本题的值是非负整数，
-1专门表示未命中；若值域也包含-1，接口应改为返回可选值。 - 容量 0 是否合法？ 本实现拒绝非正容量。若允许 0，每次插入都要立即消失，构造器契约也会改变。
- 要求严格最坏
O(1)吗？ 普通哈希表通常提供期望常数时间。若要求严格最坏界，需要不同的查找结构或更强假设。 - 能否使用标准有序映射？ 生产代码或短题中可能允许，但面试官仍可要求手写底层链表并说明不变量。
- 需要线程安全吗？ 本题不需要。若增加该要求，要记住
get会修改顺序，因此同步语义上也是写操作。
30 秒回答框架
“我需要期望常数时间的查找和顺序更新，所以用哈希表把键映射到双向链表节点。靠近头的是最近使用，靠近尾的是最近最少使用；头尾哨兵让摘除与插入保持统一。命中或更新就把节点移到头部；新插入导致超容时，从链表和哈希表同时删除 tail.prev。映射与链表始终包含同一组真实节点，因此 get、put 都是期望 O(1)，空间是 O(capacity)。”
分步骤深入解答
只用链表可以保存顺序，但查找键和删除任意条目要 O(n)。只用哈希表可以快速找到值，却不能直接知道谁最久没用。数组加哈希表仍会在移动元素或寻找前驱时付出 O(n)。题目的两个约束共同要求一份查找索引和一份可快速修改的顺序。
全文采用这个方向：
head <-> 最近使用 <-> ... <-> 最近最少使用 <-> tail两个哨兵永远不进入哈希表，也不计入容量。每个真实节点保存 key、value、prev 和 next。节点必须保存键，因为淘汰从 tail.prev 开始，需要直接删除对应映射，不能再反向扫描哈希表。
四条不变量让实现可以逐行检查：
- 缓存非空时，
head.next是最近使用节点，tail.prev是最近最少使用节点。 - 哈希表中的键与链表中的真实节点一一对应，描述的是同一组条目。
- 任意相邻节点都满足
left.next is right且right.prev is left。 - 每个公开操作结束后，都有
0 <= len(nodes) <= capacity。
get 和 put 确实会复用相同的指针操作，因此把摘除与头插放在两个私有方法中：
class Node:
__slots__ = ("key", "value", "prev", "next")
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
if capacity <= 0:
raise ValueError("capacity must be positive")
self.capacity = capacity
self.nodes = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def _detach(self, node: Node) -> None:
node.prev.next = node.next
node.next.prev = node.prev
def _attach_after_head(self, node: Node) -> None:
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _mark_recent(self, node: Node) -> None:
self._detach(node)
self._attach_after_head(node)
def get(self, key: int) -> int:
node = self.nodes.get(key)
if node is None:
return -1
self._mark_recent(node)
return node.value
def put(self, key: int, value: int) -> None:
node = self.nodes.get(key)
if node is not None:
node.value = value
self._mark_recent(node)
return
node = Node(key, value)
self.nodes[key] = node
self._attach_after_head(node)
if len(self.nodes) > self.capacity:
victim = self.tail.prev
self._detach(victim)
del self.nodes[victim.key]attachafter_head 中的赋值顺序有意义。新节点先记住原首节点，再让原首节点反向指向新节点，最后才覆盖 head.next。若过早改掉 head.next，可能丢失仍需修改 prev 的邻居引用。
正确性可以对操作序列做归纳。初始化满足四条不变量；miss 不改变状态；命中或更新只摘除一个已映射节点，再把同一节点插到头部，成员集合和大小都不变。插入新键时先同时加入两个结构；若大小变成 capacity + 1，再从链表和映射中删除 tail.prev，一一对应关系与容量上限随即恢复。容量为正保证被淘汰的是一个真实节点。
容量为 2 时，依次执行 put(1,10)、put(2,20)、get(1)、put(3,30)、put(1,15)，最近到最旧的顺序依次为 [1]、[2,1]、[1,2]、[3,1]、[1,3]。键 2 被淘汰，更新键 1 只改值和顺序，不会淘汰键 3。
在哈希表平均性能假设下，每个公开方法只做一次查找、固定次数的指针修改和映射操作，所以期望时间为 O(1)。哈希表与链表最多保存 capacity 个真实节点，空间为 O(capacity)。这不等于哈希表在任何输入下都有严格最坏常数时间。
验证要把示例轨迹和不变量检查结合起来：空缓存 miss、容量 0 被拒绝、容量 1、不同键使用相同值、满容量更新已有键、重复命中、交替淘汰和长随机操作流。随机测试可以用简单的 O(n) 参考模型比较返回值与顺序，并在每次操作后断言双向指针对称、节点不重复、映射与链表集合相同、大小不超容。
若允许使用库，访问顺序映射可以更短地表达同一策略。例如 Java 的 LinkedHashMap 支持按访问排序和淘汰最旧条目的钩子，适合生产代码，但不能代替面试中的不变量证明。还要区分面试里的精确单进程 LRU 与生产缓存淘汰：大型服务可能用抽样近似 LRU，减少全局顺序元数据和竞争。
高质量示范回答
“我先明确契约：容量必须为正，miss 返回 -1，每次命中和 put 都更新最近使用顺序；更新已有键不增加大小。目标是基于哈希表平均查找的期望 O(1)。
哈希表解决按键定位，却没有淘汰顺序。双向链表保存顺序，而且只要已经拿到节点，就能以固定指针操作把它摘下。我会把哈希表写成 key -> node，链表从头哨兵后的最近使用节点排到尾哨兵前的最近最少使用节点。节点保存键，尾部淘汰时才能同步删映射。
核心不变量是哈希表与真实链表节点始终为同一集合。命中时摘下节点并头插；更新时改值后做同样移动；新键先加入两个结构，若超过容量，再从两个结构中删除 tail.prev。哨兵让首个、末尾和唯一节点都走同一套指针逻辑。
我会重点测容量 1、满容量更新、重复 get 改变淘汰对象，以及 miss 不改变顺序；再用慢速参考模型对照随机操作，并逐次遍历链表检查不变量。最终每个操作期望 O(1)，空间是 O(capacity)。”
常见错误
- 哈希表只保存值 → 命中后仍要在线性结构中找节点 → 让每个键直接指向链表节点。
- 使用单向链表 → 哈希表给出了节点，却没有前驱，删除任意节点仍可能扫描 → 同时保存
prev与next。 - 节点不保存键 → 尾部淘汰时无法直接删除映射 → 节点同时保存键和值。
- 把插入顺序当作最近使用顺序 → 成功的
get没有改变下一次淘汰对象 → 每次命中都移动到最近端。 - 更新已有键时也执行淘汰 → 大小没有增长，却误删了无关条目 → 先处理更新并返回，再进入新键超容判断。
- 只从一个结构删除淘汰项 → 产生过期映射或链表幽灵节点 → 对称更新两个结构，并测试集合相等。
- 为头、尾和单节点分别写分支 → 指针路径过多，边界行为容易漂移 → 使用两个永久哨兵。
- 声称严格
O(1)→ 哈希表通常只是期望界，碰撞时可能退化 → 明确哈希假设。 - 只检查返回值 → 错误顺序可能要到后续淘汰才暴露 → 同时断言完整顺序和指针不变量。
追问及应对
追问一：怎样改成线程安全？
get 会修改链表，因此也是写操作。最简单的正确扩展是用一把互斥锁包住完整的 get 或 put，确保映射和链表原子更新。普通读写锁不能把命中当作读。分片可以降低竞争，但每个分片会有独立 LRU 顺序；若要保持一个精确全局顺序，就仍需共享的排序协调。
追问二：怎样增加 TTL？
TTL 与最近使用是两种独立淘汰规则。命中前要先判断过期，put 也可能在容量淘汰前清理过期项。使用按过期时间排序的最小堆可以惰性清理，但维护成本变为 O(log n)，还会产生旧堆记录；时间轮又会改变精度与实现。没有重新定义过期机制和边界时，不能继续宣称两个操作都为 O(1)。
追问三：能否保证严格最坏 O(1)？
链表部分已经只有固定次数的指针操作。查找部分取决于哈希表保证。严格最坏常数查找需要更强的字典模型、有限键域上的直接寻址，或专门的哈希假设。普通语言哈希表下，应按其契约表述为期望或摊销 O(1)。
追问四：为什么不用 LinkedHashMap 或 OrderedDict？
当库的访问顺序和淘汰语义符合业务、手写指针没有额外价值时，应使用库。面试中先说明底层映射与链式顺序不变量，再给出库方案。还要核对读取、更新、遍历和最旧项删除是否都算一次访问；名字相近的有序映射不一定有相同语义。
追问五：大型缓存服务会使用精确 LRU 吗？
不一定。维护一个精确的全局访问顺序，会让每次命中都产生元数据写入和竞争点。生产缓存可能按分片维护顺序、抽样候选键，或在访问频率更能预测复用时选择 LFU。这些方案用淘汰精确度换内存与吞吐；面试对象仍有价值，因为它的精确策略与不变量可以完整验证。