LRU缓存必须用双向链表+哈希表，因单纯dict无法O(1)删除最久未使用项；双向链表支持O(1)节点移动，哈希表提供O(1)查找，二者协同实现get/put的常数时间复杂度。
LRU 缓存为什么必须用双向链表 + 哈希表
单纯用 dict 无法在 O(1) 时间内删除最久未使用的项，因为 python 字典不保证访问顺序（3.7+ 虽然有序，但“最近访问”和“插入顺序”不是一回事）。LRU 的核心操作——把某 key 移到“最近使用”位置、删掉“最久未使用”节点——需要常数时间定位 + 删除 + 插入。双向链表支持 O(1) 拆入节点，哈希表提供 O(1) 查找节点指针。
常见错误是只用 OrderedDict 的 move_to_end()，它确实能模拟 LRU，但底层仍是链表操作，且每次访问都触发重排；而手写结构可避免冗余移动（比如只在 get 时更新，put 冲突时才删尾）。
Python 标准库 functools.lru_cache 怎么做缓存淘汰
它不公开内部链表，但行为等价：调用函数时命中缓存 → 把对应 entry 移至链表头；新 entry 插入头；容量超限时删链表尾。关键点在于它用弱引用（weakref）管理参数哈希键，避免因缓存导致对象无法回收。
实操注意：
立即学习“Python免费学习笔记（深入）”；
-
lru_cache(maxsize=128)中maxsize=None表示无限制，但实际仍受内存约束 - 被装饰函数的参数必须可哈希（否则抛
TypeError: unhashable type），比如不能传list或dict - 线程安全：内部用
RLock，多线程下调用不会崩，但高并发下锁争用会影响吞吐
手动实现 LRU 时最容易漏掉的边界条件
自己写 LRUCache 类时，90% 的 bug 出在节点操作的对称性上：插入新节点要同时更新哈希表和链表；删除节点要从两者中都清除；更新访问顺序时不能只改链表而忘了哈希表里存的还是旧节点指针。
典型坑：
- 初始化时没设好虚拟头尾节点（
self.head/self.tail），导致get空缓存时next为None报AttributeError -
put时 key 已存在，只更新 value 却忘了把节点移到头部 - 容量为 0 时，任何
put都应直接丢弃，不进缓存也不触发淘汰
一个最小可用骨架的关键逻辑是：self.cache[key] = new_node 必须紧挨着 self._add_to_head(new_node)，顺序反了就会缓存错位。
lru_cache 的性能开销主要在哪
不是哈希计算，也不是链表操作，而是函数调用前后的封装层：每次调用都要走 descriptor 协议、检查参数 hash、查表、计数器更新、可能的锁获取。实测显示，空函数加 @lru_cache() 后调用耗时增加 3–5 倍（纳秒级变几十纳秒）。
所以别给单次运行就结束的函数加缓存；更别给参数总在变的函数加（比如含 time.time() 或随机数）；如果函数本身耗时远低于 100ns，缓存反而拖慢整体。
真正值得缓存的是：纯函数、参数组合有限、执行成本显著高于哈希与查表（如 IO、复杂计算、数据库查询封装）。