LRU缓存的实现
面试时有可能会被问到LRU的具体实现。在 Python 语言中，有一种结合了哈希表与双向链表的数据结构 OrderedDict，只需要短短的几行代码就可以完成本题。在 Java 语言中，同样有类似的数据结构 LinkedHashMap。但这些做法都不会符合面试官的要求，因此我们需要了解LRU底层的原理。
LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。
这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1) 的时间内完成 get 或者 put 操作。具体的方法如下：
对于 get 操作，首先判断 key 是否存在：
如果 key 不存在，则返回 −1；
如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
对于 put 操作，首先判断 key 是否存在：
如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；
如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。
上述各项操作中，访问哈希表的时间复杂度为 O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。而将一个节点移到双向链表的头部，可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作，都可以在 O(1) 时间内完成。
下面给出Java代码的实现：
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
| public class LRUCache {
class Node {
public Node prev;
public Node next;
public int key;
public int value;
public Node() {
this.prev = null;
this.next = null;
this.key = 0;
this.value = 0;
}
public Node(int key, int value) {
this.prev = null;
this.next = null;
this.key = key;
this.value = value;
}
public Node(Node prev, Node next, int key, int value) {
this.prev = prev;
this.next = next;
this.key = key;
this.value = value;
}
}
private int capacity;
private Map<Integer, Node> map;
private Node dummyHead;
private Node dummyTail;
private int size;
public LRUCache(int capacity) {
this.capacity = capacity;
this.size = 0;
map = new HashMap<Integer, Node>();
dummyHead = new Node();
dummyTail = new Node();
dummyHead.next = dummyTail;
dummyTail.prev = dummyHead;
}
public int get(int key) {
Node node = map.get(key);
if (node == null) return -1;
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = map.get(key);
if (node == null) {
size++;
map.put(key, addToHead(new Node(key, value)));
} else {
node.value = value;
moveToHead(node);
}
if (size > capacity) {
deleteFromTail();
}
}
private void deleteNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private Node addToHead(Node node) {
node.prev = dummyHead;
node.next = dummyHead.next;
dummyHead.next.prev = node;
dummyHead.next = node;
return node;
}
private void moveToHead(Node node) {
deleteNode(node);
addToHead(node);
}
private void deleteFromTail() {
if (size > 0) {
int key = dummyTail.prev.key;
deleteNode(dummyTail.prev);
map.remove(key);
size--;
}
}
}
|
