前言
面试官:你了解过reids的内存淘汰策略么? 面试者:嗯,了解过,biubiu。。。 面试官:打断一下,如果让你去实现LRU算法,你该如何实现? 面试者:我就会用linkedHashMap实现。。。 面试官:好了,你的情况我大概知道了,你先回去等通知吧 面试者:就是又挂了呗。。
什么是LRU
LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used,也就是说我们认为最近使用过的数据应该是是「有用的」,很久都没用过的数据应该是无用的,内存满了就优先删那些很久没用过的数据。 如redis的内存淘汰策略就有LRU
算法实现思路
- 假设定义一个哈希链表阈值为5来存放用户信息,目前缓存了4个用户信息(001,002,003,004),这4个用户按照被访问的时间顺序依次从链表右端插入(001,002,003,004)。
- 如果现在业务查询005用户,哈希链表中没有则从数据库获取,由于当前容量为超过阈值,可以直接插入到缓存链表中,此时005是最新被访问的用户,则存在哈希链表最右端,那么在最左端的001用户是最近最少访问。(001,002,003,004,005)
- 如果接下来访问的是002用户信息,则002为最新被访问的用户需要将002位置移动到最右端。(001,003,004,005,002)
- 如果当前业务查006用户信息,则由于哈希链表中没有需要先到数据库查询,然后再插入到哈希链表中,但由于当前容量为6超过了哈希链表的阈值,则需要先淘汰最近最少访问的用户,也就是要删除哈希链表最左端的001用户,然后才将006插入到哈希链表中最右端。(003,004,005,002,006)
LRU代码实现
public class LRUCache {
private Node head;
private Node end;
private int limit;
private HashMap<String,Node> hashMap;
public LRUCache(int limit){
this.limit =limit;
hashMap = new HashMap<String,Node>();
}
public String get (String key){
Node node = hashMap.get(key);
if (node == null){
return null;
}
refreshNode(node);
return node.value;
}
public void put(String key,String value){
Node node = hashMap.get(key);
if(node == null){
if(hashMap.size()>=limit){
String oldKey=removeNode(head);
hashMap.remove(oldKey);
}
node = new Node(key,value);
addNode(node);
hashMap.put(key,node);
}else {
node.value = value;
refreshNode(node);
}
}
public void remove (String key){
Node node = hashMap.get(key);
refreshNode(node);
hashMap.remove(key);
}
private void refreshNode(Node node){
if(node == end){
return;
}
removeNode(node);
addNode(node);
}
private String removeNode(Node node){
if(node == head && node == end){
head = null;
end = null;
}else if (node == end){
end = end .pre;
end =null ;
} else if(node == head){
head = head.next;
head.pre = null;
}else {
node.pre.next =node.next;
node.next.pre = node.pre;
}
return node.key;
}
private void addNode(Node node){
if (end!=null){
end.next = node;
node.pre = end;
node.next =null;
}
end =node;
if (head == null){
head = node;
}
}
class Node {
Node(String key, String value) {
this.key = key;
this.value = value;
}
public Node pre;
public Node next;
public String key;
public String value;
}
}
总结
按照上述的思路来实现LRU算法并不是太难,后续作者理解更深理解后会继续更新相关内容。
|