class LRUCahce {
private Node head;
private Node tail;
private Map hashMap;
private int capacity;
public LRUCahce(int capacity) {
this.capacity = capacity;
hashMap = new HashMap<>();
}
/**
*
* @Title: put
* @Description:
* @param key
* @param value
*/
public void put(String key,Object value) {
Node node = hashMap.get(key);
if (node != null) {
node.value = value;
refreshNode(node);
}else{
if (hashMap.size() >= capacity) {
removeNode(head);
hashMap.remove(head.key);
}
Node newNode = new Node(key, value);
addNode(newNode);
hashMap.put(key, newNode);
}
}
/**
* @Title: get
* @Description:
* @param key
* @return
*/
public Object get(String key) {
Node node = hashMap.get(key);
if (node == null) {
return null;
}
refreshNode(node);
return node.value;
}
/**
* @Title: remove
* @Description:
* @param key
*/
public void remove(String key) {
Node node = hashMap.get(key);
if (node == null) {
return;
}else{
removeNode(node);
hashMap.remove(key);
}
}
/**
* @Title: refreshNode
* @Description:
* @param node
*/
public void refreshNode(Node node) {
if (node == tail) {
return;
}
removeNode(node);
addNode(node);
}
/**
* @Title: removeNode
* @Description:删除节点
* @param node
*/
public void removeNode(Node node) {
if (head == node && tail == node) {
head = null;
tail = null;
} else if (head == node) {
head = head.next;
head.pre.next = null; //help GC
head.pre = null;
}else if (tail == node) {
tail = tail.pre;
tail.next.pre = null;//help GC
tail.next = null;
}else {
node.pre.next = node.next;
node.next.pre = node.pre;
}
}
/**
* @Title: addNode
* @Description: 新增节点
* @param node
*/
public void addNode(Node node) {
if (tail == null) {
head = tail = node;
} else {
tail.next = node;
node.pre = tail;
tail = node;
tail.next = null;
}
}
class Node {
private String key;
private Object value;
private Node pre;// 前驱结点
private Node next;// 后驱结点
public Node(String key, Object value) {
this.key = key;
this.value = value;
}
}
}
Original: https://www.cnblogs.com/wha6239/p/15035468.html
Author: 一只烤鸭朝北走
Title: LRU算法
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/611790/
转载文章受原作者版权保护。转载请注明原作者出处!