0146.LRU缓存

难度：🟡 中等

标签：哈希表、链表、设计、双向链表

链接：146. LRU 缓存

题目描述

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

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存。

• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 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. 能够快速查找、插入和删除键值对。

2. 能够维护一个访问顺序，以便在容量满时，能快速找到并淘汰“最近最少使用”的数据。

为了同时满足这两个要求，单一的数据结构（如普通数组或哈希表）是不足的。

思路选择

哈希表 + 双向链表 是解决此问题的标准最优数据结构组合。

• 哈希表 (Map)：用于提供 O(1) 的平均时间复杂度来查找一个 key 是否存在，并直接获取到其在链表中的对应节点。Map 的键是 key，值是链表节点的引用。

• 双向链表 (Doubly Linked List)：用于维护数据的访问顺序。链表中的节点顺序代表了其被访问的时间顺序。我们规定：

  • 越靠近 链表头部 的节点，是 最近被使用 的。

  • 越靠近 链表尾部 的节点，是 最近最少被使用 的。

  • 使用双向链表的好处是，当我们需要移动或删除一个节点时，可以通过其 prev 和 next 指针在 O(1) 时间内完成操作，而无需遍历。

关键步骤

1. get(key) 操作: a. 通过哈希表查找 key。如果不存在，返回 -1。 b. 如果存在，获取对应的链表节点 node。 c. 将 node 从其当前位置移动到链表的头部，表示它刚刚被访问过。 d. 返回 node.value。

2. put(key, value) 操作: a. 检查 key 是否已存在于哈希表中。 i. 如果存在，更新对应节点 node 的 value，然后将 node 移动到链表头部。 ii. 如果不存在，创建一个新的节点 newNode。 b. 将 newNode 添加到链表头部，并在哈希表中设置 key 到 newNode 的映射。 c. 检查当前缓存大小是否超过 capacity。 i. 如果超过，则从链表尾部移除“最近最少使用”的节点。 ii. 同时，从哈希表中删除该尾部节点对应的 key。

代码实现

// 定义双向链表节点
var Node = function (key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
}

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
    this.capacity = capacity;
    this.cache = new Map();
    // 使用哨兵节点简化边界处理
    this.head = new Node(0, 0);
    this.tail = new Node(0, 0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
};

// 将节点移动到链表头部
LRUCache.prototype._moveToHead = function (node) {
    this._removeNode(node);
    this._addToHead(node);
}

// 在链表头部添加节点
LRUCache.prototype._addToHead = function (node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
}

// 从链表中移除节点
LRUCache.prototype._removeNode = function (node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

/** * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    if (!this.cache.has(key)) return -1;

    const node = this.cache.get(key);
    this._moveToHead(node);
    return node.value;
};

/** * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    if (this.cache.has(key)) {
        const node = this.cache.get(key);
        node.value = value;
        this._moveToHead(node);
    } else {
        const newNode = new Node(key, value);
        this.cache.set(key, newNode);
        this._addToHead(newNode);

        if (this.cache.size > this.capacity) {
            const tail = this.tail.prev;
            this._removeNode(tail);
            this.cache.delete(tail.key);
        }
    }
};

复杂度分析

• 时间复杂度：O(1) get 和 put 操作都只涉及哈希表的查找和双向链表的头部/尾部操作，这些都是常数时间复杂度的。

• 空间复杂度：O(capacity) 哈希表和双向链表最多存储 capacity 个元素。

相关题目

• 0460.LFU缓存

• 0001.两数之和

总结

LRU 缓存是面试中考察数据结构设计能力的经典题目。其标准解法——哈希表与双向链表的结合——完美地展示了如何组合不同数据结构的优点来满足复杂的性能要求。理解 get 和 put 操作如何同步更新哈希表和双向链表，是掌握此算法的关键。