跳到主要内容

LeetCode 146. LRU 缓存

本节目标

用哈希表定位节点、双向链表维护最近使用顺序，实现常数时间缓存操作。

这道题承接数据结构综合。它的难点不是单独使用哈希表或链表，而是在每一次操作后让“键能定位节点”和“节点顺序反映最近使用”同时成立。

查看原题

题意与约束​

实现固定容量的缓存，支持 get(key) 与 put(key, value)。访问或写入一个键后，它成为最近使用；容量已满时，插入新键前要淘汰最久未使用的键。题目要求两种操作平均为 O(1)。

单用哈希表能快速按键找到值，却不知道谁最久未使用；单用链表能表示顺序，却要线性查找某个键所在节点。两个需求分别交给不同结构。

两个结构各自负责什么​

  • 哈希表保存 key -> node，因此 get 或覆盖已有键时能直接定位链表节点。
  • 双向链表从头到尾表示“最近使用到最久使用”。头部紧后方是最新节点，尾部紧前方是最旧节点，移动和删除都是常数时间。

头、尾哨兵不保存真实缓存数据。它们让插入头部、删除尾部前节点不必为第一个或最后一个真实节点写特殊分支。

同步不变量与四种更新​

任意时刻都保持三条不变量：哈希表中的每个键恰好对应一个真实链表节点；每个真实节点恰好有一个哈希表键指向它；链表从头到尾严格按最近使用到最久使用排列。

  1. 插入新键：创建节点，同时写入哈希表，再插到头哨兵后。
  2. 访问命中：哈希表找到节点，把它从原位置摘下并插到头部，返回值不变。
  3. 覆盖已有键：不创建第二个节点；先更新节点值，再把同一个节点移到头部。
  4. 容量淘汰：若节点数超过容量，取尾哨兵前的节点，从链表摘下、从哈希表删除对应键，再释放或丢弃节点。

只移动链表不更新映射会造成以后定位到脱链节点；只删除映射不删除链表会留下错误的淘汰候选。同步更新是本题正确性的核心。

代码实现​

C++ 为真实节点动态分配，并在析构函数中遍历释放包括哨兵在内的全部节点；Python 以独立的 Node 类保存键、值和双向链接。两种实现的 get 命中和 put 覆盖都调用同一移动到头部操作。

C++17
#include <unordered_map>
using namespace std;

class Node {
public:
    int key;
    int value;
    Node* prev;
    Node* next;

    Node(int key, int value) : key(key), value(value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
public:
    LRUCache(int capacity) : capacity(capacity), head(new Node(0, 0)), tail(new Node(0, 0)) {
        head->next = tail;
        tail->prev = head;
    }

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

    int get(int key) {
        auto it = nodes.find(key);
        if (it == nodes.end()) {
            return -1;
        }
        moveToFront(it->second);
        return it->second->value;
    }

    void put(int key, int value) {
        auto it = nodes.find(key);
        if (it != nodes.end()) {
            it->second->value = value;
            moveToFront(it->second);
            return;
        }

        Node* node = new Node(key, value);
        nodes[key] = node;
        addToFront(node);

        if (static_cast<int>(nodes.size()) > capacity) {
            Node* leastRecent = tail->prev;
            remove(leastRecent);
            nodes.erase(leastRecent->key);
            delete leastRecent;
        }
    }

private:
    int capacity;
    unordered_map<int, Node*> nodes;
    Node* head;
    Node* tail;

    void remove(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void addToFront(Node* node) {
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

    void moveToFront(Node* node) {
        remove(node);
        addToFront(node);
    }
};

复杂度分析​

  • 时间复杂度：get 和 put 都是期望 O(1)。哈希表定位、链表摘除、插入头部和删除尾部前节点均为常数次操作。
  • 空间复杂度：O(capacity)。哈希表与双向链表各保存至多容量个真实节点。

易错点​

  • get 命中后忘记更新顺序：随后会淘汰刚访问过的键。
  • 覆盖已有键时新建节点：旧节点或旧映射会残留，破坏一键一节点。
  • 淘汰后只从链表删除：哈希表仍能找到已失效节点。
  • 不使用哨兵却遗漏空链表或首尾节点边界。
  • 让多个缓存实例共享节点表：不同容量的对象必须维护独立状态。

模式迁移​

组合结构先拆分职责，再为每次更新列出所有需同步的状态。哈希表负责定位、双向链表负责顺序的模式也可迁移到需要按键删除的队列、滑动窗口和在线调度问题；本章前面的哈希表只解决了其中的快速定位部分。