LRU与LFU缓存替换策略
LRU（Least Recently Used，最少最近使用）和 LFU（Least Frequently Used，最不经常使用）是两种常用的缓存替换策略，用于决定缓存中哪些项应该被淘汰。它们的实现和应用场景非常广泛，特别是在内存管理、数据库缓存和操作系统中。
LRU (Least Recently Used) 最少最近使用
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)的平均时间复杂度运行。}
思路：
每次访问缓存时，将该缓存项标记为“最近使用”。
当缓存满时，淘汰最久未被访问的缓存项。
实现方法：
LRU 可以通过 双向链表 和 哈希表 来实现：
哈希表 用于快速访问缓存项。
双向链表 用于维护缓存项的使用顺序，最近访问的项放在链表头，最久未访问的项放在链表尾。
LRU 实现步骤：
哈希表：存储缓存的键值对，键是缓存的键，值是缓存项（值和最近使用的顺序）。
双向链表：存储缓存项的顺序，最近访问的缓存项放在头部，最久未访问的放在尾部。
插入和删除：每次访问缓存项时，将该项移动到链表头；如果缓存满了，移除链表尾部的项。
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
| import java.util.*;
class LRUCache {
private int capacity;
private Map<Integer, Integer> cache;
private LinkedHashMap<Integer, Long> accessOrder;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
this.accessOrder = new LinkedHashMap<>(capacity, 0.75f, true);
}
public int get(int key) {
if (!cache.containsKey(key)) {
return -1;
}
accessOrder.put(key, System.nanoTime());
return cache.get(key);
}
public void put(int key, int value) {
if (cache.size() >= capacity) {
long leastUsedTime = Long.MAX_VALUE;
int keyToRemove = -1;
for (Map.Entry<Integer, Long> entry : accessOrder.entrySet()) {
if (entry.getValue() < leastUsedTime) {
leastUsedTime = entry.getValue();
keyToRemove = entry.getKey();
}
}
cache.remove(keyToRemove);
accessOrder.remove(keyToRemove);
}
cache.put(key, value);
accessOrder.put(key, System.nanoTime());
}
}}
|
但这么写 过不了力扣......
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
| class LRUCache {
private static class Node {
int key, value;
Node prev, next;
Node(int k, int v) {
key = k;
value = v;
}
}
private final int capacity;
private final Node dummy = new Node(0, 0);
private final Map<Integer, Node> keyToNode = new HashMap<>();
public LRUCache(int capacity) {
this.capacity = capacity;
dummy.prev = dummy;
dummy.next = dummy;
}
public int get(int key) {
Node node = getNode(key);
return node != null ? node.value : -1;
}
public void put(int key, int value) {
Node node = getNode(key);
if (node != null) {
node.value = value;
return;
}
node = new Node(key, value);
keyToNode.put(key, node);
pushFront(node);
if (keyToNode.size() > capacity) {
Node backNode = dummy.prev;
keyToNode.remove(backNode.key);
remove(backNode);
}
}
private Node getNode(int key) {
if (!keyToNode.containsKey(key)) return null;
Node node = keyToNode.get(key);
remove(node);
pushFront(node);
return node;
}
private void remove(Node x) {
x.prev.next = x.next;
x.next.prev = x.prev;
}
private void pushFront(Node x) {
x.prev = dummy;
x.next = dummy.next;
x.prev.next = x;
x.next.prev = x;
}
}}
|
LFU (Least Frequently Used) 最不经常使用
LFU 策略用于淘汰访问频率最低的缓存项。即：每次访问缓存时，缓存项的访问次数增加。缓存满时，淘汰访问次数最少的缓存项。
思路：
每个缓存项都有一个访问频率：当访问缓存时，增加该项的频率。
淘汰策略：当缓存满时，淘汰频率最低的缓存项。若频率相同，则淘汰最早添加的缓存项。
实现方法：
LFU 通常使用 哈希表 和 最小堆（或 哈希表+双向链表）来实现。
哈希表 用于存储缓存的键值对。
频率表：哈希表将缓存项的访问次数作为键，缓存项列表作为值（即频率与缓存项的映射关系）。
最小堆：或者使用优先队列来管理访问频率，以便快速找到访问次数最少的缓存项。
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
| import java.util.*;
class LFUCache {
private int capacity;
private Map<Integer, Integer> values;
private Map<Integer, Integer> frequencies;
private Map<Integer, LinkedHashSet<Integer>> freqList;
private int minFreq;
public LFUCache(int capacity) {
this.capacity = capacity;
this.values = new HashMap<>();
this.frequencies = new HashMap<>();
this.freqList = new HashMap<>();
this.minFreq = -1;
}
public int get(int key) {
if (!values.containsKey(key)) {
return -1;
}
int freq = frequencies.get(key);
frequencies.put(key, freq + 1);
freqList.get(freq).remove(key);
if (freqList.get(freq).isEmpty()) {
if (minFreq == freq) {
minFreq++;
}
freqList.remove(freq);
}
freqList.putIfAbsent(freq + 1, new LinkedHashSet<>());
freqList.get(freq + 1).add(key);
return values.get(key);
}
public void put(int key, int value) {
if (capacity <= 0) return;
if (values.containsKey(key)) {
values.put(key, value);
get(key);
return;
}
if (values.size() >= capacity) {
int evictKey = freqList.get(minFreq).iterator().next();
freqList.get(minFreq).remove(evictKey);
if (freqList.get(minFreq).isEmpty()) {
freqList.remove(minFreq);
}
values.remove(evictKey);
frequencies.remove(evictKey);
}
values.put(key, value);
frequencies.put(key, 1);
minFreq = 1;
freqList.putIfAbsent(1, new LinkedHashSet<>());
freqList.get(1).add(key);
}
}}
|
主要思路：
频率管理：用一个哈希表 freqToDummy 存储每个访问频率对应的链表，链表的头部代表最近访问的节点，尾部代表最久未访问的节点。
双向链表：为每个访问频率维护一个双向链表，这样可以高效地管理节点的顺序，并能在常数时间内删除最不常使用的节点。
最小频率：minFreq 变量用于记录当前缓存中的最小访问频率。每当访问一个节点时，如果该节点的访问频率变化，并且该频率链表变为空，我们需要更新 minFreq。
核心操作：
get 操作：查找并返回缓存中 key 对应的值，同时将该节点的访问频率加 1，并将其移动到新的频率链表中。
put 操作：如果缓存已满，先移除访问频率最少的节点。然后将新节点插入到频率为 1 的链表中，并设置 minFreq 为 1。
节点的移动：每次访问或插入时，节点会根据其访问频率被移动到对应的链表头部，从而保证频率最低的节点最先被淘汰。
性能分析：
时间复杂度：每个操作（get、put、remove、pushFront）都可以在 O(1) 时间内完成，因为链表操作和哈希表操作的时间复杂度是 O(1)。
空间复杂度：空间复杂度是 O(capacity)，因为我们只在缓存中存储最多 capacity 个节点。
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
| class LFUCache {
private static class Node {
int key, value, freq = 1;
Node prev, next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final Map<Integer, Node> keyToNode = new HashMap<>();
private final Map<Integer, Node> freqToDummy = new HashMap<>();
private int minFreq;
public LFUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
Node node = getNode(key);
return node != null ? node.value : -1;
}
public void put(int key, int value) {
Node node = getNode(key);
if (node != null) {
node.value = value;
return;
}
if (keyToNode.size() == capacity) {
Node dummy = freqToDummy.get(minFreq);
Node backNode = dummy.prev;
keyToNode.remove(backNode.key);
remove(backNode);
if (dummy.prev == dummy) {
freqToDummy.remove(minFreq);
}
}
node = new Node(key, value);
keyToNode.put(key, node);
pushFront(1, node);
minFreq = 1;
}
private Node getNode(int key) {
if (!keyToNode.containsKey(key)) {
return null;
}
Node node = keyToNode.get(key);
remove(node);
Node dummy = freqToDummy.get(node.freq);
if (dummy.prev == dummy) {
freqToDummy.remove(node.freq);
if (minFreq == node.freq) {
minFreq++;
}
}
pushFront(++node.freq, node);
return node;
}
private Node newList() {
Node dummy = new Node(0, 0);
dummy.prev = dummy;
dummy.next = dummy;
return dummy;
}
private void pushFront(int freq, Node x) {
Node dummy = freqToDummy.computeIfAbsent(freq, k -> newList());
x.prev = dummy;
x.next = dummy.next;
x.prev.next = x;
x.next.prev = x;
}
private void remove(Node x) {
x.prev.next = x.next;
x.next.prev = x.prev;
}
}}
|