LRU&LFU算法
每次淘汰那些最久没被使用的数据
LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。
要让 put 和 get 方法的时间复杂度为 O(1)，我们可以总结出 cache 这个数据结构必要的条件：
1、显然 cache 中的元素必须有时序，以区分最近使用的和久未使用的数据，当容量满了之后要删除最久未使用的那个元素腾位置。
2、我们要在 cache 中快速找某个 key 是否已存在并得到对应的 val；
3、每次访问 cache 中的某个 key，需要将这个元素变为最近使用的，也就是说 cache 要支持在任意位置快速插入和删除元素。
那么，什么数据结构同时符合上述条件呢？哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表 LinkedHashMap。
LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。
若要自己实现，则需要hashmap 和 双链表
尾插 + hashmap，保证迭代顺序就是插入顺序
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
| class LRUCache {
LinkedHashMap<Integer,Integer> cache;
int cap;
public LRUCache(int capacity) {
cache=new LinkedHashMap<>();
cap=capacity;
}
public int get(int key) {
int val=cache.getOrDefault(key,-1);
if(val!=-1){
makeRecently(key);
}
return val;
}
public void put(int key, int value) {
if(cache.containsKey(key)){
cache.put(key,value);
makeRecently(key);
}else{
cache.put(key,value);
}
if(cache.size()>cap){
int first = cache.keySet().iterator().next();
cache.remove(first);
}
}
void makeRecently(int key){
int val=cache.get(key);
cache.remove(key);
cache.put(key,val);
}
}
|
LRU 算法的核心数据结构是使用哈希链表 LinkedHashMap，首先借助链表的有序性使得链表元素维持插入顺序，同时借助哈希映射的快速访问能力使得我们可以在 O(1) 时间访问链表的任意元素。
LFU 算法的淘汰策略是 Least Frequently Used，也就是每次淘汰那些使用次数最少的数据。
淘汰访问频次最低的数据，如果访问频次最低的数据有多条，需要淘汰最旧的数据
LinkedHashSet 顾名思义，是链表和哈希集合的结合体。链表不能快速访问链表节点，但是插入元素具有时序；哈希集合中的元素无序，但是可以对元素进行快速的访问和删除。
那么，它俩结合起来就兼具了哈希集合和链表的特性，既可以在 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
| class LFUCache {
HashMap<Integer, Integer> keyToVal;
HashMap<Integer, Integer> keyToFreq;
HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
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) {}
public void put(int key, int val) {}
}
|
注意：测试用例有capacity为0的情况，需要考虑
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
| class LFUCache {
HashMap<Integer,Integer> keyValue;
HashMap<Integer,Integer> keyFreq;
HashMap<Integer, LinkedHashSet<Integer>> freqKey;
int minFreq;
int cap;
public LFUCache(int capacity) {
keyValue=new HashMap<>();
keyFreq=new HashMap<>();
freqKey=new HashMap<>();
minFreq=0;
cap=capacity;
}
public int get(int key) {
if(cap==0){
return -1;
}
int val = keyValue.getOrDefault(key,-1);
if(val!=-1){
increaseFreq(key);
}
return val;
}
public void put(int key, int value) {
if(cap==0){
return;
}
if(keyValue.containsKey(key)){
keyValue.put(key,value);
increaseFreq(key);
}else{
if(keyValue.size()>=cap){
removeLeastFreq();
}
keyValue.put(key,value);
keyFreq.put(key,1);
freqKey.putIfAbsent(1,new LinkedHashSet<>());
LinkedHashSet<Integer> set = freqKey.get(1);
set.add(key);
minFreq=1;
}
}
void removeLeastFreq(){
LinkedHashSet<Integer> set = freqKey.get(minFreq);
int first = set.iterator().next();
set.remove(first);
keyValue.remove(first);
keyFreq.remove(first);
}
void increaseFreq(int key){
int freq=keyFreq.get(key);
keyFreq.put(key,freq+1);
freqKey.putIfAbsent(freq+1,new LinkedHashSet<>());
LinkedHashSet<Integer> cur = freqKey.get(freq + 1);
cur.add(key);
LinkedHashSet<Integer> pre = freqKey.get(freq);
pre.remove(key);
if(pre.isEmpty()){
freqKey.remove(freq);
if(freq==minFreq){
minFreq++;
}
}
}
}
|