Python LRU 缓存的实现原理_网络技术_宿州市腾雀网络科技有限公司

Python LRU 缓存的实现原理

发布时间 - 2026-01-29 00:00:00 点击率：次

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）管理参数哈希键，避免因缓存导致对象无法回收。

实操注意：

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 都应直接丢弃，不进缓存也不触发淘汰