Microsoft LRU Cache：哈希表加双向链表做到 O(1)

题目重点：按读写更新最近使用顺序，容量满时逐出最久未用项；讨论 OrderedDict 的语言差异与 TTL/并发追问。

题意与假设

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

训练 API 为 LRUCache(capacity)、get(key)→(found,value)、put(key,value)；get 命中及 put 更新都刷新最近使用位置。
容量为非负整数；容量 0 时 put 不存储。允许值为 None，返回 found 标记区别 miss。
主实现是单进程、单线程、无 TTL；并发与 TTL 作为独立追问，不将其混入题目 LC146 主规则。

解题路线

哈希表从 key O(1) 预期找到链表节点；双向链表头侧放最近使用，尾侧放最久未用。用头尾哨兵减少空表/单元素分支。
get 命中时把节点摘下再插到头侧；miss 不动顺序。put 已存在键时更新值并刷新位置；新键建节点并插头侧。
超过容量时删除尾哨兵前的节点，并同步从哈希表删除 key。链表和哈希表必须保持一一对应。
若语言自带保持插入顺序的容器，先核它在所用语言中的更新/移动复杂度；不能从‘ordered dictionary’名称推断一定 O(log n) 或 O(1)。
加 TTL 时需定义过期优先于 LRU 的时机，并用到期时间索引或懒清理；多线程则要把查找、摘链、插头和逐出做原子临界区。

手动走一遍

容量 2：put(1,None)、put(2,'b') 后 2 最近；get(1) 返回命中 None 且使 1 最近；put(3,'c') 逐出 2，get(2) miss。若未在 get 命中时移动 1，会错误逐出它。

Python 参考实现

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

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

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


class LRUCache:
    """Most recently used node after head, least recently used before tail."""

    def __init__(self, capacity: int):
        if capacity < 0:
            raise ValueError("negative capacity")
        self.capacity = capacity
        self.nodes: dict[object, Node] = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

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

    def _insert_front(self, node: Node) -> None:
        first = self.head.next
        self.head.next = node
        node.prev = self.head
        node.next = first
        first.prev = node

    def get(self, key: object) -> tuple[bool, object | None]:
        node = self.nodes.get(key)
        if node is None:
            return False, None
        self._unlink(node)
        self._insert_front(node)
        return True, node.value

    def put(self, key: object, value: object) -> None:
        if self.capacity == 0:
            return
        node = self.nodes.get(key)
        if node is not None:
            node.value = value
            self._unlink(node)
            self._insert_front(node)
            return
        node = Node(key, value)
        self.nodes[key] = node
        self._insert_front(node)
        if len(self.nodes) > self.capacity:
            old = self.tail.prev
            self._unlink(old)
            del self.nodes[old.key]


if __name__ == "__main__":
    cache = LRUCache(2)
    cache.put(1, None)
    cache.put(2, "b")
    assert cache.get(1) == (True, None)
    cache.put(3, "c")
    assert cache.get(2) == (False, None)

复杂度

哈希表操作预期 O(1)，链表摘插 O(1)，所以 get/put 预期 O(1) 时间；空间 O(capacity)。哈希碰撞最坏情况与运行时实现有关；逐出不是链表扫描。

易错点与追问

容易失分的边界

只用单向链表，已知任意节点仍不能 O(1) 删除前驱未知的节点。
get 命中不更新最近使用次序。
逐出链表尾节点却忘记删除哈希表条目，造成脏引用。
值 None 与未命中混淆。
把 Python OrderedDict、C++ std::map、Java LinkedHashMap 都笼统称同一个复杂度。
TTL 过期与 LRU 逐出是两个规则，不应未经确认给题目加容量/过期要求。

继续深挖

如果 key 有 TTL，过期瞬间与 LRU 顺序冲突时谁先逐出？
多个线程同时 get/put 同一 key，怎样避免链表破坏？
分布式缓存的全局 LRU 是否可精确维护，代价是什么？
如需按字节容量而非项数限制，逐出循环如何变化？