本文主要是介绍LRU缓存淘汰算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
class LRUCache {
//哈希表+双向链表 LinkedHashMap (最近最少使用) 缓存机制
private Map<Integer,Node> map; //存储key value value为Node节点
private int capacity; //最大容量
private Node first; //虚拟头节点
private Node last; //虚拟尾节点
//构造方法
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>(capacity);
first = new Node(); //初始化虚拟头尾节点
last = new Node();
first.next = last; //开始没有任何键值对 头尾节点互指
last.prev = first;
}
//get方法
public int get(int key) {
Node node = map.get(key);
if(node == null) return -1;
//将该节点先删后插入到最前面 用完放前面
removeNode(node);
addAfterFirst(node);
return node.value;
}
//put方法
public void put(int key, int value) {
Node node = map.get(key);
if(node != null){
node.value = value;
//将该节点先删后插入到最前面 更新双向链表
removeNode(node);
}else{ //添加一对新的key-value
if(map.size() == capacity){
//淘汰最久未用的node
//map中的key要删除 双向链表中的虚拟尾节点前的节点也要删除
removeNode(map.remove(last.prev.key));
}
map.put(key,node = new Node(key,value)); //插入新节点
}
addAfterFirst(node); //更新双向链表
}
//从双向链表中删除节点
private void removeNode(Node node){
node.next.prev = node.prev;
node.prev.next = node.next;
}
//将该节点插入到虚拟头节点前面
private void addAfterFirst(Node node){
node.next = first.next;
first.next.prev = node;
node.prev = first;
first.next = node;
}
//静态内部类 value节点是一个个Node
private static class Node{
public int key;
public int value;
public Node prev;
public Node next;
public Node(int key,int value){
this.key = key;
this.value = value;
}
public Node(){}
}
}
/**
* 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);
*/
这篇关于LRU缓存淘汰算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!