LFU缓存
请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：$get$ 和 $put$。
- $get(key)$: - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 $-1$。
- $put(key, value)$ - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键。
「项的使用次数」就是自插入该项以来对其调用 $get$ 和 $put$ 函数的次数之和。使用次数会在对应项被移除后置为 $0$ 。
1
2
3
4
5
6
7
8
9
10
11
12
| LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 去除 key 2
cache.get(2); // 返回 -1 (未找到key 2)
cache.get(3); // 返回 3
cache.put(4, 4); // 去除 key 1
cache.get(1); // 返回 -1 (未找到 key 1)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
|
Solution-双哈希
freqMap: 以频率freq为索引(key)，每个索引存放一个双向链表(value)。
- 双向链表：存放所有使用频率为
freq 的缓存，缓存里存放三个信息，分别为key,value以及使用频率freq。
cache: 以key为索引，每个索引存放对应缓存在freqMap中链表里的内存地址。minFreq: 当前缓存最少使用的频率，为删除操作服务。- 利用双哈希可以实现
get和put操作的时间复杂度为 $O(1)$.
接下来要关注的点就是如何实现get和put的功能的同时维护以上三个变量。
get(key): 通过索引key在cache中找到缓存freqMap中的链表的内存地址
- 如果不存在：直接返回 $-1$；
- 如果存在：获取缓存的相关信息，取得缓存的键值以及使用频率。
get后使用频率freq加 $1$，更新缓存在freqMap中的位置。已知这个缓存的key,value,freq，那么该缓存该存放到freqMap中以freq + 1为索引的链表中。以 $O(1)$ 删除该缓存对应的结点，根据情况更新minFreq值，然后以 $O(1)$ 插入到以freq + 1为索引的链表头部完成更新。- 之所以插入到链表头部，是为了保证缓存在当前链表中从链表头到链表尾的插入时间是有序的，为删除操作服务。
put(key, value)操作: 就跟所有的Map操作一样，先检查key-value是否已存在，然后再做对应的处理。
- 已存在：将当前缓存的值更新为
value
- 不存在：添加进哈希表，同时检查缓存是否已达到最大容量
capacity，如果达到，先删除最近最少用的缓存，再进行插入。
- 插入时结点的频率为 $1$，链接到
freqMap中频率为 $1$ 的链表的头部。
- 此时
minFreq一定为 $1$.
- 删除操作：由于维护了
minFreq，所以能够知道freqMap中目前使用频率最少的索引，以 $O(1)$ 获得频率等于minFreq的链表；同时由于保证了链表从链表头到链表尾的插入时间是有序的，所以freqMap.get(minFreq)获得的链表中的链表尾的结点即为使用频率最小且插入时间最早的结点，删除它，同时根据情况更新minFreq，整个时间复杂度为 $O(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
| class LFUCache {
private int minFreq, capacity, size;
private Map<Integer, DLinkedNode> cache;
private Map<Integer, DLinkedList> freqMap;
public LFUCache(int capacity) {
this.capacity = capacity;
cache = new HashMap<>();
freqMap = new HashMap<>();
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) return -1;
incrementFreq(node);
return node.value;
}
public void put(int key, int value) {
if (capacity == 0) return;
DLinkedNode node = cache.get(key);
if (node == null) {
if (size == capacity) {
DLinkedList minFreqList = freqMap.get(this.minFreq);
DLinkedNode tailNode = minFreqList.tail.pre;
cache.remove(tailNode.key);
minFreqList.remove(tailNode);
size--;
}
DLinkedNode newNode = new DLinkedNode(key, value);
cache.put(key, newNode);
DLinkedList dLinkedList = freqMap.get(1);
if (dLinkedList == null) {
dLinkedList = new DLinkedList();
freqMap.put(1, dLinkedList);
}
dLinkedList.addToHead(newNode);
size++;
this.minFreq = 1;
} else {
node.value = value;
incrementFreq(node);
}
}
private void incrementFreq(DLinkedNode node) {
int freq = node.freq;
DLinkedList freqLinkedList = freqMap.get(freq);
freqLinkedList.remove(node);
if (freq == this.minFreq && freqLinkedList.isEmpty())
this.minFreq = freq + 1;
++node.freq;
freqLinkedList = freqMap.get(freq + 1);
if (freqLinkedList == null) {
freqLinkedList = new DLinkedList();
freqMap.put(freq + 1, freqLinkedList);
}
freqLinkedList.addToHead(node);
}
private static class DLinkedNode {
private int key, value;
private int freq = 1;
private DLinkedNode pre, next;
public DLinkedNode() {}
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
private static class DLinkedList {
private DLinkedNode head, tail;
public DLinkedList() {
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.pre = head;
}
private void remove(DLinkedNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
private void addToHead(DLinkedNode node) {
node.pre = head;
node.next = head.next;
head.next.pre = node;
head.next = node;
}
private boolean isEmpty() {
return head.next == tail ? true : false;
}
}
}
|
Redis中的LFU
