索引减少定位记录的工作，布隆过滤器尝试提前排除不存在的键。如果某些结果反复被请求，还可以保存已经算过的值，命中时直接返回，这就是本文讨论的缓存。

空间只能放 C 个条目时，满了该淘汰谁？“删掉最早放进去的”与“删掉最久没用过的”是两种不同策略。先把访问顺序画出来，再讨论命中率，才能理解 LRU 的适用条件和失败边界。

先定义状态

左端最久未用，右端最近访问。

再证明命中

数两次访问之间不同键的个数。

最后测边界

扫描、变更与并发不是一条队列就能解决的。

访问A B C A D B时，LRU在再次访问A后将它移到最近端，装入D时淘汰B；FIFO仍在装入D时淘汰A；复用距离按不同键计数
队列顺序由规则决定。 图示与下方手算、程序输出使用同一条合成访问序列；方框是等大小条目，不代表真实字节占用。查看原图

先限定缓存模型

本文使用全相联、从空开始、容量固定为 C 个等大小条目的读缓存。每次请求一个字符串键：命中后更新最近访问顺序；未命中时同步调用加载器，成功才插入，满了淘汰最近最少使用者。没有 TTL、主动失效、写入、预取或并发。

朴素做法用列表保存顺序，每次命中先线性查找并删除旧位置，单次 O(C)。常见结构是“哈希表定位条目＋双向链表维护顺序”，在通常的哈希假设下，把查询、移到端点和淘汰控制在期望 O(1)。最坏哈希冲突、长键哈希及加载器耗时仍需另算。

下面用标准库 OrderedDict 表达该结构：Python 官方文档说明了 move_to_end 与 popitem(last=False) 的重排、端点弹出语义。普通字典保留插入顺序，不意味着读取会自动改变顺序。

每次访问怎样保持不变量

把已缓存条目从左到右排列为“最久未访问 → 最近访问”。命中时把当前键移到最右，其他键相对顺序不变；未命中且加载成功时把新键放到最右，超过容量则从左端弹出。

归纳证明：空缓存满足顺序约定；每次访问只有当前键成为最新，其余键的最后访问时间关系未改变，按上述操作仍按最后访问时间排序。所以左端确实是该模型中最近最少使用的条目。

六次请求的手算

容量 C=3，请求 A、B、C、A、D、B。表中顺序始终为最久未用到最近使用。FIFO 的命中不移动条目，LRU 的命中会移动。

请求 LRU 结果 LRU 淘汰 LRU 顺序 FIFO 结果 FIFO 顺序
A 未命中 无 A 未命中 A
B 未命中 无 A B 未命中 A B
C 未命中 无 A B C 未命中 A B C
A 命中 无 B C A 命中 A B C
D 未命中 B C A D 未命中 B C D
B 未命中 C A D B 命中 B C D

这条序列里 LRU 只有 1 次命中，FIFO 有 2 次。LRU 利用时间局部性，并不保证在每条轨迹上胜过 FIFO，更不等于知道未来的最优淘汰。

复用距离为什么决定命中

对非首次请求，定义复用距离 d 为同一键上次请求之后、本次请求之前出现的不同键个数。重复出现同一个其他键只算一次。首次请求单独标记为冷启动，不把它的距离记成 0。

在本文模型下，上次访问当前键后它在最近端。之后每出现一个不同的其他键，它在完整最近访问栈中的排名向后增加一位；再次访问这些其他键只调整它们之间的位置。因此本次请求前当前键的排名为 d+1，容量 C 保存完整栈的前 C 项，所以：

1
2
命中 ⇔ 不是首次访问，而且 d < C
未命中 ⇔ 首次访问，或者 d ≥ C

A、B、C、A、D、B 的距离为 [冷,冷,冷,2,冷,3]。C=3 时 A 的 2＜3 命中，B 的 3≥3 未命中；C=4 时二者都命中。任意时刻，较小 LRU 缓存都是较大缓存的子集，因此在相同轨迹和这些假设下，增加容量不会增加未命中数。

这个结论不能直接套到设置了 TTL、容量按不同字节权重计费、旁路加载或主动失效的实现。下面的复用距离参考用集合直接数不同键，故意采用易审查的 O(T²) 教学算法，独立核对实际缓存轨迹。

容量异常与扫描污染

FIFO 不具有上述包含关系。对轨迹 [1,2,3,4,1,2,5,1,2,3,4,5]，FIFO 容量 3 未命中 9 次，容量 4 反而 10 次；本文程序会复现这个容量异常。相同轨迹 LRU 分别为 10 和 8 次。这里把数字键转换为字符串，避免与实现的输入规则混用。

