2021-07-02（146. LRU 缓存机制）

本文主要是介绍2021-07-02（146. LRU 缓存机制），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

class LRUCache {class ListNode{int key;int value;ListNode prev;ListNode next;public ListNode(){}public ListNode(int key, int value){this.key=key;this.value=value;}}// 这个Integer也是get的输入参数keyMap<Integer,ListNode> cache=new HashMap<Integer,ListNode>();int size;int capacity;ListNode head,tail;public LRUCache(int capacity) {this.size=0;this.capacity=capacity;head=new ListNode();tail=new ListNode();head.next=tail;tail.prev=head;}public int get(int key) {ListNode node = cache.get(key);if(node==null){return -1;}moveToHead(node);return node.value;}public void put(int key, int value) {ListNode node =cache.get(key);if(node==null){ListNode newNode=new ListNode(key,value);cache.put(key,newNode);addToHead(newNode);++size;if(size>capacity){ListNode tail=removeTail();cache.remove(tail.key);--size;}}else{node.value=value;moveToHead(node);}}void addToHead(ListNode node){node.prev=head;node.next=head.next;head.next.prev=node;head.next=node;}void removeNode(ListNode node){node.prev.next=node.next;node.next.prev=node.prev;}void moveToHead(ListNode node){removeNode(node);addToHead(node);}ListNode removeTail(){ListNode res=tail.prev;removeNode(res);return res;}}/*** 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);*/

要选择哈希表和双向链表（链表增删快+配合哈希表查找快）来实现是没想到的，我一上来想到的是用队列，用哈希表记录key和其对应节点其实就是典型的空间换时间策略。
这种工作量大点的工程性代码还要多敲。

这篇关于2021-07-02（146. LRU 缓存机制）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---