LRU讲的很不错https://leetcode.cn/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/
哈希双链表
class LRUCache {
//明确LRU缓存要实现什么功能
//get(key) 如果key存在 获取其值 并把它设为最近使用过的节点
// put(key,val) 如果key存在 更改节点的值 并且把它设为最近使用过的节点 如果它不存在 缓存满了 先删掉最近最少使用的节点 并讲它加入
//缓存
//头部节点存放最近最少使用的节点
//尾部节点刚刚使用过
class Node{//双链表节点
int key;
int val;
Node prev;//前驱指针
Node next;//后继指针
public Node(int key,int val){
this.key = key;
this.val = val;
}
}
class DoubleList{//双向链表
private Node head;//头节点
private Node tail;//尾节点
private int size;
public DoubleList(){
this.head = new Node(0,0);
this.tail = new Node(0,0);
head.next = tail;
tail.prev = head;
size = 0;
}
//在尾节点之前添加节点x
public void addLast(Node x){
x.prev = tail.prev;
x.next = tail;
tail.prev.next = x;
tail.prev = x;
size += 1;
}
//删除节点x
public void remove(Node x){
x.prev.next = x.next;
x.next.prev = x.prev;
size -= 1;
}
public int getSize(){
return size;
}
public Node removeFirst(){
if(head.next == tail)
return null;
Node first = head.next;
remove(first);
return first;
}
}
private Map<Integer,Node> map;
private DoubleList cache;
private int cap;
public LRUCache(int capacity) {
this.map = new HashMap<>();
this.cache = new DoubleList();
this.cap = capacity;
}
public void makeRecently(int key){
Node x = map.get(key);
cache.remove(x);
cache.addLast(x);
}
public int get(int key) {
if(map.containsKey(key) == false)
return -1;
makeRecently(key);
return map.get(key).val;
}
public void put(int key, int value) {
if(map.containsKey(key) == true){
// 修改map
Node node = map.get(key);
node.val = value;
makeRecently(key);
return ;
}
if(cache.getSize() == cap){
Node first = cache.removeFirst();
//这里说明了 在节点中也需要记录key值
map.remove(first.key);
}
Node x = new Node(key,value);
map.put(key,x);
cache.addLast(x);
}
}
