LRU 是 Least Recently Used 的缩写,一种缓存替换策略。缓存(cache)的容量有限,新内容要进来,就必须挑一部分旧内容出去;LRU 挑的是“上一次被使用的时间距今最久”的那一条。

中文常把它译成“最近最少使用”,这个译名容易让人以为在数访问次数,那是 LFU(Least Frequently Used)的判据。least recently used 的重点是 recently——看的是“多久没用过”,不是“用过多少次”。课件自己也补了一句“译成最久未使用会更形象”,这句是对的。
两个结构,各管一件事
要让 get 和 put 都落在 O(1),得同时解决两个问题:按 key 找到数据,以及知道谁最旧。
只用哈希表,能 O(1) 找到值,但它不记录顺序,淘汰时只能扫全表找最旧的那条;只用链表,插入删除很便宜,可按 key 找结点要遍历。所以拆成两个结构:
- 哈希表:
key → 结点位置,负责定位; - 双向链表:按访问时间排序,头部最新、尾部最旧。
链路里最关键的一处设计,是哈希表的值存什么。只存 value,命中后还得在链表里找这个 key,退化成 O(N);存链表下标,链表根本没有下标这个概念;存迭代器或结点指针,才能直接摘下来再挂到头部。

课件把这一步叫“最巧的设计”,说得没错:哈希表存着链表结点,链表结点里存着 key,两者互指,才粘成一个整体。这里补一句常被说漏的前提——双向链表能做到“任意位置 O(1) 插入删除”,前提是你已经握着那个结点的指针;只给一个序号,找过去仍然是 O(N)。这也是哈希表必须存迭代器、不能存下标的原因。
方向要先约定死:头部最新,尾部最旧。命中就搬到头部,容量满了从尾部踢。反过来约定也能跑,但中途改主意不会当场报错,只会在某次淘汰时突然错一次。
get 与 put:命中就搬到表头
#include <list>
#include <unordered_map>
#include <utility>
#include <cstddef>
using namespace std;
class LRUCache
{
public:
explicit LRUCache(size_t capacity) : _capacity(capacity) {}
int get(int key)
{
auto it = _map.find(key);
if (it == _map.end())
return -1;
auto lit = it->second;
pair<int, int> kv = *lit; // erase 之前先拷出来
_list.erase(lit);
_list.push_front(kv); // 读也是一次使用
_map[key] = _list.begin(); // 迭代器变了,重新登记
return kv.second;
}
void put(int key, int value)
{
if (_capacity == 0)
return; // 没有坑位,put 什么也留不下
auto it = _map.find(key);
if (it != _map.end())
{
auto lit = it->second;
pair<int, int> kv = *lit;
kv.second = value;
_list.erase(lit);
_list.push_front(kv); // 更新已存在的 key 也算使用
_map[key] = _list.begin();
return;
}
if (_list.size() >= _capacity)
{
_map.erase(_list.back().first); // 先销登记
_list.pop_back(); // 再拆结点
}
_list.push_front(make_pair(key, value));
_map[key] = _list.begin();
}
private:
list<pair<int, int>> _list;
unordered_map<int, list<pair<int, int>>::iterator> _map;
size_t _capacity;
};四处细节决定它能不能跑对:
pair<int, int> kv = *lit;必须在erase之前。erase之后迭代器失效,再解引用是未定义行为。- 每次“删了再头插”,
std::list都会新建一个结点,旧迭代器跟着作废。忘记_map[key] = _list.begin(),下一次碰这个 key 就会读到已经释放的位置。 - 淘汰时先
_map.erase再pop_back。反过来的话,_list.back()已经换了人,你删掉的是另一个仍然在缓存里的 key,留下“表里有、链上没”的幽灵。 - 容量判断用
>=。写成>会让缓存稳定停在_capacity + 1,功能未必立刻出错,但后面的容量假设全废。
unordered_map 自身 rehash 会让指向它的迭代器失效,所以 find 出来的迭代器不要在插入之后再拿来用;存进 map 的是 std::list 的迭代器,它不受 rehash 影响。这个区分很多人第一次写 LRU 时会混。
课件在淘汰那段有一处注释错误:注释写“删除链表头的数据和 hashmap 中的数据”,紧跟的代码却是 _map.erase(_list.back().first); _list.pop_back();,删的是表尾。按“头新尾旧”的约定,代码对,注释错。读一份 LRU 实现,第一件事永远是确认它的方向,再看注释。
get 命中之后必须搬家,这一点在读写比例悬殊的负载里最明显。只返回不搬家,链表顺序就只剩写入顺序,实现的其实是 FIFO;读得最多的那批数据会一直蹲在最旧的位置,被优先扔掉。put 写入一个已存在的 key 同样算使用:它不占新坑位、不触发淘汰,但必须把结点搬到最新端。课件给出的示例序列里没有出现“对已有 key 再 put 一次”,所以这个分支的 bug 能一路隐身。
LRU 与 LFU 的判据不是一回事
| 策略 | 淘汰谁 | 需要维护的东西 | 典型短板 |
|---|---|---|---|
| FIFO(先进先出) | 最早进入的 | 一条队列 | 不管用得多频繁,到点就踢 |
| LRU | 最久没有被访问的 | 访问顺序 | 一次全表扫描会把热数据冲掉 |
| LFU | 访问次数最少的 | 频次计数 + 最小频次指针 | 曾经的热点降不下来,新数据进不来 |
LRU 假设的是时间局部性:刚访问过的,接下来大概率还会被访问。这个假设在“扫描型”负载里会被打穿——几十 GB 的冷数据依次流过,每一页都把热数据往尾部挤,扫完之后缓存里全是只读了一遍的垃圾。这不是实现错误,是策略本身的短板。
LFU 假设的是频率:访问次数多的更重要。它要维护每个 key 的频次,还要能 O(1) 找到“当前最小频次”的那一组,常见做法是频次桶加双向链表,桶数随最大频次增长。它的问题是“历史包袱”:一个 key 早期被访问了几百万次,之后不再使用,频次仍然很高,挤不掉;新出现的 key 频次从 1 开始,很难晋升。工程上的 LFU 通常要加频次衰减或者定期减半,否则缓存会逐渐僵化。
两者的实现代价也不同。LRU 只要一张哈希表加一条双向链表;LFU 要维护频次到链表的映射、最小频次指针,更新一个 key 时可能要在频次桶之间搬结点。要 O(1) 的 get/put,LRU 的结构更短,也更容易写对。
回到 O(1) 这句话本身:哈希表的增删查改是平均常数时间,最坏会退化成线性——所有 key 落进同一个桶时,它就是一条链表。写复杂度时把“平均”带上,不算吹毛求疵。LRU 的链表操作是严格 O(1),但整体仍然是“期望 O(1)”,因为前面那层哈希表不是严格常数。
还没有评论 — 第一条由你来留。