Oracle LRU Cache：哈希表与双向链表做到常数时间

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练版 LRUCache(capacity) 支持 get(key) 返回值或 None、put(key,value)；capacity 非负，0 容量不存储。
• 读取与更新已有键都使键成为最近使用；None 也可作为存储值，正式接口可改用命中标记消除歧义。

解题路线

1. 哈希表 key→链表节点让定位期望 O(1)；双向链表从最久未使用到最近使用排列节点，并用哨兵简化首尾操作。
2. get 命中时摘下节点并追加到尾部；put 已有键时更新值并移到尾部。
3. put 新键且容量满时移除头哨兵后的旧节点，再把新节点放尾部；所有节点移动同时更新哈希表。
4. 先手算 get(A)、put(B)、get(A)、put(C) 的淘汰顺序，再验证零容量、重复更新和空键。

手动走一遍

容量 2：put(A,1)、put(B,2) 后顺序 A→B；get(A) 后 B→A；put(C,3) 淘汰 B，顺序 A→C。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

class Node:
    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        if capacity < 0:
            raise ValueError("capacity must be nonnegative")
        self.capacity = capacity
        self.by_key = {}
        self.head, self.tail = Node(), Node()
        self.head.next, self.tail.prev = self.tail, self.head

    def _detach(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = node.next = None

    def _append_recent(self, node: Node) -> None:
        last = self.tail.prev
        last.next = node
        node.prev, node.next = last, self.tail
        self.tail.prev = node

    def get(self, key):
        node = self.by_key.get(key)
        if node is None:
            return None
        self._detach(node)
        self._append_recent(node)
        return node.value

    def put(self, key, value) -> None:
        if self.capacity == 0:
            return
        node = self.by_key.get(key)
        if node is not None:
            node.value = value
            self._detach(node)
            self._append_recent(node)
            return
        if len(self.by_key) == self.capacity:
            oldest = self.head.next
            self._detach(oldest)
            del self.by_key[oldest.key]
        node = Node(key, value)
        self.by_key[key] = node
        self._append_recent(node)

复杂度

get/put 期望 O(1)，容量 C 时哈希表和链表 O(C)；极端哈希碰撞可能降低哈希操作性能。

易错点与追问

容易失分的边界

• 只用列表查找最旧键，get/put 退化 O(C)。
• 淘汰链表节点却忘从哈希表删除。
• 把 LFU 的频次桶当作这篇 LRU 题目要求。
• 返回 None 时无法区分未命中与值为 None；实际 API 应补命中标记。

继续深挖

• 若要求 TTL，过期检查和 LRU 顺序如何配合？
• 多线程下 get 会修改链表，该用什么锁粒度？
• 缓存对象按字节计容量时，淘汰条件如何变化？