请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache
类:
LRUCache(int capacity)
以 正整数 作为容量capacity
初始化 LRU 缓存int get(int key)
如果关键字key
存在于缓存中,则返回关键字的值,否则返回-1
。void put(int key, int value)
如果关键字key
已经存在,则变更其数据值value
;如果不存在,则向缓存中插入该组key-value
。如果插入操作导致关键字数量超过capacity
,则应该 逐出 最久未使用的关键字。
函数 get
和 put
必须以 O(1)
的平均时间复杂度运行。
/**
2024年7月20日16:38:09
定义node,要把key,value存取起来,同时记录前向节点,后向节点
然后维护这样一个节点的关系;
然后再用一个map就存储元素;
add元素,先put进map,然后更新节点关系;
如果超出size,再更新节点关系,移除map里老元素
get元素,就是正常get,get完需要把当前节点的位置移动到
最新的位置
*/
class LRUCache {
private class Node{
// key这个字段是为了容量超出限制时,可以快速的移除多余的元素
int key;
int value;
Node prev;
Node next;
public Node(){}
public Node(int key,int value){
this.key=key;
this.value=value;
}
}
private Map<Integer,Node> cache;
private int capacity;
private Node head, tail;
public LRUCache(int capacity) {
this.capacity=capacity;
cache=new HashMap<>(capacity);
head=new Node();
tail=new Node();
head.next=tail;
tail.prev=head;
}
public int get(int key) {
Node node=cache.get(key);
if(node==null){
return -1;
}
move2Head(node);
return node.value;
}
public void put(int key, int value) {
Node node=cache.get(key);
if(node==null){
Node newNode=new Node(key,value);
cache.put(key,newNode);
addNode(newNode);
if(cache.size()>capacity){
Node tailNode=popTail();
cache.remove(tailNode.key);
}
} else{
// 相同的key,value可能更新
node.value=value;
move2Head(node);
}
}
private void move2Head(Node node){
removeNode(node);
addNode(node);
}
private void addNode(Node node){
node.next=head.next;
node.prev=head;
head.next.prev=node;
head.next=node;
}
private void removeNode(Node node){
node.prev.next=node.next;
node.next.prev=node.prev;
}
private Node popTail(){
Node tailNode=tail.prev;
removeNode(tailNode);
return tailNode;
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/