专题进阶 · 操作系统算法推荐总顺序 · 第 145 / 148 课

把哈希定位与双向链表排序结合,实现访问更新和最近最少使用淘汰。

先学会这些,再进入本课 哈希表 链表
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 操作系统算法

最近最少使用LRU Cache

哈希表定位、双向链表维护最近使用次序,支持平均 O(1) 访问与淘汰。

建议 50 分钟 · 含手算、代码与三层练习

本课要建立的能力

把哈希定位与双向链表排序结合,实现访问更新和最近最少使用淘汰。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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为什么这个方法成立

  1. 始终保持容器顺序等于条目最后一次命中或写入的时间顺序。
  2. 命中和写入后移动到尾部,正好更新该条目的最近性,其他条目的相对顺序不变。
  3. 超容量时弹出最前条目,因此淘汰的就是当前最久未使用项。

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 · 复现与理解

容量1,put(A)、put(B) 后留下谁?

需要一点提示

新插入使 A 成为最旧。

查看解析与答案

只留下 B。

练习 2 · 边界与辨析

为什么单向链表不方便 O(1) 删除任意节点?

需要一点提示

修改前驱的 next 需要先找到前驱。

查看解析与答案

若只持有当前节点,通常还需定位前驱;双向链表直接保存它。

练习 3 · 变式与迁移

纯顺序扫描为何可能让 LRU 效果差?

需要一点提示

每个新条目都被判成最近使用。

查看解析与答案

一次性条目不断挤掉之后仍可能被访问的旧热门数据,局部性假设不成立。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Arpaci-Dusseau · Operating Systems: Three Easy Pieces

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。