解题思路：
在LRU基础上，加上使用频率这一个指标去做页面置换。
labuladong大佬的讲解：LFU算法拆解
最不经常使用（LFU）缓存算法，应该支持操作：get 和 put。
在缓存满的时候，淘汰访问频次最低的数据，如果访问频次最低的数据有多条，需要淘汰最旧的数据。
使用一个HashMap(keyToVal)存储key到val的映射，就可以快速计算get(key)
使用一个HashMap(keyToFreq)存储key到freq的映射，就可以快速操作key对应的freq
使用一个HasMap(freqToKey)存储freq到key的映射，实现：
1.freq对key的一对多关系
2.希望freq中对应的key有时序
3.希望能够快速删除key列表中的一个key
LinkedHashSet可以满足上述3个要求
代码：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
95class LFUCache {
HashMap<Integer,Integer> keyToVal;
HashMap<Integer,Integer> keyToFreq;
//LinkedHashSet
//顾名思义，是链表和哈希集合的结合体。
//链表不能快速访问链表节点，但是插入元素具有时序；
//哈希集合中的元素无序，但是可以对元素进行快速的访问和删除
HashMap<Integer,LinkedHashSet<Integer>> freqToKeys; //同一个频率可能对应多个key
int minFreq;//最小频率
int cap;//容量
public LFUCache(int capacity) {
keyToVal = new HashMap<>();
keyToFreq = new HashMap<>();
freqToKeys = new HashMap<>();
this.cap = capacity;
this.minFreq = 0;
}
public int get(int key) {
if(!keyToVal.containsKey(key)){
return -1;
}
//增加key对应的freq
increaseFreq(key);
return keyToVal.get(key);
}
public void put(int key, int value) {
if(this.cap <= 0) return ;
//若key已存在，修改对应的val即可
if(keyToVal.containsKey(key)){
keyToVal.put(key,value);
//key对应的freq加一
increaseFreq(key);
return;
}
//若key不存在，需要插入
//如果容量已满的话需要淘汰一个freq最小的key
if(this.cap <= keyToVal.size()){
removeMinFreqKey();
}
//插入key和val，对应的freq为1
//插入kv表
keyToVal.put(key,value);
//插入kf表
keyToFreq.put(key,1);
//插入fk表
freqToKeys.putIfAbsent(1, new LinkedHashSet<>());//如果key已经存在，不再放入值(不覆盖)
freqToKeys.get(1).add(key);//频率1增加一个元素
//新插入key后最小的freq肯定是1
this.minFreq = 1;
}
private void increaseFreq(int key){ //增加key对应freq是LFU的核心
int freq = keyToFreq.get(key);
//更新kf表
keyToFreq.put(key,freq+1);
//更新kf表，将key从freq对应的列表删除
freqToKeys.get(freq).remove(key);
//将key加入freq+1对应的列表中
freqToKeys.putIfAbsent(freq+1,new LinkedHashSet<>());
freqToKeys.get(freq+1).add(key);
//如果freq对应的列表空了，移除这个freq
if(freqToKeys.get(freq).isEmpty()){
freqToKeys.remove(freq);
//若这个freq恰好是minFreq，更新minFreq
if(freq == this.minFreq){
this.minFreq++;
}
}
}
private void removeMinFreqKey(){//淘汰最小频率的对象也是LFU的核心
//获取freq最小的key列表
LinkedHashSet<Integer> keyList = freqToKeys.get(this.minFreq);
//其中最先被插入的那个key就是该被淘汰的key
int deletedKey = keyList.iterator().next();
//更新FK表
keyList.remove(deletedKey);
//如果删除key之后列表为空
if(keyList.isEmpty()){
freqToKeys.remove(this.minFreq);
//这里没有办法快速求得最小minfreq，所以不更新minfreq频率
}
//更新kv表
keyToVal.remove(deletedKey);
//更新kf表
keyToFreq.remove(deletedKey);
}
}
