警告
本文最后更新于 2022-09-09，文中内容可能已过时。
LFU (Least Frequently Used)
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
| class Node {
int key, value;
Node prev, next;
public Node (int key, int value) {
this.key = key;
this.value = value;
}
}
class BiLinkedList {
final Node head, tail;
int length;
public BiLinkedList() {
this.head = new Node(0, 0);
this.tail = new Node(0, 0);
this.length = 0;
head.next = tail;
tail.prev = head;
}
public void addLast(Node node) {
node.prev = tail.prev;
node.next = tail;
tail.prev.next = node;
tail.prev = node;
length++;
}
public void remove(Node node) {
if (node.prev == null || node.next == null) {
return;
}
node.prev.next = node.next;
node.next.prev = node.prev;
length--;
}
public void removeFirst() {
if (length == 0) {
return;
}
head.next.next.prev = head;
head.next = head.next.next;
length--;
}
}
class LFUCache {
HashMap<Integer, Node> keyToNode;
HashMap<Integer, Integer> keyToFreq;
HashMap<Integer, BiLinkedList> freqToNodes;
final int capacity;
int length;
int minFreq;
public LFUCache(int capacity) {
this.keyToNode = new HashMap<>();
this.keyToFreq = new HashMap<>();
this.freqToNodes = new HashMap<>();
this.capacity = capacity;
this.length = 0;
this.minFreq = -1;
}
public int get(int key) {
if (keyToNode.containsKey(key)) {
Node node = keyToNode.get(key);
// 更新频率
int freq = keyToFreq.get(key);
keyToFreq.put(key, freq + 1);
// 删除结点
freqToNodes.get(freq).remove(node);
// 添加结点
if (freqToNodes.containsKey(freq + 1)) {
freqToNodes.get(freq + 1).addLast(node);
} else {
BiLinkedList list = new BiLinkedList();
list.addLast(node);
freqToNodes.put(freq + 1, list);
}
// 更新 minFreq
if (freq == minFreq) {
while (freqToNodes.get(minFreq).length == 0) {
minFreq++;
}
}
return node.value;
} else {
return -1;
}
}
public void put(int key, int value) {
if (keyToNode.containsKey(key)) {
// 更新值
Node node = keyToNode.get(key);
node.value = value;
// 更新频率
int freq = keyToFreq.get(key);
keyToFreq.put(key, freq + 1);
// 删除结点
freqToNodes.get(freq).remove(node);
// 添加结点
if (freqToNodes.containsKey(freq + 1)) {
freqToNodes.get(freq + 1).addLast(node);
} else {
BiLinkedList list = new BiLinkedList();
list.addLast(node);
freqToNodes.put(freq + 1, list);
}
// 更新 minFreq
if (freq == minFreq) {
while (freqToNodes.get(minFreq).length == 0) {
minFreq++;
}
}
} else {
if (capacity == 0) {
return;
}
if (length == capacity) {
int rkey = freqToNodes.get(minFreq).head.next.key;
freqToNodes.get(minFreq).removeFirst();
keyToNode.remove(rkey);
keyToFreq.remove(rkey);
length--;
}
Node node = new Node(key, value);
keyToNode.put(key, node);
keyToFreq.put(key, 1);
if (freqToNodes.containsKey(1)) {
freqToNodes.get(1).addLast(node);
} else {
BiLinkedList list = new BiLinkedList();
list.addLast(node);
freqToNodes.put(1, list);
}
minFreq = 1;
length++;
}
}
}
|