LRU缓存淘汰算法

本文主要是介绍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缓存淘汰算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！