package practice;
import java.util.HashMap;
import java.util.Map;
/**
* 链表头,链表尾,map,size
* 构造方法:初始化size,构建map,头尾赋空,头尾相连
* get: 判断是否包含key -> 得到key的Node -> 删除node -> 把Node添加到头部 -> 返回node.v
* put: 判断是否存在key -> 存在,删除 -> 初始化新节点,put到map中,头插 -> 长度超出,移除尾节点
*/
public class LRUTest<K, V> {
Node head;
Node tail;
Map<K, Node> map;
int maxSize;
private class Node {
Node pre;
Node next;
K k;
V v;
public Node(K k, V v) {
this.k = k;
this.v = v;
}
}
public LRUTest(int maxSize) {
this.maxSize = maxSize;
map = new HashMap<>(maxSize * 4 / 3);
head = new Node(null, null);
tail = new Node(null, null);
head.next = tail;
tail.pre = head;
}
public V get(K k) {
if (!map.containsKey(k)) {
return null;
}
Node node = map.get(k);
unlink(node);
appendHead(node);
return node.v;
}
public void put(K k, V v) {
if (map.containsKey(k)) {
unlink(map.get(k));
}
//不存在
Node node = new Node(k, v);
appendHead(node);
map.put(k, node);
if (map.size() > maxSize) {
//长度超出,移除尾节点
K removeKey = removeTail();
map.remove(removeKey);
}
}
public void unlink(Node node) {
Node pre = node.pre;
Node next = node.next;
pre.next = next;
next.pre = pre;
node.pre = null;
node.next = null;
}
public void appendHead(Node node) {
Node headNext = head.next;
head.next = node;
node.pre = head;
node.next = headNext;
headNext.pre = node;
}
public K removeTail() {
Node node = tail.pre;
Node pre = node.pre;
pre.next = tail;
tail.pre = pre;
node.pre = null;
node.next = null;
return node.k;
}
}
使用哈希表存储节点。降低查找复杂度
