记录生活中的点点滴滴

0%

LRU实现

这篇文章写一下LRU的实现对应leetcode上的题目146. LRU 缓存机制

LRU 算法就是一种缓存淘汰策略原理不难

计算机的缓存容量有限如果缓存满了就要删除一些内容给新内容腾位置但问题是删除哪些内容呢我们肯定希望删掉哪些没什么用的缓存而把有用的数据继续留在缓存里方便之后继续使用那么什么样的数据我们判定为有用的的数据呢

LRU 缓存淘汰算法就是一种常用策略LRU 的全称是 Least Recently Used也就是说我们认为最近使用过的数据应该是是有用的很久都没用过的数据应该是无用的内存满了就优先删那些很久没用过的数据

例如手机的后台运行情况

当然除了LRU还有FIFO先进先出LFU最少使用等等其他算法

先看看题

1
2
3
4
5
6
7
8
9
10
11
class LRUCache {
public LRUCache(int capacity) {

}
public int get(int key) {

}
public void put(int key, int value) {

}
}

实现它的get和put方法这个类肯定维护着一个数据结构可能是数组也可能是链表或者其他更复杂的什么的数据结构需要我们后续的分析才能得出来

我们来想想它的get和put方法

  • get方法先得判断有没有有了然后将这个key提升等级然后返回val
  • put方法首先判断是否有相同的如果有的话直接把这个key提升等级就结束了没有的话要看缓存是否满了如果满了得先删除一个等级最低的然后再插入这个kv也还是得提升等级

所以我们通过上面的分析可以得出来首先因为头尾和中间的数据要经常变换位置所以如果要求复杂度为O1那么需要是链表+hashmap只有这样的数据结构才能符合条件

所以我们使用的数据结构就是 LinkedHahsMap

还需要一个size字段记录缓存的最大长度在构造方法中初始化即可

1
2
3
4
5
6
7
8
class LRUCache {
int size;
LinkedHashMap<Integer,Integer> map = new LinkedHashMap<>();

public LRUCache(int capacity) {
this.size = capacity;
}
}

基本就是这样HashMap会扩容所以我们只能通过添加一个size字段来控制大小

然后完成get方法很简单的逻辑

1
2
3
4
5
6
7
// get 获取值
public int get(int key) {
if(!map.containsKey(key)) return -1;
//提升等级也就是把key提到map头
highLevel(key);
return map.get(key);
}

接下来提升等级方法

1
2
3
4
5
6
// 提升等级
public void highLevel(int key){
int val = map.get(key);
map.remove(key);
put(key,val);
}

其实就是删除然后重新添加 所以接下来重点还是我们的put方法

关键在于最近最少使用的那些数据是在map的前面还是后面呢

我设计的是前面因为每次默认使用LinkedHashMap的put方法它被放到了链表尾

所以我们每次如果想提升等级说白了就是先删除再放到链表尾

不过对于put方法还多了一些逻辑上的判断代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void put(int key, int value) {
//判断是否有相同的
if(map.containsKey(key)){
map.put(key,value);
highLevel(key);
return;
}
// 判断缓存是否满
if(map.size()>=this.size){//超出
//删除头部的
int top = map.keySet().iterator().next();
map.remove(top);
}
map.put(key,value);
}

所以综上代码如下

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
class LRUCache {
int size;
LinkedHashMap<Integer,Integer> map = new LinkedHashMap<>();

public LRUCache(int capacity) {
this.size = capacity;
}
// get 获取值
public int get(int key) {
if(!map.containsKey(key)) return -1;
//提升等级也就是把key提到map头
highLevel(key);
return map.get(key);
}
// put放入值
public void put(int key, int value) {
//判断是否有相同的
if(map.containsKey(key)){
map.put(key,value);
highLevel(key);
return;
}
// 判断缓存是否满
if(map.size()>=this.size){//超出
//删除头部的
int top = map.keySet().iterator().next();
map.remove(top);
}
map.put(key,value);
}
// 提升等级
public void highLevel(int key){
int val = map.get(key);
map.remove(key);
put(key,val);
}
}

/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/