0146. LRU Cache

题目信息

题号:
  1. LRU 缓存

难度:

Medium

主题:

设计、哈希表、双向链表、数据结构不变量

原题:

LeetCode 0146

重点:

让哈希表回答键定位,让双向链表维护使用顺序,并保持两种结构对每个缓存项的一一对应

题目重述

设计容量固定的最近最少使用缓存 LRUCache:

  • get(key):键存在时返回值,并把它更新为最近使用;不存在返回 -1,顺序不变;

  • put(key, value):已有键就更新值并刷新为最近使用;新键则插入。插入后超过容量时,删除最久没有被 成功 get 或 put 的键。

两种操作都要求平均 O(1) 时间。容量至少为一。

自建示例

LRUCache cache(2)
put(4, 40)    顺序:[4]
put(7, 70)    顺序:[7, 4]
get(4) -> 40  顺序:[4, 7]
put(9, 90)    顺序:[9, 4],淘汰 7
get(7) -> -1  顺序仍为 [9, 4]

容量为一时连续执行 put(3, 8)、put(3, 11) 只是更新同一条目,不应先淘汰再创建;随后 get(3) 返回 11。

C++ 实现

#include <unordered_map>

class LRUCache {
private:
    struct Node {
        int key;
        int value;
        Node* previous;
        Node* next;

        Node(int nodeKey, int nodeValue)
            : key(nodeKey),
              value(nodeValue),
              previous(nullptr),
              next(nullptr) {}
    };

    int capacity_;
    std::unordered_map<int, Node*> index_;
    Node* mostRecentSentinel_;
    Node* leastRecentSentinel_;

    void detach(Node* node) {
        node->previous->next = node->next;
        node->next->previous = node->previous;
    }

    void insertAsMostRecent(Node* node) {
        node->previous = mostRecentSentinel_;
        node->next = mostRecentSentinel_->next;
        mostRecentSentinel_->next->previous = node;
        mostRecentSentinel_->next = node;
    }

    void markAsMostRecent(Node* node) {
        detach(node);
        insertAsMostRecent(node);
    }

public:
    LRUCache(int capacity)
        : capacity_(capacity),
          mostRecentSentinel_(new Node(0, 0)),
          leastRecentSentinel_(new Node(0, 0)) {
        mostRecentSentinel_->next = leastRecentSentinel_;
        leastRecentSentinel_->previous = mostRecentSentinel_;
    }

    int get(int key) {
        auto found = index_.find(key);
        if (found == index_.end()) {
            return -1;
        }
        Node* node = found->second;
        markAsMostRecent(node);
        return node->value;
    }

    void put(int key, int value) {
        auto found = index_.find(key);
        if (found != index_.end()) {
            Node* node = found->second;
            node->value = value;
            markAsMostRecent(node);
            return;
        }

        Node* node = new Node(key, value);
        index_[key] = node;
        insertAsMostRecent(node);

        if (static_cast<int>(index_.size()) > capacity_) {
            Node* victim = leastRecentSentinel_->previous;
            detach(victim);
            index_.erase(victim->key);
            delete victim;
        }
    }

    ~LRUCache() {
        Node* node = mostRecentSentinel_;
        while (node != nullptr) {
            Node* next = node->next;
            delete node;
            node = next;
        }
    }
};

题解

先列出每次操作真正需要什么

get 需要按键找到条目,并把它移到“最新”位置;put 还需要在容量超限时立刻找到“最旧”条目。于是 至少有三类基本操作:

  • 按键定位任意条目;

  • 已知条目时从顺序中删除并移到最前;

  • 直接取得并删除顺序末尾。

若只用哈希表,可给每个键附带递增时间戳,查找和刷新是平均 O(1),但淘汰时必须扫描所有条目寻找最小 时间戳,耗时 O(capacity)。若只用按新旧排列的普通序列,末尾淘汰很快,按键查找和把中间条目移到 最前又需要线性扫描。单一结构各自只解决了一半问题。

组合结构怎样分工

哈希表 index_ 保存 key -> Node*,负责平均常数时间定位。双向链表按使用时间排列,越靠近 mostRecentSentinel_ 越新,越靠近 leastRecentSentinel_ 越旧。已知节点地址后,双向链表能通过 previous、next 在常数时间摘除中间节点;单链表做不到,因为它还要寻找前驱。

两个哨兵不代表缓存项,只固定边界:

mostRecentSentinel
    <-> 最近使用项 <-> ... <-> 最久未使用项
    <-> leastRecentSentinel

空缓存时两个哨兵直接相连。插入首项、删除末项与处理中间节点使用完全相同的四个指针更新,不需要分别处理 空表、头节点和尾节点分支。

必须始终保持的三个不变量

  1. 每个真实缓存键在哈希表中出现一次,也在两个哨兵之间出现一次;index_[key] 正好指向该链表节点;

  2. mostRecentSentinel_->next 是最近成功访问的条目,leastRecentSentinel_->previous 是最久未访问项;

  3. 哈希表大小等于真实链表节点数,并且不超过容量(一次新插入的检查过程中可暂时多一)。

detach 只接受真实节点,用两次跨接把它从当前位置删除;insertAsMostRecent 把节点插到头哨兵之后。 markAsMostRecent 组合两者,因此命中节点原本就在最前也无需特判:先摘除再插回,结果不变量不变。

get 的分支意义

哈希未命中时返回 -1,这次访问没有对应缓存项,不能改变新旧顺序。命中时先取得节点指针,移动到最新 位置,再返回值。移动与返回的先后在单线程结果上等价,但代码把“成功访问必刷新”集中在返回之前,不会 遗漏副作用。

对示例中的 get(4),原顺序 [7, 4] 先摘下 4 得到 [7],再插到头部得到 [4, 7]; 随后淘汰依据已经正确改变。

put 必须先区分覆盖与新增

已有键的 put 只更新现有节点的 value 并刷新位置,条目数不变,所以不能执行容量淘汰。新键才分配 节点、同时写入哈希并插到最新位置。若此时哈希大小超过容量,leastRecentSentinel_->previous 就是唯一 应淘汰节点:先从链表摘除,再用节点内保存的 key 从哈希删除,最后释放节点。

删除必须同时作用于两种结构。只删哈希会让链表留下不可定位的旧节点;只删链表会让后续 get 取得悬空 或已淘汰节点。节点同时保存 key 和 value,正是为了从表尾选中 victim 后能反向删除哈希项。

完整操作走读

操作

链表顺序(新到旧)

哈希变化

put(4, 40)

[4]

增加 4 -> node4

put(7, 70)

[7, 4]

增加键 7

get(4)

[4, 7]

映射不变,只移动节点

put(9, 90)

先 [9, 4, 7],再淘汰尾部成为 [9, 4]

增加 9,删除 7

get(7)

[9, 4]

未命中,不变

析构与边界状态

析构函数沿 next 删除整条链,包括两个哨兵和所有尚存数据节点,防止手工 new 的内存泄漏。容量至少 为一,所以新插入后需要淘汰时,尾哨兵前必有真实节点;代码不会把哨兵当 victim。哨兵没有放入哈希,它们 的占位键值也不会与用户键冲突。

复杂度与方案选择

哈希查找、插入和删除平均 O(1);已知节点的双向链表摘除、头插和尾部定位都是严格 O(1),所以 get、put 均满足平均 O(1)。空间为至多 capacity 个节点和哈希项,即 O(capacity)。 主解采用哈希表与双向链表组合,因为它恰好覆盖三类所需操作;时间戳扫描与单序列方案只作为瓶颈推导, 没有额外认知收益值得保留第二份较长 C++ 实现。