LFU实现详解
缓存的大小都是有限的，当缓存满时有新元素需要添加，就需要一种方式从缓存中删除一些元素，删除的策略就是缓存的淘汰算法。
LFU有个兄弟LRU，他们两都是常用的缓存淘汰算法。
LRU(Least Recently Used) 最近最少使用算法，它是根据时间维度来选择将要淘汰的元素，即删除掉最长时间没被访问的元素。
LFU(Least Frequently Used) 最近最不常用算法，它是根据频率维度来选择将要淘汰的元素，即删除访问频率最低的元素。如果两个元素的访问频率相同，则淘汰最久没被访问的元素。
也就是说LFU淘汰的时候会选择两个维度，先比较频率，选择访问频率最小的元素；如果频率相同，则按时间维度淘汰掉最久远的那个元素。
LRU的实现是一个哈希表加上一个双链表
而LFU则要复杂多了，需要用两个哈希表再加上N个双链表才能实现
我们先看看LFU的两个哈希表里面都存了什么
第一个哈希表是key-value的哈希表(以下简称kv哈希表)
这里的key就是输入的key，没什么特别的。关键是value，它的value不是一个简单的value，而是一个节点对象。
节点对象Node包含了key，value，以及频率，这个Node又会出现在第二个哈希表的value中。
至于为什么Node中又重复包含了key，因为某些情况下我们不是通过k-v哈希表拿到Node的，而是通过其他方式获得了Node，之后需要用Node中的key去k-v哈希表中做一些操作，所以Node中包含了一些冗余信息。
第二张哈希表，频率哈希表，这个就要复杂多了
这张哈希表中的key是频率，也就是元素被访问的频率(被访问了1次，被访问了两次等等)，它的value是一个双向链表
刚才说的Node对象，现在又出现了，这里的Node其实是双向链表中的一个节点。
第一张图中我们介绍了Node中包含了一个冗余的key，其实它还包含了一个冗余的频率值，因为某些情况下，我们需要通过Node中的频率值，去频率哈希表中做查找，所以也需要一个冗余的频率值。
下面我们将两个哈希表整合起来看看完整的结构:
k-v哈希表中key1指向一个Node，这个Node的频率为1，位于频率哈希表中key=1下面的双链表中(处于第一个节点)。
具体操作
下面我们来看看具体操作，get操作相对简单一些，我们就先说get操作吧。
get操作的具体逻辑大致是这样：
- 如果key不存在则返回-1
- 如果key存在，则返回对应的value，同时:
- 将元素的访问频率+1
- 将元素从访问频率
i的链表中移除，放到频率i+1的链表中
- 如果频率
i的链表为空，则从频率哈希表中移除这个链表
第一个很简单就不用说了，我们看下第二点的执行过程
假设某个元素的访问频率是3，现在又被访问了一次，那么就需要将这个元素移动到频率4的链表中。如果这个元素被移除后，频率3的那个链表变成空了(只剩下头结点和尾节点)就需要删除这个链表，同时删除对应的频率(也就是删除key=3)
put操作就要复杂多了，大致包括下面几种情况
- 如果key已经存在，修改对应的value，并将访问频率+1
- 将元素从访问频率
i的链表中移除，放到频率i+1的链表中
- 如果频率
i的链表为空，则从频率哈希表中移除这个链表
- 如果key不存在
- 缓存超过最大容量，则先删除访问频率最低的元素，再插入新元素
- 新元素的访问频率为1，如果频率哈希表中不存在对应的链表需要创建
- 缓存没有超过最大容量，则插入新元素
- 新元素的访问频率为1，如果频率哈希表中不存在对应的链表需要创建
我们在代码实现中还需要维护一个minFreq的变量，用来记录LFU缓存中频率最小的元素，在缓存满的时候，可以快速定位到最小频繁的链表，以达到 $O(1)$ 时间复杂度删除一个元素。
具体做法是:
- 更新/查找的时候，将元素频率+1，之后如果
minFreq不在频率哈希表中了，说明频率哈希表中已经没有元素了，那么minFreq需要+1，否则minFreq不变。
- 插入的时候，这个简单，因为新元素的频率都是1，所以只需要将minFreq改为1即可。
我们重点看下缓存超过最大容量时是怎么处理的
代码部分
代码部分比较长，我对代码加了很多注释，也做了一些简单的封装。
这里自定义了一个双向链表，增加了一些自定义的函数，就当是复习下双链表吧。
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
|
import java.util.HashMap;
import java.util.Map;
/**
* 自定义的LFU缓存类
*/
public class LFUCache {
/**
* 双链表中的链表节点对象
*/
protected static class Node{
//对应输入的key
private final int key;
//对应输入的value
private int value;
//被访问的频率
private int freq;
//指向前一个节点的指针
protected Node pre;
//指向后一个节点的指针
protected Node next;
public Node(int key, int value, int freq) {
this.key = key;
this.value = value;
this.freq = freq;
}
public Node(int key, int value, int freq, Node pre, Node next) {
this.key = key;
this.value = value;
this.freq = freq;
this.pre = null;
this.next = null;
}
public void updateValue(int value) {
this.value = value;
}
public void incrFreq() {
++this.freq;
}
public int getKey() {
return this.key;
}
public int getValue() {
return this.value;
}
public int getFreq() {
return this.freq;
}
public static final Node createEmptyNode() {
return new Node(-1,-1,-1,null,null);
}
}
/**
* 自定义的双向链表类
*/
protected static class LinkedList {
//双向链表的头结点
private final Node head;
//双向链表的尾节点
private final Node tail;
public LinkedList() {
this.head = Node.createEmptyNode();
this.tail = Node.createEmptyNode();
this.head.next = this.tail;
this.tail.pre = this.head;
}
/**
* 将指定的节点插入到链表的第一个位置
* @param node 将要插入的节点
*/
public void insertFirst(Node node) {
if(node==null) {
throw new IllegalArgumentException();
}
node.next = this.head.next;
this.head.next.pre = node;
node.pre = this.head;
this.head.next = node;
}
/**
* 从链表中删除指定的节点
* @param node 将要删除的节点
*/
public void deleteNode(Node node) {
if(node==null) {
throw new IllegalArgumentException();
}
node.pre.next = node.next;
node.next.pre = node.pre;
node.pre = null;
node.next = null;
}
/**
* 从链表中获取最后一个节点
* @return 双向链表中的最后一个节点，如果是空链表则返回None
*/
public Node getLastNode() {
if(this.head.next==this.tail) {
return Node.createEmptyNode();
}
return this.tail.pre;
}
/**
* 判断链表是否为空，除了head和tail没有其他节点即为空链表
* @return 链表不空返回True，否则返回False
*/
public boolean isEmpty() {
return this.head.next==this.tail;
}
}
//key->Node 这种结构的哈希表
private final Map<Integer,Node> keyMap = new HashMap<Integer,Node>();
//freq->LinkedList 这种结构的哈希表
private final Map<Integer,LinkedList> freqMap = new HashMap<Integer,LinkedList>();
//缓存的最大容量
private final int capacity;
//记录缓存中最低频率
private int minFreq = 0;
public LFUCache(int capacity) {
// if(capacity<=0) {
// throw new IllegalArgumentException();
// }
this.capacity = capacity;
}
/**
* 获取一个元素，如果key不存在则返回-1，否则返回对应的value，同时更新被访问元素的频率
* @param key 要查找的关键字
* @return 如果没找到则返回-1，否则返回对应的value
*/
public int get(int key) {
if(!this.keyMap.containsKey(key)) {
return -1;
}
Node node = this.keyMap.get(key);
this.increment(node);
return node.getValue();
}
/**
* 插入指定的key和value，如果key存在则更新value，同时更新频率，
* 如果key不存并且缓存满了，则删除频率最低的元素，并插入新元素。否则，直接插入新元素
* @param key 要插入的关键字
* @param value 要插入的值
*/
public void put(int key, int value) {
if(this.keyMap.containsKey(key)) {
Node node = this.keyMap.get(key);
node.updateValue(value);
this.increment(node);
}
else {
if(this.capacity==0) {
return;
}
if(this.keyMap.size()==this.capacity) {
this.remoteMinFreqNode();
}
Node node = new Node(key,value,1);
this.increment(node,true);
this.keyMap.put(key, node);
}
}
/**
* 更新节点的访问频率
* @param node 要更新的节点
*/
private void increment(Node node) {
increment(node,false);
}
/**
* 更新节点的访问频率
* @param node 要更新的节点
* @param isNewNode 是否是新节点，新插入的节点和非新插入节点更新逻辑不同
*/
private void increment(Node node,boolean isNewNode) {
if(isNewNode) {
this.minFreq = 1;
this.insertToLinkedList(node);
}
else {
this.deleteNode(node);
node.incrFreq();
this.insertToLinkedList(node);
if(!this.freqMap.containsKey(this.minFreq)) {
++this.minFreq;
}
}
}
/**
* 根据节点的频率，插入到对应的LinkedList中，如果LinkedList不存在则创建
* @param node 将要插入到LinkedList的节点
*/
private void insertToLinkedList(Node node) {
if(!this.freqMap.containsKey(node.getFreq())) {
this.freqMap.put(node.getFreq(), new LinkedList());
}
LinkedList linkedList = this.freqMap.get(node.getFreq());
linkedList.insertFirst(node);
}
/**
* 删除指定的节点，如果节点删除后，对应的双链表为空，则从__freqMap中删除这个链表
* @param node 将要删除的节点
*/
private void deleteNode(Node node) {
LinkedList linkedList = this.freqMap.get(node.getFreq());
linkedList.deleteNode(node);
if(linkedList.isEmpty()) {
this.freqMap.remove(node.getFreq());
}
}
/**
* 删除频率最低的元素，从freqMap和keyMap中都要删除这个节点，
* 如果节点删除后对应的链表为空，则要从__freqMap中删除这个链表
*/
private void remoteMinFreqNode() {
LinkedList linkedList = this.freqMap.get(this.minFreq);
Node node = linkedList.getLastNode();
linkedList.deleteNode(node);
this.keyMap.remove(node.getKey());
if(linkedList.isEmpty()) {
this.freqMap.remove(node.getFreq());
}
}
}
|
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
|
class Node(object):
"""
双链表中的链表节点对象
"""
def __init__(self,key=None,value=None,freq=0):
"""
Args:
key:对应输入的key
value:对应输入的value
freq:被访问的频率
pre:指向前一个节点的指针
next:指向后一个节点的指针
"""
self.key = key
self.value = value
self.freq = freq
self.pre = None
self.next = None
class LinkedList(object):
"""
自定义的双向链表
"""
def __init__(self):
"""
Args:
__head:双向链表的头结点
__tail:双向链表的尾节点
"""
self.__head = Node()
self.__tail = Node()
self.__head.next = self.__tail
self.__tail.pre = self.__head
def insertFirst(self,node):
"""
将指定的节点插入到链表的第一个位置
Args:
node:将要插入的节点
"""
node.next = self.__head.next
self.__head.next.pre = node
self.__head.next = node
node.pre = self.__head
def delete(self,node):
"""
从链表中删除指定的节点
Args:
node:将要删除的节点
"""
if self.__head.next==self.__tail:
return
node.pre.next = node.next
node.next.pre = node.pre
node.next = None
node.pre = None
def getLast(self):
"""
从链表中获取最后一个节点
Returns:
双向链表中的最后一个节点，如果是空链表则返回None
"""
if self.__head.next==self.__tail:
return None
return self.__tail.pre
def isEmpty(self):
"""
判断链表是否为空，除了head和tail没有其他节点即为空链表
Returns:
链表不空返回True，否则返回False
"""
return self.__head.next==self.__tail
class LFUCache(object):
"""
自定义的LFU缓存
"""
def __init__(self, capacity):
"""
Args:
__capacity:缓存的最大容量
__keyMap: key->Node 这种结构的字典
__freqMap:freq->LinkedList 这种结构的字典
__minFreq:记录缓存中最低频率
"""
self.__capacity = capacity
self.__keyMap = dict()
self.__freqMap = dict()
self.__minFreq = 0
def get(self, key):
"""
获取一个元素，如果key不存在则返回-1，否则返回对应的value
同时更新被访问元素的频率
Args:
key:要查找的关键字
Returns:
如果没找到则返回-1，否则返回对应的value
"""
if key not in self.__keyMap:
return -1
node = self.__keyMap[key]
self.__increment(node)
return node.value
def put(self, key, value):
"""
插入指定的key和value，如果key存在则更新value，同时更新频率
如果key不存并且缓存满了，则删除频率最低的元素，并插入新元素
否则，直接插入新元素
Args:
key:要插入的关键字
value:要插入的值
"""
if key in self.__keyMap:
node = self.__keyMap[key]
node.value = value
self.__increment(node)
else:
if self.__capacity==0:
return
if len(self.__keyMap)==self.__capacity:
self.__removeMinFreqElement()
node = Node(key,value,1)
self.__increment(node,True)
self.__keyMap[key] = node
def __increment(self,node,is_new_node=False):
"""
更新节点的访问频率
Args:
node:要更新的节点
is_new_node:是否是新节点，新插入的节点和非新插入节点更新逻辑不同
"""
if is_new_node:
self.__minFreq = 1
self.__setDefaultLinkedList(node)
else:
self.__deleteNode(node)
node.freq += 1
self.__setDefaultLinkedList(node)
if self.__minFreq not in self.__freqMap:
self.__minFreq += 1
def __setDefaultLinkedList(self,node):
"""
根据节点的频率，插入到对应的LinkedList中，如果LinkedList不存在则创建
Args:
node:将要插入到LinkedList的节点
"""
if node.freq not in self.__freqMap:
self.__freqMap[node.freq] = LinkedList()
linkedList = self.__freqMap[node.freq]
linkedList.insertFirst(node)
def __deleteNode(self,node):
"""
删除指定的节点，如果节点删除后，对应的双链表为空，则从__freqMap中删除这个链表
Args:
node:将要删除的节点
"""
if node.freq not in self.__freqMap:
return
linkedList = self.__freqMap[node.freq]
freq = node.freq
linkedList.delete(node)
if linkedList.isEmpty():
del self.__freqMap[freq]
def __removeMinFreqElement(self):
"""
删除频率最低的元素，从__freqMap和__keyMap中都要删除这个节点，如果节点删除后对应的链表为空，则要从__freqMap中删除这个链表
"""
linkedList = self.__freqMap[self.__minFreq]
node = linkedList.getLast()
linkedList.delete(node)
del self.__keyMap[node.key]
if linkedList.isEmpty():
del self.__freqMap[node.freq]
|