lるアルゴリズム
12548 ワード
package lru;
import java.util.HashMap;
import java.util.LinkedHashMap;
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);
//
removeNode(node);
//
hashMap.remove(key);
}
/**
*
* @param node
*/
private void refreshNode(Node node) {
// , ;
if (node == end){
return;
}
// ,
removeNode(node);
//
addNode(node);
}
private void addNode(Node node) {
}
/**
* , ;
* @param node
*/
private String removeNode(Node node) {
if (node == end){
//
end = end.pre;
} else if (node == head){
//
head = head.next;
}else {
node.pre.next = node.next;
node.next.pre = node.pre;
}
return node.key;
}
}
package lru;
public class Node {
public Node pre;
public Node next;
public String key;
public String value;
public Node(String key, String value) {
this.key = key;
this.value = value;
}
}