LRU缓存
一、什么是LRU算法
LRU,Least Recently Used算法,即一种缓存淘汰策略。
计算机的缓存容量有限,若缓存满了则需要删除一些内容,给新的缓存腾出空间,但问题是要删除哪些内容呢?当然是把用的少的缓存删掉,把最有用的数据继续保留以便于继续使用。那么如何判定哪些数据是有用的呢?
缓存淘汰的策略有很多,而LRU则是一种较为简单常用的算法,LRU判定最近使用过的数据为有用的,很久都没用过的数据是无用的,在内存满了就优先删除很久未使用,也就是无用的数据。
常见的场景如手机的后台运行缓存,我们依次打开了[设置] [网易云音乐] [优酷视频] [bilibili],假设手机只允许同时打开个应用程序,那么在我们打开bilibili的那一刻,就会将最久未使用的 [设置] 关闭,腾出空间给 [bilibili]
二、LRU的算法描述
①接收一个capacity的参数作为缓存的最大容量
②实现put(key,value)方法存入键值对
③实现get(key)方法获取key对应的value,若不存在返回-1
//缓存容量为2
LRUCache cache = new LRUCache(2);
//可以把cache理解为一个队列
//最近使用过的在队列头,久未使用的在队列尾
cache.put(1,1);//cache = [(1,1)]
cache.put(2,2);//cache = [(2,2),(1,1)]
cache.get(1);//此时访问了key为1的entry 因此将其移动到队列头 cache = [(1,1),(2,2)]
cache.put(3,3);//此时容量已满,需要删除久未使用的数据,也就是队列尾 然后插入新的数据 cache = [(3,3),(1,1)]
cache.get(2);//return -1
cache.put(1,4);//key=1已经存在,只需要覆盖value即可 且此时需要将更新的entry提前到队列头 cache = [(1,4),(3,3)]
三、LRU算法设计
要让LRUCache的put和get方法时间复杂度为O(1),那么要求数据结构的查询时间为O(1),插入时间为O(1),删除时间为O(1),且有序。
为了区分最近使用和久未使用的数据,我们必须要求cache有序;能够在cache中判断key是否存在;cache容量满了需要删除最后一个entry;每次访问的entry都重新放在队列头部。
为此我们可以考虑到HashMap与LinkedList的结合——LinkedHashMap
LRU缓存算法的核心就是基于LinkedHashMap实现的,其核心就是通过HashMap赋予链表查询迅速的特性
(图片来源LeetCode)
四、代码实现
首先将双向链表实现
class DoubleLinkedList {
class Entry{
int key;
int value;
Entry prev;
Entry next;
Entry(int key, int value) {
this.key = key;
this.value = value;
}
}
private Entry head;
private Entry tail;
private int size;
public LRUCache() {
//缓存初始化
head = new Entry(0,0);
tail = new Entry(0,0);
head.next = tail;
tail.prev = head;
int size = 0;
}
//在链表首部添加entry
public void addFirst(Entry entry) {
entry.next = head.next;
entry.prev = head;
head.next.prev = entry;
head.next = entry;
size++;
}
//删除链表中的entry
public void remove(Entry entry) {
Entry prev = entry.prev;
Entry next = entry.next;
prev.next = next;
next.prev = prev;
size--;
}
//删除链表中最后一个节点并返回
public Entry removeLast() {
if (tail.prev == head) {
return null;
}
Entry last = tail.prev;
remove(last);
return last;
}
public int size() {
return size;
}
}
然后结合HashMap即可:
public class LRUCache {
private HashMap<Integer, DoubleLinkedList.Entry> map;
private DoubleLinkedList cache;
private int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
cache = new DoubleLinkedList();
}
public int get(int key) {
//若map中不存在cache映射的key return -1
if (!map.containsKey(key)) {
return -1;
}
int val = map.get(key).value;
//将get过的entry提前,put方法直接采用了删除尾部,首部添加的策略。
put(key,val);
return val;
}
public void put(int key, int val) {
DoubleLinkedList.Entry x = new DoubleLinkedList.Entry(key,val);
if (map.containsKey(key)) {
//可以理解为缓存队列尾部删除 首部添加
cache.remove(map.get(key));
cache.addFirst(x);
//map中添加该entry的映射
map.put(key,x);
} else {
//当缓存已满,不仅要删除最后一个Entry,还要把map中映射到该节点的key同时删除,而这个key只能通过Entry得到。
if(capacity == cache.size()) {
//删除链表最后一个数据
DoubleLinkedList.Entry last = cache.removeLast();
map.remove(last.key);
}
cache.addFirst(x);
map.put(key,x);
}
}
}
以上就是LRU的简单实现,
原文参考LeetCode:https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/
放个源码:https://github.com/whl-1998/DataStructAndAlgorithm/tree/master/src/com/whl
下一篇: 142.环形链表2