一、题目描述
运用你所掌握的数据结构，设计和实现一个 LRU（最近最少使用）缓存机制。它应该支持以下操作：
- 获取数据 get(key)：如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
- 写入数据 put(key, value) ：如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶：
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例：
1
2
3
4
5
6
7
8
9
10
11
| LRUCache cache = new LRUCache( 2 );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);
cache.put(3, 3);
cache.get(2);
cache.put(4, 4);
cache.get(1);
cache.get(3);
cache.get(4);
|
二、题解
LRU 是 Least Recently Used 的缩写，这种算法认为最近使用的数据是热门数据，下一次很大概率将会再次被使用。而最近很少被使用的数据，很大概率下一次不再用到。当缓存容量满的时候，优先淘汰最近很少使用的数据。
实现 LRU 缓存的常用方法是使用有界队列。实现 LRU 的关键是将所有最近使用的数据放在队列的开头。在每次插入之前，我们检查队列是否已满。如果队列已满，我们将删除其最后一个元素，并将新节点插入队列的开头。如果队列未满，我们只需将数据添加到队列的开头。
为了方便理解，我们借助前面的示例来演示一下上述的处理流程：
当我们想要删除节点或更新节点时，我们需要快速找到该节点在队列中的位置。因此，可以使用 HashMap 支持快速查找操作。在这种情况下，get 操作的时间复杂度为 O(1)。
由于我们还需要有效地删除队列中间的节点，因此需要一个双向链表。在两种情况下，我们需要删除队列中间的节点：
- 客户端指定需要删除一个节点。
- 节点已更新，需要将其删除并插入队列的开头。
通过使用双向链表，一旦我们通过 HashMap 定位了要删除的节点的位置，就可以在 O(1) 时间从队列中删除该节点。
当我们需要更新键的缓存时，我们首先使用 HashMap 定位相应的节点，更新值，然后从队列中删除该节点，并将该节点放置在 Doubly Linked List 的开头。
LRU 算法 Java 实现
下面我们先用 Java 来实现 LRU 缓存算法。
首先定义个双向链表的节点：
1
2
3
4
5
6
7
8
9
10
11
| class Node {
int key;
int value;
Node pre;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
|
每次执行操作时，我们都使用 HashMap 定位节点在队列中的位置，然后删除该节点并将其插入链表头。因此最好定义两个方法：
- remove(node)：从双向链表中删除指定 node 节点；
- setHead(node)：把指定 node 节点插入到双向链表表头。
定义 LRUCache 类
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
| public class LRUCache {
int capacity;
Map<Integer, Node> map = new HashMap<>();
Node head = null;
Node tail = null;
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
if (map.containsKey(key)) {
Node node = map.get(key);
remove(node);
setHead(node);
return node.value;
}
return -1;
}
public void remove(Node n) {
if (n.pre != null) {
n.pre.next = n.next;
} else {
head = n.next;
}
if (n.next != null) {
n.next.pre = n.pre;
} else {
tail = n.pre;
}
}
public void setHead(Node n) {
n.next = head;
n.pre = null;
if (head != null)
head.pre = n;
head = n;
if (tail == null)
tail = head;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node old = map.get(key);
old.value = value;
remove(old);
setHead(old);
} else {
Node created = new Node(key, value);
if (map.size() >= capacity) {
map.remove(tail.key);
remove(tail);
setHead(created);
} else {
setHead(created);
}
map.put(key, created);
}
}
}
|
定义 LRUCacheDemo 测试类
1
2
3
4
5
6
7
8
9
10
11
12
| public class LRUCacheDemo {
public static void main(String[] args) {
LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println("cache.get(1): " + cache.get(1));
cache.put(3, 3);
System.out.println("cache.get(2): " + cache.get(2));
System.out.println("cache.get(3): " + cache.get(3));
}
}
|
以上代码成功运行后，输出以下结果：
1
2
3
| cache.get(1): 1
cache.get(2): -1
cache.get(3): 3
|
三、参考资源
欢迎小伙伴们订阅前端全栈修仙之路，及时阅读 Angular、TypeScript、Node.js/Java和Spring技术栈最新文章。
