如何实现一个 LRU 缓存？

直接回答

LRU 缓存淘汰最久未使用的项。经典实现是哈希表 + 双向链表：哈希表提供 O(1) 查找，双向链表维护使用顺序（头部最新、尾部最旧），节点移动和删除也是 O(1)。get 时把节点移到头部，put 时插入头部、超容量则删除尾部节点。

展开解析

为什么必须是双向链表：删除任意节点需要前驱指针，单链表删尾是 O(n)。工程技巧：用哑头/哑尾哨兵节点统一边界判断，避免空指针分支。put 要分两种情况：key 已存在则更新值并提至头部；不存在则新建节点，若超容量先 evict 尾节点并同步删哈希表项。易错点：链表操作和哈希表更新不同步（淘汰后忘了删 map）、get 命中忘记刷新位置、容量为 0 的边界。追问方向：并发 LRU（分段锁）、带 TTL 的过期淘汰、LFU 如何扩展（频次分桶+桶内链表）、Redis 的近似 LRU（采样淘汰而非精确链表）。

示例

class LRUCache:
    def __init__(self, cap):
        self.cap, self.map = cap, {}
        self.head, self.tail = Node(), Node()  # 哨兵
        self.head.nxt, self.tail.pre = self.tail, self.head

get/put 围绕"摘节点 + 插到头"两个 O(1) 操作展开。