LRU 也会被一次性扫描污染。容量 3，先访问 A、B、C，再访问 X1、X2、X3，最后重访 A、B、C，总共 9 次全未命中：扫描条目把热点全部挤走。是否引入准入规则、多队列或频率信息，需要工作负载证据，不是把 LRU 换个名字就能解决。

完整标准库实现

容量零表示每次都加载但不保存。缓存用成员关系检查命中，不用值是否为 None 判断；None 也可以是合法缓存值。加载器抛异常时还未插入或淘汰，原缓存保持不变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
from collections import OrderedDict
import json


def capacity_value(value):
    if type(value) is not int or not 0 <= value <= 100000:
        raise ValueError('capacity must be an integer in [0, 100000]')
    return value


def key_value(key):
    if not isinstance(key, str) or len(key) > 10000:
        raise ValueError('key must be a string of at most 10000 characters')
    return key


class LRU:
    def __init__(self, capacity, loader):
        self.capacity = capacity_value(capacity)
        if not callable(loader):
            raise ValueError('loader must be callable')
        self.loader = loader
        self.data = OrderedDict()

    def request(self, key):
        key_value(key)
        if key in self.data:
            self.data.move_to_end(key)
            return self.data[key], True, None
        value = self.loader(key)
        evicted = None
        if self.capacity:
            self.data[key] = value
            if len(self.data) > self.capacity:
                evicted, _ = self.data.popitem(last=False)
        return value, False, evicted


def trace(keys, capacity, policy='lru'):
    capacity_value(capacity)
    if policy not in ('lru', 'fifo'):
        raise ValueError('policy')
    keys = list(keys)
    for key in keys:
        key_value(key)
    cache = LRU(capacity, lambda key: 'value:' + key)
    rows = []
    for key in keys:
        if policy == 'fifo' and key in cache.data:
            value, hit, evicted = cache.data[key], True, None
        else:
            value, hit, evicted = cache.request(key)
        rows.append({'key': key, 'hit': hit, 'evicted': evicted,
                     'order': list(cache.data), 'value': value})
    return rows


def reuse_distances(keys):
    keys = list(keys)
    for key in keys:
        key_value(key)
    last, distances = {}, []
    for i, key in enumerate(keys):
        distance = None if key not in last else len(set(keys[last[key]+1:i]))
        distances.append(distance)
        last[key] = i
    return distances


def miss_count(keys, capacity, policy='lru'):
    return sum(not row['hit'] for row in trace(keys, capacity, policy))


if __name__ == "__main__":
    hand = list('ABCADB')
    anomaly = list(map(str, [1,2,3,4,1,2,5,1,2,3,4,5]))
    scan = ['A','B','C','X1','X2','X3','A','B','C']
    print(json.dumps({'hand': trace(hand, 3),
                      'distances': reuse_distances(hand),
                      'anomaly_misses': {
                          p: [miss_count(anomaly, c, p) for c in (3,4)]
                          for p in ('lru', 'fifo')},
                      'scan_misses': miss_count(scan, 3)}, indent=2))

复杂度和真实系统的边界

文章验证程序枚举三种键、长度 0…7 的全部轨迹，再加 320 条固定种子的随机轨迹，共 3,600 条序列；每条检查容量 0…5，共 21,600 组、225,786 次请求。独立参考使用最后访问时间戳选择淘汰项，并用完整最近访问栈核对复用距离；还检查容量包含关系、合法空值及加载失败时状态不变。这些检查验证该离散模型，不代表任何真实业务负载的性能基准。

不计加载、键哈希及值大小，缓存核心单次期望 O(1)，保存 O(C) 个条目。代码为方便审查，每次生成的 order 是 O(C) 的快照，所以 trace 的总时间和输出空间为 O(TC)，不能用它计时声称实际请求全程 O(1)。复用距离参考最坏时间 O(T²)，辅助空间 O(T)。

缓存正确性还取决于数据何时失效；过期价格、权限变化或用户隔离不能由访问顺序决定。加载器发生重入或多线程并发时，本文对象没有同步与请求合并保证，不能直接当作生产组件。functools.lru_cache 官方说明也区分内部状态线程安全与同键底层函数可能重复执行；不要把“有缓存”理解成“同键最多加载一次”。

自检：同一个键之间有十次请求，复用距离就一定是十吗？

不是。复用距离数的是不同键。例如 A、B、B、B、A 的距离为 1，容量 2 的 LRU 会命中最后一个 A。在本文等大小、无过期的模型下 d 小于 C 才命中；容量 1 会未命中。

继续比较布隆过滤器的单向错误：它缓存的是成员预检信息，不直接保存权威记录；也可回看SQLite 索引实验，区分查询定位、结果缓存和底层加载。更多路线见计算机基础分类与资源索引。