LRU 缓存题解哈希表找得到链表排得动一、LRU 的难点是两个操作都要 O(1)LRU 缓存要求 get 和 put 都是 O(1)。只用哈希表能快速找到元素但不知道谁最久没用只用链表能维护顺序但查找慢。正确结构是哈希表加双向链表。哈希表负责找链表负责排。很多题解会直接背这个组合但没有说明为什么是双向链表。因为命中一个节点后要把它移动到头部。删除一个已知节点时需要同时改前后指针单链表做不到 O(1)。二、链表头表示最新尾表示最旧每次 get 命中把节点移到头部put 新节点也放头部容量超了删除尾部节点。flowchart LR A[head] -- B[最新节点] B -- C[中间节点] C -- D[最旧节点] D -- E[tail]通常使用虚拟 head 和 tail能减少空链表和单节点边界判断。三、核心操作只有 remove 和 addFirst下面是简化 Python 结构。class Node: def __init__(self, key0, val0): self.key key self.val val self.prev None self.next None def remove(node): node.prev.next node.next node.next.prev node.prev def add_first(head, node): node.next head.next node.prev head head.next.prev node head.next nodeLRU 的代码看起来长其实核心就是这两个链表操作。写稳它们后面逻辑就清楚。四、put 更新已有 key 时别忘了移动如果 put 的 key 已存在更新值后也要移动到头部。因为这次 put 也是一次访问。很多 bug 就出在这里。删除尾节点时要同时从哈希表删除 key。链表删了map 还留着下一次 get 会拿到悬空节点。复杂度证明也很直接map 查询 O(1)链表删除和头插都是 O(1)所以 get 和 put 都是 O(1)。前提是哈希表均摊 O(1)。实现时还要处理容量为 0 的边界。虽然很多题目约束 capacity 1但工程实现里最好防一下。容量为 0 时put 应直接返回不要尝试删除 tail.prev 把哨兵节点删掉。如果扩展到多线程LRU 就不是这份代码能解决的了。map 和链表更新必须加锁或者使用分段缓存。算法题只讨论单线程工程里要把并发边界写清楚。最后LRU 不是所有缓存场景的答案。热点扫描会把真正高频数据挤出去时可能需要 LFU 或带保护窗口的策略。题解可以讲 LRU但别把它神化。调试 LRU 时可以在每次操作后打印链表顺序和 map keys。很多错误来自链表和 map 不一致。比如节点移动到头部后旧位置没有断开就会形成环。链表题别靠脑补画状态最稳。还要注意返回值语义。get 不存在时返回 -1这是题目约定工程里可能要返回错误或 optional。算法题代码不要直接搬到业务缓存里接口语义不同。最后put 新 key 超容量时先插入再删除尾还是先删除再插入都可以但要保证删除的不是新节点。使用虚拟头尾后这个逻辑会清楚很多。五、总结LRU 缓存用哈希表加双向链表解决两个问题快速定位和快速调整顺序。虚拟头尾能减少边界判断核心操作是 remove 和 addFirst。题解不要只背结构要讲清为什么单独一种数据结构不够。
)
