LRU 缓存

请你设计并实现一个满足 LRU 最近最少使用约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity)：以正整数作为容量 capacity 初始化 LRU 缓存
• int get(int key)：如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
• void put(int key, int value)：如果关键字 key 已经存在，则更新它的值；如果不存在，则插入这组 key-value

如果插入操作导致关键字数量超过 capacity，则应该逐出最久未使用的关键字。

get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入：
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

输出：
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释：
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1
lRUCache.put(4, 4); // 该操作会使关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 10^5
• 最多调用 2 * 10^5 次 get 和 put

哈希表 + 双向链表：

class LRUCache {
private:
    int capacity;
    list<pair<int, int>> cache;
    unordered_map<int, list<pair<int, int>>::iterator> mp;

public:
    LRUCache(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        if (mp.find(key) == mp.end())
        {
            return -1;
        }

        auto it = mp[key];
        cache.splice(cache.begin(), cache, it);

        return cache.begin()->second;
    }

    void put(int key, int value) {
        if (mp.find(key) != mp.end())
        {
            auto it = mp[key];
            it->second = value;
            cache.splice(cache.begin(), cache, it);
            return;
        }

        if (cache.size() == capacity)
        {
            int oldKey = cache.back().first;
            cache.pop_back();
            mp.erase(oldKey);
        }

        cache.push_front({key, value});
        mp[key] = cache.begin();
    }
};

核心思想

这题的关键不只是保存 key-value，还要快速知道哪个 key 是最近最少使用的。

如果只用哈希表，可以做到根据 key 在 O(1) 平均时间内查找值。

但是哈希表不能维护“最近使用顺序”。

如果只用普通链表，可以维护使用顺序，但查找某个 key 又需要 O(n)。

所以要把两种结构结合起来：

• 哈希表：负责 O(1) 平均时间定位某个 key
• 双向链表：负责 O(1) 时间移动节点和删除最久未使用节点

这题最关键的观察是：

把最近使用的节点放到链表头部，那么链表尾部就是最久未使用的节点。

因此，每次 get 或更新已有 key 时，都把这个节点移动到链表头部。

当缓存满了还要插入新节点时，删除链表尾部节点即可。

数据结构设计

代码中使用：

list<pair<int, int>> cache;

它表示双向链表。

链表中每个节点保存：

key, value

链表顺序约定为：

头部：最近使用
尾部：最久未使用

再使用哈希表：

unordered_map<int, list<pair<int, int>>::iterator> mp;

它的含义是：

key -> 这个 key 在链表中的位置

这样就可以通过 key 直接找到链表节点，然后用 splice 把节点移动到头部。

get 操作

如果 key 不存在：

return -1;

如果 key 存在，说明这个节点刚刚被访问过，所以它变成最近使用的节点。

需要把它移动到链表头部：

cache.splice(cache.begin(), cache, it);

然后返回节点中的 value：

return cache.begin()->second;

splice 不会重新创建节点，只是改变链表指针，因此是 O(1) 操作。

put 操作

put 分成两种情况。

1. key 已经存在

如果 key 已经存在，只需要更新值：

it->second = value;

同时，这次 put 也算一次使用，所以要把它移动到链表头部：

cache.splice(cache.begin(), cache, it);

2. key 不存在

如果 key 不存在，需要插入新节点。

插入前先判断缓存是否已满：

if (cache.size() == capacity)

如果已满，链表尾部就是最久未使用节点。

先取出尾部节点的 key：

int oldKey = cache.back().first;

然后从链表和哈希表中同时删除：

cache.pop_back();
mp.erase(oldKey);

最后把新节点插入链表头部，并记录它在链表中的位置：

cache.push_front({key, value});
mp[key] = cache.begin();

为什么必须同时维护 key 和 value

链表节点中不能只保存 value。

因为当缓存满了，需要删除尾部节点时，还要从哈希表中删除对应的 key。

尾部节点如果只保存 value，就不知道应该执行：

mp.erase(oldKey);

所以链表节点必须保存完整的：

key-value

为什么可以做到 O(1)

对于 get：

• 用哈希表查找 key，平均 O(1)
• 用链表迭代器定位节点，O(1)
• 用 splice 移动节点到头部，O(1)

对于 put：

• 用哈希表判断 key 是否存在，平均 O(1)
• 更新已有节点并移动到头部，O(1)
• 删除链表尾部节点，O(1)
• 插入链表头部节点，O(1)
• 更新哈希表，平均 O(1)

因此两个操作都满足题目要求。

边界情况

如果 get 的 key 不存在，直接返回 -1，并且不改变缓存。

如果 put 的 key 已经存在，只更新值，不增加缓存容量。

如果容量为 1，每次插入新 key 时，都会淘汰原来的唯一节点。

题目保证 capacity >= 1，所以不需要处理容量为 0 的情况。

正确性证明

我们证明：算法始终能正确返回缓存值，并在容量不足时逐出最久未使用的关键字。

结论 1：哈希表始终能准确定位缓存中的节点

每次插入新节点时，算法都会执行：

mp[key] = cache.begin();

把 key 映射到新节点在链表中的位置。

每次淘汰尾部节点时，算法会先取出尾部节点的 key，再执行：

mp.erase(oldKey);

因此被删除的节点不会继续留在哈希表中。

对于已经存在的 key，算法只移动链表节点，不删除节点本身，迭代器仍然指向同一个节点。

所以哈希表始终能准确定位缓存中的节点。

结论 2：链表顺序始终表示从最近使用到最久未使用

新插入的节点刚刚被使用，所以被放在链表头部。

get 命中某个节点时，这个节点刚刚被访问，所以被移动到链表头部。

put 更新已有节点时，这个节点刚刚被修改，也应该视为最近使用，所以同样被移动到链表头部。

其它节点的相对顺序没有改变。

因此链表从头到尾始终表示从最近使用到最久未使用。

结论 3：缓存满时删除链表尾部节点是正确的

由结论 2 可知，链表尾部节点就是当前最久未使用的节点。

当缓存满了还要插入新 key 时，题目要求逐出最久未使用的关键字。

算法删除链表尾部节点，并从哈希表中删除对应 key。

所以逐出操作正确。

结论 4：get 返回值正确

如果 key 不在哈希表中，说明缓存中不存在这个关键字，返回 -1 正确。

如果 key 在哈希表中，哈希表能定位到对应链表节点。

这个节点保存的 second 就是该关键字当前的值。

算法返回这个值，并把节点移动到头部，符合 get 的语义。

得出结论

由结论 1 可知，哈希表和链表中的节点关系始终正确。

由结论 2 可知，链表尾部始终是最久未使用节点。

由结论 3 可知，容量不足时的淘汰策略正确。

由结论 4 可知，get 的返回值正确。

因此算法正确实现了 LRUCache。

举例理解

以：

capacity = 2

为例。

链表头部表示最近使用，尾部表示最久未使用。

可以看到，每次访问过的节点都会移动到头部。

当需要淘汰时，总是删除尾部节点。

复杂度分析

设缓存容量为 capacity。

哈希表最多保存 capacity 个键，链表最多保存 capacity 个节点。

get 和 put 中的哈希表查找、插入、删除平均都是 O(1)。

链表节点移动、头插和尾删也都是 O(1)。

所以：

• 时间复杂度：get 和 put 平均都是 O(1)
• 空间复杂度：O(capacity)