146. LRU 缓存

题目链接（中等）

题目描述

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

实现 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) 的平均时间复杂度运行。

数据范围：

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

示例

输入：

["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

核心思路

LRU 缓存需要支持两种操作，都要求 $O(1)$：

• get(key)：快速找到某个 key 对应的值；
• put(key, value)：插入或更新，并在超出容量时淘汰「最久未使用」的 key。

两个核心难点：

1. 快速定位：用哈希表存储 key → 节点 的映射，$O(1)$ 查找；
2. 维护使用顺序：用双向链表维护访问顺序，靠近头部的是最近使用的，靠近尾部的是最久未使用的。

为什么是双向链表而不是单链表？

• 需要在 $O(1)$ 时间内删除任意节点（移动到头部时需要先删再插）；
• 单链表删除一个节点需要知道它的前驱，无法在 $O(1)$ 完成；
• 双向链表有 prev 指针，$O(1)$ 就能删除。

为什么不用数组 / 队列？

• 数组删除任意位置是 $O(n)$；
• 普通队列无法在 $O(1)$ 内移动任意元素到头部。

---

方法一：使用 OrderedDict（最简，但面试可能不接受）

思路及解法

Python 的 collections.OrderedDict 是一个哈希表 + 双向链表的内置实现，天然记录插入顺序，并支持 move_to_end 和 popitem。

• get：若 key 存在，先用 move_to_end(key) 移到末尾（表示最近使用），再返回值；
• put：若 key 已存在，先 move_to_end，再更新值；若不存在，插入后判断是否超容量，超出则 popitem(last=False) 淘汰最久未使用的（队首）。

代码

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

复杂度分析

• 时间复杂度：get 和 put 均为 $O(1)$。
• 空间复杂度：$O(\text{capacity})$。

面试注意：OrderedDict 太简单，通常不符合面试官「自己实现双向链表」的期望。可以作为快速解法提一下，正式作答建议手写双向链表。

---

方法二：哈希表 + 双向链表（推荐）

思路及解法

数据结构：

• cache：哈希表，key → DLinkedNode，用于 $O(1)$ 定位节点；
• 双向链表：按使用顺序存储所有节点；
  • head：伪头部，head.next 是最近使用的节点；
  • tail：伪尾部，tail.prev 是最久未使用的节点；
• 伪头部 / 伪尾部的意义：避免插入 / 删除时判断相邻节点是否存在，代码更简洁。

get(key) 流程：

1. 若 key 不存在，返回 -1；
2. 若存在，通过哈希表定位到节点，把它移到链表头部（表示最近使用），返回 node.value。

put(key, value) 流程：

1. 若 key 不存在：
   • 创建新节点，加入哈希表；
   • 加入链表头部；
   • size += 1；
   • 若 size > capacity：
     • 删除链表尾部节点 removed（最久未使用）；
     • 从哈希表中删除 removed.key；
     • size -= 1；
2. 若 key 存在：
   • 通过哈希表定位到节点，更新值 node.value = value；
   • 移到链表头部。

辅助函数：

• addToHead(node)：把节点加到头部；
• removeNode(node)：从链表中摘下节点；
• moveToHead(node)：removeNode + addToHead；
• removeTail()：摘掉尾节点并返回。

代码

class DLinkedNode:
    def __init__(self, key: int = 0, value: int = 0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.cache = {}                      # key -> DLinkedNode
        self.head = DLinkedNode()            # 伪头部
        self.tail = DLinkedNode()            # 伪尾部
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.moveToHead(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self.addToHead(node)
            self.size += 1
            if self.size > self.capacity:
                removed = self.removeTail()
                self.cache.pop(removed.key)
                self.size -= 1
        else:
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)

    def addToHead(self, node: DLinkedNode) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def removeNode(self, node: DLinkedNode) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def moveToHead(self, node: DLinkedNode) -> None:
        self.removeNode(node)
        self.addToHead(node)

    def removeTail(self) -> DLinkedNode:
        node = self.tail.prev
        self.removeNode(node)
        return node

复杂度分析

• 时间复杂度：get 和 put 均为 $O(1)$。哈希表定位 $O(1)$，链表插入 / 删除 $O(1)$。
• 空间复杂度：$O(\text{capacity})$，哈希表和双向链表最多存储 capacity + 1 个元素。

---

两种方法对比

方法	时间	空间	是否满足面试期望	特点
OrderedDict	$O(1)$	$O(\text{capacity})$	❌	代码最短，但用内置库
哈希表 + 双向链表	$O(1)$	$O(\text{capacity})$	✅	面试标准解法

推荐：

• 面试：手写方法二（哈希 + 双向链表），这是本题的标准答案；
• 日常刷题：方法一（OrderedDict），代码短，能过。

---

常见错误

错误	原因	修正
put 更新已有 key 时忘记移到头部	更新也视为「使用」	更新后调用 moveToHead
淘汰时忘记从哈希表中删除	哈希表和链表需要同步	self.cache.pop(removed.key)
用单链表导致删除不是 $O(1)$	单链表无法 $O(1)$ 删除任意节点	用双向链表
没有伪头 / 伪尾，边界判断冗长	首尾节点处理需要特判	加 head、tail 两个哑节点
节点没有存 key	淘汰尾节点时无法从哈希表删除	DLinkedNode 同时存 key 和 value

---

总结

• 数据结构：哈希表 + 双向链表 + 伪头尾节点；
• 哈希表：key → 节点，用于 $O(1)$ 定位；
• 双向链表：维护使用顺序，头部是最近使用，尾部是最久未使用；
• get：命中则移到头部；
• put：存在则更新 + 移到头部；不存在则新建 + 加到头部，超容量则删尾节点（同步删哈希表）；
• 关键记忆：「查得快用哈希，排得快用双向链表，边界清爽用哑节点」。

相关题目

• LC 460. LFU 缓存（更复杂的缓存淘汰策略）
• LC 剑指 Offer 35. 复杂链表的复制（双向链表设计）