题目重点：按容量计条目的训练契约实现 get/put，覆盖更新、命中、淘汰与指针不变量。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版容量按条目数、必须为正；`get(key)` 未命中返回 None，命中刷新最近使用时间；`put` 新增或覆盖，覆盖也刷新；键可哈希。
- LRU 标准语义只描述近期使用淘汰；若原题按字节限额、TTL、并发、持久化或 `-1` 未命中，就需改契约。
解题路线
- 哈希表 key→双向链表节点，链表 head 后是最近使用、tail 前是最久未使用；两个哨兵避免头尾特判。
- get 命中时 O(1) 把节点从原位置摘下再插到 head 后；未命中不改变顺序。put 命中更新值并同样刷新；新增后若超容量就删除 tail 前节点及哈希表项。
- 不变量：每个表项恰好对应链表中的一个真实节点，正反链接一致，链表从新到旧。任何操作都必须同时维护表和链。
- 用 OrderedDict 的独立参考模型对照 27,993 条 get/put 操作序列，逐步检查返回值、顺序和键集合。
手动走一遍
容量 2：put(A,1)、put(B,2) 后 B 最新；get(A) 后 A 最新；put(C,3) 淘汰 B。若再次 put(A,9)，A 仍最新且总条目数不增加。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
class Node:
def __init__(self, key=None, value=None):
self.key, self.value = key, value
self.prev = self.next = None
class LRUCache:
"""Capacity in entries; get miss returns None; head is most recent."""
def __init__(self, capacity: int):
if capacity < 1:
raise ValueError("capacity must be positive")
self.capacity = capacity
self.nodes = {}
self.head, self.tail = Node(), Node()
self.head.next, self.tail.prev = self.tail, self.head
def _unlink(self, node: Node) -> None:
node.prev.next = node.next
node.next.prev = node.prev
def _front(self, node: Node) -> None:
node.next, node.prev = self.head.next, self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
node = self.nodes.get(key)
if node is None:
return None
self._unlink(node)
self._front(node)
return node.value
def put(self, key, value) -> None:
node = self.nodes.get(key)
if node is not None:
node.value = value
self._unlink(node)
self._front(node)
return
node = Node(key, value)
self.nodes[key] = node
self._front(node)
if len(self.nodes) > self.capacity:
victim = self.tail.prev
self._unlink(victim)
del self.nodes[victim.key]
复杂度
哈希表平均 O(1) 查找，双向链表 O(1) 摘插，因此 get/put 平均 O(1)，空间 O(capacity)；极端哈希冲突不承诺严格最坏 O(1)。
易错点与追问
容易失分的边界
- 只用数组或普通链表，命中后找节点 O(n)。
- 更新已有 key 时错误增加容量或不刷新最近使用顺序。
- 淘汰链表节点却忘记删除哈希表项。
- 把 head/tail 哨兵当真实条目。
- 默认线程安全；多线程 get 也会写链表，需锁或分片设计。
继续深挖
- 若容量按字节计，更新值大小时怎样连续淘汰？
- TTL 与 LRU 混用时过期条目怎样清理？
- 多线程读写如何避免指针损坏？
- LFU 与 LRU 的缓存命中行为在哪些流量下不同？
