Java 基于HashMap的LRU缓存
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。
LRU算法示意图：
LRU算法代码：
/*
*来 自
nowjava.com - 时 代 Java
*/
import java.util.HashMap;
class LRU {
int capacity;
HashMap map = new HashMap();
Node head = null;
Node end = null;
public LRU(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
if (map.containsKey(key)) {
Node n = map.get(key);
/**来自
时代Java公众号**/
remove(n);
setHead(n);
return n.value;
}
return -1;
}
public void remove(Node n) {
if (n.pre != null) {
n.pre.next = n.next;
} else {
head = n.next;
}
if (n.next != null) {
n.next.pre = n.pre;
} else {
end = n.pre;
}
}
public void setHead(Node n) {
n.next = head;
n.pre = null;
if (head != null)
head.pre = n;
head = n;
if (end == null)
end = head;
}
public void set(int key, int value) {
if (map.containsKey(key)) {
Node old = map.get(key);
old.value = value;
remove(old);
setHead(old);
} else {
Node created = new Node(key, value);
if (map.size() >= capacity) {
map.remove(end.key);
remove(end);
setHead(created);
} else {
setHead(created);
}
map.put(key, created);
}
}
}
class Node {
int key;
int value;
Node pre;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public&