前言缓存的核心矛盾是容量有限而数据无限当新的键值对要进来而缓存已满时必须挑一个旧条目淘汰。挑谁就是缓存淘汰算法要回答的问题。FIFO 按进入时间淘汰LRU 按最近使用时间淘汰LFU 按使用频率淘汰CLOCK 用一个环形指针和访问位近似 LRU。它们在命中率、实现复杂度和对访问模式的适应性上各有取舍。关于 LRU 的典型误解有两个。第一个是把它等同于「记录每个键的最后访问时间戳淘汰时排序取最小」这种做法每次淘汰都要 O(n log n)而且在时间戳精度不足或系统时钟回拨时会失效。第二个是以为必须用数组或std::vector保存顺序于是每次命中都要把元素挪到头部单次操作退化成 O(n)。真正的 O(1) 实现依赖两个结构的配合哈希表负责定位双向链表负责顺序。本文先对比几种常见策略的适用场景再给出基于std::list与std::unordered_map的 LRU 实现最后讨论把它用到多线程环境时需要补哪些东西。代码以 C17 为基准。一、淘汰策略在解决什么问题一段程序的访问往往具有时间局部性刚刚访问过的数据很可能马上还会被访问。LRU 正是把这条经验编码成规则——最近被访问过的条目留在缓存里最久没被访问的条目最先淘汰。它对「循环扫描」这类访问模式表现很差如果工作集比缓存略大且按固定顺序循环访问那么每次访问的恰好都是即将被淘汰的那个命中率会降到零。这种现象称为缓存颠簸thrashing是所有「按历史预测未来」的策略共同的天花板。FIFO 完全不看访问历史只按插入顺序淘汰。它实现最简单但对「先加载、后频繁访问」的数据很不友好一个早期加载但一直很热的数据会因为「资格老」而被踢出去。LFU 记录每个键被访问的次数淘汰次数最少的它能保护长期热点但新加入的键因为计数从零开始很容易在被访问够之前就被淘汰而且计数器需要定期衰减否则历史热点会永久占据缓存。CLOCK 是 LRU 的低成本近似所有条目排成一个环每个条目有一个访问位命中时把访问位置 1需要淘汰时指针沿环扫描遇到访问位为 1 的清零并跳过遇到 0 的就淘汰。它不需要在每次命中时移动链表节点代价是淘汰结果只是「近似最近未使用」。策略淘汰依据单次操作复杂度优点缺点FIFO插入顺序O(1)实现最简单不识别热点LRU最近访问时间O(1)哈希表加链表符合时间局部性循环扫描时命中率崩塌LFU访问频次O(1)频次桶保护长期热点新条目饥饿需衰减CLOCK访问位加环形扫描均摊 O(1)命中时无链表操作只是近似 LRU随机随机选取O(1)无需维护顺序命中率不可控二、LRU 的两个不变式要用 O(1) 完成「查询」「插入」「提升为最近使用」「淘汰最久未使用」四件事需要两个结构同步维护第一一条双向链表头部是最近使用的条目尾部是最久未使用的条目。命中一个键时把对应节点从原位置摘下来挂到头部插入新键时挂到头部淘汰时删掉尾部节点。第二一张哈希表键映射到链表节点的迭代器。没有它查找就得遍历链表退化成 O(n)。两个结构必须始终一致链表里有多少节点哈希表里就有多少项哈希表里存的迭代器必须指向链表中真实存在的节点。这里的幸运之处在于std::list的迭代器在splice之后仍然有效——节点只是被重新链接内存位置没有变。这正是可以用splice把节点搬到头部、而不必先 erase 再 insert 的原因也是整个实现能做到 O(1) 的关键。如果换成std::vector情况完全不同任何一次插入或删除都可能让所有迭代器和指针失效哈希表里存的下标全部作废而且头部插入是 O(n)。这就是「用 vector 实现 LRU」在实践中总是很慢的根源。三、完整实现下面的实现把容量、链表和索引封装成一个类模板。get返回值类型的std::optional未命中时返回空put在容量为 0 时直接忽略避免出现「插入后立刻淘汰自己」的荒谬行为。// 适用于 C17#include cstddef#include list#include optional#include unordered_map#include utilitytemplate class Key, class Valueclass LruCache {public:explicit LruCache(std::size_t capacity) : capacity_(capacity) {}std::optionalValue get(const Key key) {auto it index_.find(key);if (it index_.end()) {return std::nullopt;}// 命中把节点搬到链表头部迭代器仍然有效items_.splice(items_.begin(), items_, it-second);return it-second-value;}void put(const Key key, const Value value) {if (capacity_ 0) {return;}auto it index_.find(key);if (it ! index_.end()) {it-second-value value;items_.splice(items_.begin(), items_, it-second);return;}if (items_.size() capacity_) {// 尾部是最久未使用的条目先删索引再删节点index_.erase(items_.back().key);items_.pop_back();}items_.push_front(Entry{key, value});index_[key] items_.begin();}std::size_t size() const { return items_.size(); }std::size_t capacity() const { return capacity_; }private:struct Entry {Key key;Value value;};std::size_t capacity_;std::listEntry items_; // 头部最新尾部最旧std::unordered_mapKey, typename std::listEntry::iterator index_;};使用方式很直接// 适用于 C17#include iostream#include stringint main() {LruCachestd::string, int cache(2);cache.put(a, 1);cache.put(b, 2);(void)cache.get(a); // 命中a 变成最近使用cache.put(c, 3); // 淘汰最久未使用的 bstd::cout (cache.get(a).has_value() ? a 在 : a 不在) \n;std::cout (cache.get(b).has_value() ? b 在 : b 不在) \n;std::cout cache.size() \n;return 0;}按标准语义推演插入a、b后链表顺序是b, a头到尾get(a)后变成a, b插入c时容量已满淘汰尾部b链表变成c, a所以a命中、b未命中、size()为 2。有三处细节值得单独说明。第一put命中已有键时不能走到「淘汰尾部」的分支否则会把别的条目误删。第二淘汰时必须先index_.erase(items_.back().key)再pop_back()顺序反了就拿不到被删节点的键哈希表里会留下一个指向已销毁节点的迭代器后续任何get都是未定义行为。第三get返回的是值的副本如果Value很大应当改成返回const Value*但必须同时约定「指针在下一次put之后可能失效」。put的签名用const Value而不是Value避免调用方传入临时对象时多一次拷贝如果希望支持移动语义可以增加一个Value重载并在内部用std::move构造Entry但要注意此时Entry{key, std::move(value)}的写法需要Entry支持对应的构造。四、放到多线程与生产环境上面的实现完全没有同步。std::unordered_map的并发读写是数据竞争属于未定义行为不是「偶尔读到旧值」这么温和。最直接的做法是在get和put外面套一把std::mutex用std::lock_guard管理代价是所有操作串行热点键会成为瓶颈。进一步的优化方向有三个。其一是分片把键按哈希值分到若干个独立的子缓存每个子缓存有自己的锁锁竞争按分片数摊薄。其二是读写锁std::shared_mutex允许多个读并行但get会修改链表顺序本质上是写操作所以这个方案对 LRU 意义不大对只读缓存才适用。其三是把淘汰做成后台线程的异步清理前台只负责写入和打标记代价是「容量上限」变成软约束。还有一个常被忽略的点TTL。LRU 只按访问顺序淘汰不关心数据是否过期。如果缓存的是有有效期的数据需要在条目里加时间戳并在get时判断是否过期过期条目的清理可以和 LRU 淘汰共用同一条链表但判定逻辑必须分开写。常见坑点坑点一用 vector 保存顺序每次命中都移动元素。❌std::vectorEntry items;命中时std::rotate或erase加insert单次操作 O(n)。✅ 用std::list加splice节点搬家不改变迭代器单次操作 O(1)。坑点二淘汰时先删节点、后删索引。❌items_.pop_back(); index_.erase(key);此时key已经随节点一起销毁。✅ 先取出尾部节点的键并index_.erase再pop_back。坑点三容量为 0 时仍然执行插入。❌ 构造函数接受 0put里先插入再淘汰逻辑上刚插入就被删掉还可能触发对空链表的back()。✅put开头判断capacity_ 0直接返回或者构造时断言容量大于 0。坑点四get返回引用或指针随后条目被淘汰。❌const Value v *cache.get(k);下一次put之后v悬垂。✅ 返回值类型如std::optionalValue或者明确文档化「指针仅在下次修改前有效」。坑点五多线程下不加锁直接读写哈希表。❌ 两个线程同时调用putunordered_map内部桶数组可能正在重建行为未定义。✅ 用互斥量保护整个缓存或按哈希分片后每片独立加锁。坑点六用时间戳排序实现 LRU。❌ 给每个条目记一个steady_clock时间点淘汰时遍历找最小。✅ 用链表顺序表达「最近使用」时间戳只用于 TTL 判断。坑点七put命中已有键时错误地走了淘汰分支。❌ 不区分「键已存在」和「键不存在」每次put都先淘汰尾部。✅ 先查索引命中就更新值并splice到头部未命中才考虑淘汰。坑点八把 LFU 的频次直接当 LRU 用。❌ 认为「访问次数多就等于最近使用」在阶段性热点切换后长期保留已经冷掉的数据。✅ 按访问模式选策略需要兼顾时用 LRU 加频次衰减或直接用 W-TinyLFU 一类组合策略。总结要点结论LRU 的核心结构双向链表维护顺序哈希表负责定位命中操作splice把节点搬到头部O(1)淘汰操作删除链表尾部同步删除哈希表项迭代器有效性std::list的迭代器在splice后仍有效容量为零直接拒绝写入避免空链表操作线程安全默认没有需要互斥量或分片策略选择时间局部性用 LRU长期热点用 LFU低成本用 CLOCK已知缺陷循环扫描时命中率崩塌LRU 本身只有二十来行难的是想清楚「为什么必须是链表加哈希表」以及「两个结构在什么时刻必须保持一致」。把这两点吃透再去看工程实现里的分片、TTL、异步淘汰就只是在这套骨架上加零件而已。