友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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 <= 105 -
最多调用
2 * 105次get和put
思路分析
使用双向链表实现时，使用两个"空节点" head 和 tail，可以有效减少空值判断，真是精巧。想起来上大学时，老师讲课提到这么一句。没想到竟然是如此实现。
LinkedHashMap 的实现也有不少的秘密可以探索。
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
/**
* Runtime: 14 ms, faster than 90.57% of Java online submissions for LRU Cache.
*
* Memory Usage: 50.8 MB, less than 96.93% of Java online submissions for LRU Cache.
*
* Copy from: https://leetcode-cn.com/problems/lru-cache/solution/lru-huan-cun-ji-zhi-by-leetcode/[LRU 缓存机制 - LRU缓存机制 - 力扣（LeetCode）]
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-26 10:49
*/
class LRUCache {
private Map<Integer, DLinkedNode> data;
private int capacity;
private int size;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
this.data = new HashMap<>();
this.head = new DLinkedNode();
this.tail = new DLinkedNode();
this.head.next = this.tail;
this.tail.prev = this.head;
}
public int get(int key) {
DLinkedNode node = data.get(key);
if (Objects.isNull(node)) {
return -1;
}
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = data.get(key);
if (Objects.isNull(node)) {
DLinkedNode newNode = new DLinkedNode();
newNode.key = key;
newNode.value = value;
data.put(key, newNode);
addNode(newNode);
++size;
if (size > capacity) {
DLinkedNode tail = popTail();
data.remove(tail.key);
--size;
}
} else {
node.value = value;
moveToHead(node);
}
}
private void addNode(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(DLinkedNode node) {
DLinkedNode prev = node.prev;
DLinkedNode next = node.next;
prev.next = next;
next.prev = prev;
}
private void moveToHead(DLinkedNode node) {
removeNode(node);
addNode(node);
}
private DLinkedNode popTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
private class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
}
}
/**
* Runtime: 22 ms, faster than 43.05% of Java online submissions for LRU Cache.
*
* Memory Usage: 58 MB, less than 51.53% of Java online submissions for LRU Cache.
*/
class LRUCacheLinkedHashMap {
private LinkedHashMap<Integer, Integer> data;
public LRUCacheLinkedHashMap(int capacity) {
data = new LinkedHashMap<Integer, Integer>(capacity, 0.75F, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return this.size() > capacity;
}
};
}
public int get(int key) {
return data.getOrDefault(key, -1);
}
public void put(int key, int value) {
data.put(key, value);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/**
* 最近最少使用缓存
*
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-01 23:28:56
*/
class LRUCache {
private Map<Integer, Node<Integer>> data;
private Node<Integer> head;
private Node<Integer> tail;
private int capacity;
public LRUCache(int capacity) {
head = new Node<>();
tail = new Node<>();
head.next = tail;
tail.prev = head;
data = new HashMap<>(capacity);
this.capacity = capacity;
}
public int get(int key) {
Node<Integer> node = data.getOrDefault(key, null);
if (node == null) {
return -1;
}
siftUp(node);
return node.item;
}
public void put(int key, int value) {
Node<Integer> node;
if (data.containsKey(key)) {
node = data.get(key);
node.item = value;
siftUp(node);
} else {
node = new Node<>(key, value);
data.put(key, node);
addNode(node);
}
if (data.size() > capacity) {
Node<Integer> removing = tail.prev;
removeNode(removing);
data.remove(removing.key);
}
}
private void siftUp(Node<Integer> node) {
// 如果是第一个节点，则不需要处理
if (node.prev == head) {
return;
}
// 将当前访问节点放在链表最前面
// 先删除
removeNode(node);
// 再添加
addNode(node);
}
private void addNode(Node<Integer> node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
private void removeNode(Node<Integer> node) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.prev = null;
node.next = null;
}
static class Node<E> {
E key;
E item;
Node<E> next;
Node<E> prev;
Node() {
}
Node(E key, E element) {
this.key = key;
this.item = element;
this.next = next;
this.prev = prev;
}
}
}