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

狭义的 Cache 指 CPU 与主存之间的快速 SRAM:容量小、速度快,放不下的数据必须有替换规则,LRU 是其中最常用的一种

中文常把它译成“最近最少使用”,这个译名容易让人以为在数访问次数,那是 LFU(Least Frequently Used)的判据。least recently used 的重点是 recently——看的是“多久没用过”,不是“用过多少次”。课件自己也补了一句“译成最久未使用会更形象”,这句是对的。

两个结构,各管一件事

要让 get 和 put 都落在 O(1),得同时解决两个问题:按 key 找到数据,以及知道谁最旧。

只用哈希表,能 O(1) 找到值,但它不记录顺序,淘汰时只能扫全表找最旧的那条;只用链表,插入删除很便宜,可按 key 找结点要遍历。所以拆成两个结构:

  • 哈希表:key → 结点位置,负责定位;
  • 双向链表:按访问时间排序,头部最新、尾部最旧。

链路里最关键的一处设计,是哈希表的值存什么。只存 value,命中后还得在链表里找这个 key,退化成 O(N);存链表下标,链表根本没有下标这个概念;存迭代器或结点指针,才能直接摘下来再挂到头部。

上排是哈希表的键 k1 到 k5,下排是双向链表的结点 n1 到 n5;键的编号和结点位置没有关系,每个 key 直接记着自己结点在哪里,才能跳过查找直接摘链

课件把这一步叫“最巧的设计”,说得没错:哈希表存着链表结点,链表结点里存着 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;
};

四处细节决定它能不能跑对:

  1. pair<int, int> kv = *lit; 必须在 erase 之前。erase 之后迭代器失效,再解引用是未定义行为。
  2. 每次“删了再头插”,std::list 都会新建一个结点,旧迭代器跟着作废。忘记 _map[key] = _list.begin(),下一次碰这个 key 就会读到已经释放的位置。
  3. 淘汰时先 _map.erase 再 pop_back。反过来的话,_list.back() 已经换了人,你删掉的是另一个仍然在缓存里的 key,留下“表里有、链上没”的幽灵。
  4. 容量判断用 >=。写成 > 会让缓存稳定停在 _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)”,因为前面那层哈希表不是严格常数。