手写 LRU 缓存踩坑记淘汰端写错被断言当场抓出LRU 缓存是面试手写题之王LeetCode 146。本文给出哈希表双向链表的工业实现以及一个真实开发过程踩的坑——淘汰端写错被断言当场抓出。一、结构设计哈希表负责 O(1) 查找双向链表维护使用顺序。方向约定是整个实现的灵魂front 最近使用tail 最久未用淘汰端。Node 里额外存 key淘汰时 O(1) 反查删除无反向扫描。二、我踩的坑真实开发过程淘汰时写成了oldest list.head.next——那是最近使用端容量 3 的访问序列断言当场爆出期望[True, False, True]b 被淘汰后未命中实际[True, True, True]b 还活着说明淘汰错了人。一行修正tail.prev全部通过。教训方向约定是 LRU 第一易错点先写断言再写实现。三、基准为什么非链表不可操作链表Python list头插 20 万次29.3ms4313.7ms147 倍差头删 10 万次14.2ms7662.6ms538 倍差list 底层是数组头部操作要整体搬移 O(n)——这就是链表存在的意义。四、LRU 压测命中序列断言通过后10 万键 put 抽查一致性、5 万次带淘汰 put 仅20ms——O(1) 设计在真数据量下的表现。完整实现单链表反转/哨兵双链表/LRU 工业版约 230 行与 results.txt 见下方资源包。
