LRU-最近最久未使用算法
程序员文章站
2024-03-18 13:01:16
...
import java.util.HashMap;
import java.util.Map;
/**
* @author caisebei
*/
public class LRUCache {
private Node head;
private Node end;
private int limit;
private Map<String,Node> hashMap;
public LRUCache(int limit) {
this.limit = limit;
this.hashMap = new HashMap<>();
}
public Node get(String key) {
Node node = hashMap.get(key);
if(node == null) {
return null;
}
refreshNode(node);
return node;
}
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);
removeNode(node);
hashMap.remove(key);
}
/**
*
* 添加节点
**/
private void addNode(Node node) {
if(end != null) {
end.next = node;
node.pre = end;
}
end = node;
if(head == null) {
head = node;
}
}
/**
* 刷新被访问的节点位置
**/
private void refreshNode(Node node) {
if(node == end) {
return ;
}
removeNode(node);
addNode(node);
}
/**
* 删除节点
* @return java.lang.String
**/
private String removeNode(Node node) {
if(node == head && node == end) { //移除唯一节点
head = null;
end = null;
}else if (node == end) { //移除尾节点
end = end.pre;
end.next = 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;
}
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(5);
lruCache.put("001", "用户1");
lruCache.put("002", "用户2");
lruCache.put("003", "用户3");
lruCache.put("004", "用户4");
lruCache.put("005", "用户5");
lruCache.get("002");
lruCache.put("006", "用户6");
}
class Node {
public Node pre;
public Node next;
public String key;
public String value;
Node(String key, String value) {
this.key = key;
this.value = value;
}
}
}
from: 《漫画算法》1