当前位置：首页 > news >正文

【LeetCode 热题 100】146. LRU 缓存——哈希表+双向链表

news 2025/7/12 8:27:38

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

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(1)
- 空间复杂度：O(capacity)

整体思路

这段代码旨在实现一个 LRU (Least Recently Used) 缓存。LRU 缓存是一种遵循特定淘汰策略的固定容量缓存：当缓存已满且需要添加新元素时，它会移除最近最少被使用的那个元素。

为了高效地实现这一功能，该算法巧妙地结合了两种数据结构：

哈希表 (HashMap):
- 代码中是 private final Map<Integer, Node> keyToNode。
- 作用: 提供 O(1) 平均时间复杂度的快速查找。通过 key，我们可以立即找到对应的链表节点 Node。这是实现高效 get 和 put 的关键。
双向链表 (Doubly Linked List):
- 代码中是通过 Node 类和一系列指针操作（remove, pushFront）实现的。
- 作用: 维护数据的“最近使用”顺序。所有节点按照其被访问的先后顺序排列。
  - 队首 (MRU - Most Recently Used): 链表的头部（紧跟在 dummy 节点之后）存放的是最近被访问（get 或 put）的元素。
  - 队尾 (LRU - Least Recently Used): 链表的尾部（dummy 节点的前一个节点）存放的是最久未被访问的元素。
- 双向链表的优势在于，只要我们有了一个节点的引用（可以从哈希表中O(1)获得），我们就可以在 O(1) 的时间内将该节点从链表的任意位置移除，或移动到头部。

核心操作逻辑:

get(key): 当一个元素被访问时，它就成为了“最近使用”的。
1. 通过哈希表快速找到该 key 对应的节点。
2. 如果找到，就将该节点从其当前位置移动到双向链表的头部。
3. 返回节点的值。如果未找到，返回 -1。
put(key, value): 当插入或更新一个元素时，它也成为了“最近使用”的。
1. 检查是否存在: 通过哈希表检查 key 是否已存在。
2. 如果存在 (更新): 更新该节点的值，并将其移动到链表头部。
3. 如果不存在 (插入):
  a. 创建一个新节点。
  b. 将新节点插入到链表的头部。
  c. 在哈希表中添加 key到新节点的映射。
  d. 检查容量: 如果此时缓存的大小超过了 capacity，就需要淘汰最久未使用的元素。
  e. 淘汰 (Eviction): 移除链表的尾部节点，并同时从哈希表中移除该节点的 key。

通过这两种数据结构的协同工作，LRU 缓存得以在平均 O(1) 的时间内完成所有核心操作。

完整代码

class LRUCache {// 内部类，定义双向链表的节点结构private static class Node {int key; // 存储键，便于在淘汰时从哈希表中删除int val; // 存储值Node prev; // 指向前一个节点Node next; // 指向后一个节点Node(int key, int val) {this.key = key;this.val = val;}}private final int capacity; // 缓存的最大容量// dummy 是一个哨兵节点，用于简化链表头尾的操作，避免空指针判断。// dummy.next 指向真正的头节点 (MRU)，dummy.prev 指向真正的尾节点 (LRU)。private final Node dummy = new Node(0, 0);// 哈希表，实现 O(1) 的 key -> Node 查找private final Map<Integer, Node> keyToNode = new HashMap<>();public LRUCache(int capacity) {this.capacity = capacity;// 初始化双向链表为一个空的循环链表，dummy 自己指向自己。dummy.prev = dummy;dummy.next = dummy;}public int get(int key) {// 调用辅助函数 getNode 获取节点。// getNode 会自动处理“将节点移动到头部”的逻辑。Node node = getNode(key);// 如果节点不存在，返回 -1；否则返回节点的值。return node == null ? -1 : node.val;}public void put(int key, int value) {// 尝试获取节点，如果存在，getNode 会将其移动到头部。Node node = getNode(key);if (node != null) {// Case 1: Key 已存在，更新值即可。node.val = value;return;}// Case 2: Key 不存在，需要插入新节点。node = new Node(key, value);// a. 将新节点添加到链表头部 (MRU)pushFront(node);// b. 在哈希表中建立 key 到新节点的映射keyToNode.put(key, node);// c. 检查是否超出容量if (keyToNode.size() > capacity) {// d. 淘汰最久未使用的元素 (链表尾部)Node lruNode = dummy.prev;// 从哈希表中移除keyToNode.remove(lruNode.key);// 从链表中移除remove(lruNode);}}/*** 辅助函数：根据 key 获取节点，并将其标记为最近使用（移动到链表头部）。*/private Node getNode(int key) {if (!keyToNode.containsKey(key)) {return null; // Key 不存在}// 从哈希表中获取节点引用Node node = keyToNode.get(key);// 将节点从当前位置移除remove(node);// 将节点添加到链表头部pushFront(node);return node;}/*** 辅助函数：从双向链表中移除一个节点。*/private void remove(Node node) {node.prev.next = node.next;node.next.prev = node.prev;}/*** 辅助函数：将一个节点添加到双向链表的头部。*/private void pushFront(Node node) {node.next = dummy.next;node.next.prev = node;dummy.next = node;node.prev = dummy;}
}

时空复杂度

时间复杂度：O(1)

get(int key):
- 该操作主要调用 getNode。
- 在 getNode 中，keyToNode.containsKey 和 keyToNode.get 都是哈希表操作，平均时间复杂度为 O(1)。
- remove(node) 和 pushFront(node) 是双向链表的指针操作，时间复杂度为 O(1)。
- 因此，get 方法的平均时间复杂度是 O(1)。
put(int key, int value):
- 该操作首先调用 getNode，耗时 O(1)。
- 更新情况: 赋值操作是 O(1)。
- 插入情况: new Node, pushFront, keyToNode.put 都是 O(1) 的平均操作。
- 淘汰情况: keyToNode.remove 和 remove(lruNode) 也都是 O(1) 的平均操作。
- 因此，put 方法的平均时间复杂度是 O(1)。

注意：以上分析基于哈希表的平均情况。在极罕见的哈希冲突最坏情况下，哈希表操作可能退化到 O(N)，但通常不作为主要考量。

空间复杂度：O(capacity)

主要存储开销：算法需要存储数据，其存储量与缓存的容量 capacity 直接相关。
哈希表 keyToNode: 在最坏情况下，哈希表会存储 capacity 个键值对。每个键是 Integer，每个值是 Node 的引用。空间复杂度为 O(capacity)。
双向链表: 双向链表最多会存储 capacity 个 Node 对象。每个 Node 对象包含 key, val, prev, next。空间复杂度也为 O(capacity)。