首先看看什么是LRU
LRU是Least Recently Used的缩写,即最近最少使用,是一种常用的页面置换算法,选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 t,当须淘汰一个页面时,选择现有页面中其 t 值最大的,即最近最少使用的页面予以淘汰。(来自[百度百科](https://baike.baidu.com/item/LRU/1269842?fr=aladdin))
Java实现
先来捋一下思路,我们需要准备一个双向链表,这样到时候删除cache中很久没有被使用的key的时间复杂度就为n(1)。但是链表的查询时间复杂度为O(n),对此我们引入HashMap进行存储链表节点,HashMap的查询时间复杂度为O(1)。
代码实现如下
import java.util.HashMap;
import java.util.Map;
class LRUCacheTest{
private class LinkedNode{
private int key;
private int val;
LinkedNode pre;
LinkedNode next;
public LinkedNode(){}
public LinkedNode(int key, int val){
this.key = key;
this.val = val;
this.pre = null;
this.next = null;
}
}
private Map<Integer, LinkedNode> map = new HashMap<>();
private int capacity;
private LinkedNode head;
private LinkedNode tail;
public LRUCacheTest(int capacity){
this.capacity = capacity;
head = new LinkedNode(-1,-1);
tail = new LinkedNode(-1,-1);
head.next = tail;
head.pre = null;
tail.pre = tail;
tail.next = null;
}
public int get(int key){
if(map.containsKey(key)){
LinkedNode node = map.get(key);
removeNode(node);
addToHead(node);
System.out.print("The value of "+key+" is ");
return map.get(key).val;
}
System.out.print("404, the key you get is not in cache ");
return -1;
}
private void removeNode(LinkedNode node) {
LinkedNode from = node.pre;
LinkedNode to = node.next;
from.next = to;
to.pre = from;
}
private void addToHead(LinkedNode node) {
node.next = head.next;
node.pre = head;
head.next.pre = node;
head.next = node;
}
public void put(int key, int val){
if(map.containsKey(key)){
map.remove(key);
removeNode(map.get(key));
LinkedNode node = new LinkedNode(key, val);
map.put(key, node);
addToHead(node);
System.out.println(key+" has been put in cache, the value of "+key+" is "+ val);
}else{
if(map.size()==capacity){
int removeKey = removeTailNode();
map.remove(removeKey);
LinkedNode node = new LinkedNode(key, val);
addToHead(node);
map.put(key,node);
System.out.println(key+" has been put in cache, the value of "+key+" is "+ val);
}else{
LinkedNode node = new LinkedNode(key, val);
map.put(key,node);
addToHead(node);
System.out.println(key+" has been put in cache, the value of "+key+" is "+ val);
}
}
}
private int removeTailNode() {
LinkedNode node = tail.pre;
removeNode(tail.pre);
return node.key;
}
}
public class LRUTest01 {
public static void main(String[] args) {
LRUCacheTest lru = new LRUCacheTest(3);
lru.put(1,1);
lru.put(2,2);
lru.put(3,3);
System.out.println(lru.get(1));
lru.put(4,4);
System.out.println(lru.get(2));
}
}
运行结果如下
![请添加图片描述](https://img-blog.csdnimg.cn/e80b304082dd4eb0b94010eaadb5b957.png)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)