数组与哈希中等2 种解法
#146LRU 缓存
实现固定容量的最近最少使用缓存，使 get 与 put 平均 O(1)。
#设计#哈希表#双向链表#LinkedHashMap
原题
请你设计并实现一个满足 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 <= 30000 <= key <= 100000 <= value <= 105- 最多调用
2 * 105次get和put
解题主线
- 哈希表提供按 key 定位，双向链表提供 O(1) 删除、移到最新端和淘汰最旧端。
- LinkedHashMap 的 accessOrder=true 已内置访问顺序，可通过 removeEldestEntry 自动淘汰。
解法 1：LinkedHashMap 访问顺序
启用 access-order，让 get/put 自动把条目移到最新端，并由钩子淘汰最旧项。
-
时间复杂度： get/put 平均 O(1)
-
空间复杂度： O(capacity)
import java.util.LinkedHashMap;
import java.util.Map;
final class LRUCache extends LinkedHashMap<Integer, Integer> {
private final int capacity;
LRUCache(int capacity) {
super(Math.max(1, capacity), 0.75f, true);
this.capacity = capacity;
}
public int get(int key) {
// access-order 模式下，命中的读取会自动把条目移到最新端
return getOrDefault(key, -1);
}
public void put(int key, int value) {
// 新增和更新都会刷新访问顺序
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
// 插入完成后容量超限时，由钩子淘汰最久未访问条目
return size() > capacity;
}
}实现提示
- 修复旧版未插入新键且淘汰判断时机错误的问题。
解法 2：哈希表 + 双向链表
链表头侧表示最近使用、尾侧表示最久未使用；所有节点移动均通过摘除和头插完成。
-
时间复杂度： get/put 平均 O(1)
-
空间复杂度： O(capacity)
import java.util.HashMap;
import java.util.Map;
final class LRUCache {
private static final class Node {
int key;
int value;
Node previous;
Node next;
Node() {}
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final Map<Integer, Node> nodes = new HashMap<>();
private final Node head = new Node();
private final Node tail = new Node();
LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.previous = head;
}
public int get(int key) {
Node node = nodes.get(key);
if (node == null) return -1;
// 命中即算一次访问，节点需移到最近使用端
moveToFront(node);
return node.value;
}
public void put(int key, int value) {
Node existing = nodes.get(key);
if (existing != null) {
existing.value = value;
// 更新已有键时也要刷新其新旧顺序
moveToFront(existing);
return;
}
Node added = new Node(key, value);
nodes.put(key, added);
addFirst(added);
if (nodes.size() > capacity) {
// 尾部前驱始终是最久未使用节点，淘汰时链表与 Map 必须同步
Node evicted = removeLast();
nodes.remove(evicted.key);
}
}
private void moveToFront(Node node) {
remove(node);
addFirst(node);
}
private void addFirst(Node node) {
// 头尾哨兵消除空链表和边界节点的特殊分支
node.previous = head;
node.next = head.next;
head.next.previous = node;
head.next = node;
}
private void remove(Node node) {
node.previous.next = node.next;
node.next.previous = node.previous;
}
private Node removeLast() {
Node last = tail.previous;
remove(last);
return last;
}
}实现提示
- 修复节点判空条件，并确保容量超限时链表与 Map 同步淘汰。
边界与易错点
- 旧自定义链表版把 cache != null 误写成节点存在判断，首次 put 就会对 null 节点解引用。
- 旧 LinkedHashMap 版缺少正常插入，并把淘汰条件写成 size > capacity，导致缓存长期为空。
- 更新已有 key 也算访问，必须移动到最近使用端；淘汰后要同步删除哈希映射。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
medium/Q146_II_LRUCache.javamedium/Q146_LRUCache.java