三种方法手撕 LRU 缓存淘汰算法
LRU 介绍
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。
面试中常考的题目，运用你所掌握的数据结构，自己设计手写LRU算法。
相关题目可参考LeetCode146题
方法一：使用LinkedHashMap实现
在Java中，其实LinkedHashMap已经实现了LRU缓存淘汰算法，需要在构造函数第三个参数传入true，表示按照时间顺序访问。可以直接继承LinkedHashMap来实现。
但是LinkedHashMap会自动扩容，如果想实现限制容量删除队列顶端元素，需要重写removeEldestEntry()方法，当map里面的元素个数大于了缓存最大容量，删除链表的顶端元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
private int capacity;
LRULinkedHashMap(int capacity) {
super(capacity, 0.75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
}
|
方法二： 使用LinkedList+HashMap实现
也可以使用LinkedList和HashMap实现，但时间复杂度较高。使用HashMap可以通过O(1)时间拿到元素，但是无法在O(1)时间定位它在链表中的位置，在LinkedList里访问元素仍然是顺序遍历，所以删除元素的时间复杂度仍然是O(n)。并不是高效的LRU算法。
因为从HashMap中删除元素需要Key，所以这里在链表中存放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
| public class LRUCacheBeta<K, V> {
int capacity;
Map<K, V> map;
LinkedList<K> list;
public LRUCacheBeta(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>();
this.list = new LinkedList<>();
}
public void put(K key, V value) {
V v = map.get(key);
if (v != null) {
list.remove(key);
list.addLast(key);
map.put(key, value);
return;
}
if (list.size() < capacity) {
list.addLast(key);
map.put(key, value);
} else {
K firstKey = list.removeFirst();
map.remove(firstKey);
list.addLast(key);
map.put(key, value);
}
}
public V get(K key) {
V v = map.get(key);
if (v != null) {
list.remove(key);
list.addLast(key);
return v;
}
return null;
}
}
|
方法三：使用双向链表结构+HashMap实现
在方法二中，删除操作的时间复杂度仍是O(n)，那么如何使其复杂度降为O(1)？
我们可以自定义双向链表的结构，这里定义了内部类Node，存放K-V以及前后指针。这样我们通过hashmap找到对应Node，然后根据其前驱节点进行指针的操作，就可以实现复杂度O(1)的删除操作。
同样因为访问HashMap需要key，所以定义Node节点存放了K和V，而不是只存放V。保存队列的头节点和尾节点。
在代码中，我们通过调整指针，定义了三个方法，分别是添加元素到队尾，将队列中元素移动到队尾，删除队列头节点并返回，因为是双向链表，特别注意指针变换的顺序以及不要遗漏前驱和后继指针。
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
| public class LRUCache<K, V> {
private int size;
private HashMap<K, Node> map;
private Node head;
private Node tail;
LRUCache(int size) {
this.size = size;
map = new HashMap<>();
}
public void put(K key, V value) {
Node node = map.get(key);
if (node != null) {
node.v = value;
moveNodeToTail(node);
} else {
Node newNode = new Node(key, value);
if (map.size() == size) {
Node delHead = removeHead();
map.remove(delHead.k);
}
addLast(newNode);
map.put(key, newNode);
}
}
public V get(K key) {
Node node = map.get(key);
if (node != null) {
moveNodeToTail(node);
return node.v;
}
return null;
}
public void addLast(Node newNode) {
if (newNode == null) {
return;
}
if (head == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
newNode.pre = tail;
tail = newNode;
}
}
public void moveNodeToTail(Node node) {
if (tail == node) {
return;
}
if (head == node) {
head = node.next;
head.pre = null;
} else {
node.pre.next = node.next;
node.next.pre = node.pre;
}
node.pre = tail;
node.next = null;
tail.next = node;
tail = node;
}
public Node removeHead() {
if (head == null) {
return null;
}
Node res = head;
if (head == tail) {
head = null;
tail = null;
} else {
head = res.next;
head.pre = null;
res.next = null;
}
return res;
}
class Node {
K k;
V v;
Node pre;
Node next;
Node(K k, V v) {
this.k = k;
this.v = v;
}
}
}
|
文章引用转载自：
作者：icecrea
链接：https://leetcode-cn.com/problems/lru-cache/solution/san-chong-fang-fa-dai-ni-shou-si-lrusuan-fa-javaba/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。