造轮子：手写 LRU Cache

本章目标

这一章实现一个 LRU 缓存。你会理解缓存为什么需要容量，什么是最近最少使用，如何用组合数据结构表达性能目标，以及为什么工程里常用成熟 crate。

它是什么

LRU 是 Least Recently Used，意思是“最近最少使用”。当缓存满了，要淘汰最久没有被访问的条目。

缓存需要两种能力：

• 快速按 key 找到 value。
• 快速知道谁最久没被使用。

常见工业实现会组合哈希表和链表。教学版可以先用 VecDeque 加 HashMap 思路实现。

为什么需要

缓存是系统编程和服务端工程的常见工具：减少重复计算、减少磁盘读取、减少网络请求。手写 LRU 可以帮你理解一个重要设计原则：单个数据结构经常无法同时满足所有操作，需要组合。

怎么使用

教学版 API：

let mut cache = LruCache::new(2);
cache.put("a", 1);
cache.put("b", 2);
cache.get("a");
cache.put("c", 3);

assert_eq!(cache.get("b"), None);

访问 a 后，b 变成最久未使用；插入 c 时淘汰 b。

逐行解释

fn touch(&mut self, key: &str) {
    self.order.retain(|existing| existing != key);
    self.order.push_back(key.to_string());
}

• fn touch 表示某个 key 刚刚被访问。
• &mut self 因为访问顺序会改变。
• retain 保留不等于当前 key 的元素，相当于先删除旧位置。
• existing != key 比较已有 key 和当前 key。
• push_back 把 key 放到队尾，表示最新使用。
• key.to_string() 因为队列要拥有这份 key。

这个版本不是最高性能，因为 retain 是线性扫描。但它清楚表达了 LRU 的语义。

常见坑

• get 也应该更新最近使用顺序，不只是 put。
• 容量为 0 时要明确行为，可以直接不存任何值。
• 教学版可能 O(n)，生产版通常追求 O(1)。
• 缓存会引入一致性问题：数据源变化时，缓存什么时候失效必须有策略。

练习

1. 定义 LruCache，内部用 HashMap<String, String> 和 VecDeque<String>。
2. 实现 put。
3. 实现 get，命中时更新顺序。
4. 写测试覆盖淘汰行为。

造轮子任务

给文档站设计一个 Markdown 渲染缓存：key 是章节 slug，value 是渲染后的 HTML。先写教学版结构，不急着接入项目。思考文件变化后缓存如何失效。

小结

LRU 展示了工程中常见的组合思维：哈希表负责查找，顺序结构负责淘汰策略。造轮子的价值不是替代成熟库，而是理解成熟库为什么这样设计。