问题链接

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

示例：

输入
[“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

问题解答

要解决LRU（最近最少使用）缓存问题，我们需要设计一个数据结构，支持在O(1)平均时间复杂度内完成get和put操作。核心思路是结合哈希表（快速查找）和双向链表（维护使用顺序）。

解题思路

数据结构选择：
- 哈希表（HashMap）：存储键到双向链表节点的映射，实现O(1)时间复杂度的查找。
- 双向链表：维护节点的使用顺序，最近使用的节点放在链表头部，最久未使用的节点放在尾部，支持O(1)时间复杂度的插入、删除和移动操作。
- 虚拟头节点和虚拟尾节点：简化边界处理（如插入第一个节点或删除最后一个节点时无需判断null）。
核心操作：
- get(key)：若键存在，将对应节点移到链表头部（标记为最近使用）并返回值；否则返回-1。
- put(key, value)：若键存在，更新值并将节点移到头部；若键不存在，创建新节点插入头部，若容量超限，删除链表尾部节点（最久未使用）并从哈希表中移除对应键。

代码实现

import java.util.HashMap;
import java.util.Map;class LRUCache {// 双向链表节点static class Node {int key;int value;Node prev;Node next;public Node(int key, int value) {this.key = key;this.value = value;}}private final Map<Integer, Node> cache; // 哈希表：key -> 节点private final Node head; // 虚拟头节点private final Node tail; // 虚拟尾节点private final int capacity; // 缓存容量public LRUCache(int capacity) {this.capacity = capacity;cache = new HashMap<>(capacity);// 初始化虚拟节点并连接head = new Node(-1, -1);tail = new Node(-1, -1);head.next = tail;tail.prev = head;}public int get(int key) {if (!cache.containsKey(key)) {return -1; // 键不存在，返回-1}Node node = cache.get(key);moveToHead(node); // 访问后移到头部（最近使用）return node.value;}public void put(int key, int value) {if (cache.containsKey(key)) {// 键存在，更新值并移到头部Node node = cache.get(key);node.value = value;moveToHead(node);} else {// 键不存在，创建新节点Node newNode = new Node(key, value);cache.put(key, newNode);addToHead(newNode); // 插入头部// 若容量超限，删除尾部节点（最久未使用）if (cache.size() > capacity) {Node tailNode = removeTail();cache.remove(tailNode.key);}}}// 将节点移到头部（先删除再插入头部）private void moveToHead(Node node) {removeNode(node);addToHead(node);}// 从链表中移除节点private void removeNode(Node node) {node.prev.next = node.next;node.next.prev = node.prev;}// 将节点插入到头部（虚拟头节点之后）private void addToHead(Node node) {node.next = head.next;node.prev = head;head.next.prev = node;head.next = node;}// 移除尾部节点（虚拟尾节点之前的节点）并返回private Node removeTail() {Node res = tail.prev;removeNode(res);return res;}
}