01先把问题说具体
容量只有两个条目的缓存,读到旧条目时也算最近使用,如何快速找到并更新它的位置?
02一步步得到方法
先定义最近使用的事件
LRU 淘汰最久没有被访问的条目。get 命中会刷新它的最近性,put 已存在的键也会刷新;get 未命中不应插入条目。容量满时插入新键,要移除当前最旧项。
这和 FIFO 不同:FIFO 只看进入时间,命中不会改变队列位置。明确这些事件,比只背“哈希表加链表”更重要。
为什么需要两种数据结构
哈希表 key→节点负责平均 O(1) 定位;双向链表按旧到新排列,负责 O(1) 删除任意已知节点并追加到尾部。移除节点 x 时连接 x.prev.next=x.next、x.next.prev=x.prev,再把 x 插到尾部。
只有链表时按 key 查找要 O(n),只有普通无序哈希表时不能直接找到最旧项。头尾哨兵可以统一空链表、首尾删除等边界,避免大量条件分支。
参考实现与工程边界
Python OrderedDict 提供保序哈希容器、移动条目和弹出最旧项,适合直接表达上述接口。下面给出完整缓存行为,底层链表思想通过文字和操作顺序说明,不把容器内部实现细节当作 Python 语言承诺。
缓存性能取决于访问局部性。扫描大量一次性数据可能冲掉热门条目;并发访问还需同步,过期时间、字节容量与持久化都属于需要另外设计的策略。
03把一个小例子完全算清楚
容量2,执行 put(A,1)、put(B,2)、get(A)、put(C,3)。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 插入 A、B | 旧→新:[A,B] | B 最近写入 |
| 读取 A | 旧→新:[B,A] | 命中也刷新最近性 |
| 插入 C | 淘汰 B,变为 [A,C] | 容量超过2,移除最旧项 |
窄屏可左右滑动表格,阅读完整计算与理由。
最终保留 A、C;若使用 FIFO,同样序列会淘汰 A。
04为什么这个方法成立
- 始终保持容器顺序等于条目最后一次命中或写入的时间顺序。
- 命中和写入后移动到尾部,正好更新该条目的最近性,其他条目的相对顺序不变。
- 超容量时弹出最前条目,因此淘汰的就是当前最久未使用项。
05把推导翻译成代码
Python · 可独立运行的教学实现
from collections import OrderedDict
class LRU:
def __init__(self,capacity):
if capacity<1:
raise ValueError("positive capacity required")
self.capacity = capacity
self.data = OrderedDict()
def get(self,key,default=None):
if key not in self.data:
return default
self.data.move_to_end(key)
return self.data[key]
def put(self,key,value):
self.data[key] = value
self.data.move_to_end(key)
if len(self.data)>self.capacity:
self.data.popitem(last=False)
cache = LRU(2)
cache.put("A",1)
cache.put("B",2)
cache.get("A")
cache.put("C",3)
print(list(cache.data.items()))逐个理解关键决定
move_to_end(key)- 读命中与写入都移动到最新端。
popitem(last=False)- 删除顺序最前、也就是最旧的条目。
default=None- 未命中返回默认值;若缓存允许存 None,可由调用者传独特哨兵区分。
06时间、空间与实现范围
哈希操作平均 O(1),移动和删除顺序节点 O(1),单次访问通常平均 O(1),空间 O(capacity)。
哈希最坏情况和并发控制成本不能从平均 O(1) 中自动排除。
07改变条件,检查哪里会出错
读取不移动节点
这样就不再是这里定义的 LRU,淘汰顺序会错。
写已有键也增加条目数
更新应覆盖并移动,不能创建同一个 key 的第二个节点。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
容量1,put(A)、put(B) 后留下谁?
需要一点提示
新插入使 A 成为最旧。
查看解析与答案
只留下 B。
为什么单向链表不方便 O(1) 删除任意节点?
需要一点提示
修改前驱的 next 需要先找到前驱。
查看解析与答案
若只持有当前节点,通常还需定位前驱;双向链表直接保存它。
纯顺序扫描为何可能让 LRU 效果差?
需要一点提示
每个新条目都被判成最近使用。
查看解析与答案
一次性条目不断挤掉之后仍可能被访问的旧热门数据,局部性假设不成立。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
Arpaci-Dusseau · Operating Systems: Three Easy Pieces