Salesforce LRU Cache：哈希表与双向链表保证 get/put O(1)

题意与假设

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

• 训练版接口为 LRUCache(capacity)、get(key)、put(key,value)；get 不存在返回 None，put 更新或插入并返回 None。容量按条数，0 容量永不存值。
• 最近使用由成功 get 和 put 决定；更新已有键也变成最新。缓存仅在单线程中使用，哈希表操作按均摊 O(1) 讨论。
• 键可哈希；若业务允许缓存值本身为 None，调用方无法用 get 返回值区分命中与未命中，需增加 contains 或哨兵结果。

解题路线

1. 字典 key→Node 提供 O(1) 均摊定位；双向链表按从最久到最新排列节点，头尾哨兵让空链、首尾摘除和追加都使用统一指针操作。
2. get 命中时把节点从原位置摘下并接到尾哨兵前，返回值；未命中不改顺序。put 已存在时更新值并移动到尾；新键在满容量时删除头哨兵之后的最久节点，再新建并追加。
3. 不变量：字典中每个键恰好对应链表中的一个数据节点，链表顺序等于这些键最近一次成功访问的顺序。摘除时同时修前后相邻指针，淘汰时还须从字典删除；若任一路遗漏就会出现幽灵节点。

手动走一遍

capacity=2：put(A,1)、put(B,2) 后顺序 A→B；get(A) 后 B→A；put(C,3) 淘汰 B，剩 A→C；get(B) 返回 None。put(A,4) 更新 A 并移至最新，顺序 C→A。capacity=0 时 put 无作用。

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)；空间 O(capacity)。Python 哈希表不保证恶意碰撞下严格最坏 O(1)，文章不把均摊说成数学最坏上界。若多线程并发，整体状态转换需要锁或更复杂同步，题目未要求。

易错点与追问

容易失分的边界

• 只用数组保存访问顺序，get 或更新中间项需要 O(n) 删除。
• 链表用单向 next 指针，已知节点时仍难以 O(1) 摘除，因为没有前驱。
• 淘汰链头却忘记删字典键，后续 get 返回已淘汰值。
• 容量 0 时仍插入并试图淘汰哨兵节点。
• 把 LRU 和 LFU 混同；后者按访问频次淘汰，频次相同才可能用 LRU 决胜。

继续深挖

• 如果每个 value 大小不同、容量按字节算，一次 put 可能淘汰多个节点；复杂度与大对象策略如何变化？
• 如果附加 TTL，过期检查与 LRU 淘汰顺序如何定义？是否需要后台清理？
• 在并发访问下如何把字典查找、摘链和追加作为一个原子操作，避免链表损坏？