LRU缓存淘汰算法
leet code146: https://leetcode.cn/problems/lru-cache
一、基本思想
1.1 基本思想
LRU全名Last Recently Used,即当缓存空间满时,优先淘汰最不常使用(访问)的缓存。
1.2 抽象接口
1、 init() 初始化大小为N的缓存空间
2、 put(key, val) 将id为key的缓存加入缓存空间,要求O(1)时间复杂度
3、get(key) 得到id为key的缓存,要求O(1)时间复杂度
明确行为:
要实现缓存访问时间的区别,所选的数据结构最好能保持元素有序。
在put存一个缓存时,有可能是插入,也有可能是更新。不论是插入还是更新,id为key的缓存页都被访问了一次,需要将它的优先级提高。插入时还需要考虑缓存满,需要选择一个缓存页淘汰。
在get一个缓存时,访问了一遍id为key的缓存,需要提高它的优先级。
二、代码实现
2.1 数据结构
插入删除要求O(1),自然是选择链表。
查找更新要求O(1),肯定是哈希表。
两者结合就形成了哈希链表,LinkedHashMap。
2.2 借助API实现
class LRUCache {
int cap;
// 插入队尾,就是最常使用的
LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
public LRUCache(int capacity) {
cap = capacity;
}
public int get(int key) {
int val = -1;
if(cache.containsKey(key)){
// 得到值
val = cache.get(key);
// 提升这个值到队尾
cache.remove(key);
cache.put(key, val);
}
return val;
}
public void put(int key, int val) {
if(cache.containsKey(key)){
cache.put(key, val); //变更数据
this.get(key);
return;
}else{
// 插入需要先判断容量是否已满
if(cache.size()>=this.cap){
// 淘汰队首
int oldKey = cache.keySet().iterator().next();
cache.remove(oldKey);
}
cache.put(key, val);
}
}
}
}
我们用链表存数据,最新的数据插入到队尾。
get要做的事情:得到key对应的值,将key优先级提高。
put要做的事情:判断key在不在链表中,相应的修改/插入操作行为。
修改操作:修改值,提升优先级。
插入操作:判断队伍空间是否满,已满需要淘汰队首。然后在插入。
2.3 自己实现哈希链表
(1)想明白
要做哪些事?
- 自己实现双向链表
- 利用HashMap哈希表
- 整合这两个为哈希链表
哈希链表要实现哪些API?
- get 根据key得到值
- put 根据key进行修改或插入操作
- remove 删除指定key
双向链表要实现的API:
- 插入节点
- 删除节点(给出Node)
(2)双向链表实现
class Node{
public int key,val;
public Node prev,next;
Node(int key, int val){
this.key = key;
this.val = val;
prev = null;
next = null;
}
}
class DoubleList{
private Node dummyNode;
public int size;
DoubleList(){
dummyNode = new Node(-1, -1);
dummyNode.prev = dummyNode;
dummyNode.next = dummyNode;
size = 0;
}
public void insert(Node tmp){
tmp.prev = dummyNode.prev;
tmp.next = dummyNode;
dummyNode.prev.next = tmp;
dummyNode.prev = tmp;
size+=1;
}
public void remove(Node tmp){
if(size<=0) return;
Node front = tmp.prev;
Node rear = tmp.next;
front.next = rear;
rear.prev = front;
tmp.prev = null;
tmp.next = null;
size-=1;
}
public int removeFirst(){
int ret = dummyNode.next.key;
remove(dummyNode.next);
return ret;
}
}
技巧:文章来源:https://www.uudwc.com/A/aYDR9/
- 伪头节点
- 循环链表
(3) LRUCache实现文章来源地址https://www.uudwc.com/A/aYDR9/
class LRUCache {
private HashMap<Integer, Node> map;
private DoubleList cache;
private int cap;
public LRUCache(int capacity) {
cap = capacity;
map = new HashMap<>();
cache = new DoubleList();
}
public int get(int key) {
Node tmp = map.get(key);
int val = -1;
if(tmp==null) return val;
val = tmp.val;
cache.remove(tmp);
cache.insert(tmp);
return val;
}
public void put(int key, int val) {
Node tmp = map.get(key);
if(tmp==null){
// 插入操作,判断队满
if(cache.size == cap){
int oldkey = cache.removeFirst();
map.remove(oldkey);
}
Node new_tmp = new Node(key,val);
map.put(key, new_tmp);
cache.insert(new_tmp);
}else{
// 更新操作
cache.remove(tmp);
tmp.val = val;
cache.insert(tmp);
}
}
}