太仓市住房城乡建设局网站,深圳市人才一体化综合服务平台,网站建设太金手指六六二八,自建橱柜教程146.LRU缓存 方法一#xff1a;哈希表双向链表
使用一个哈希表和一个双向链表维护所有在缓存中的键值对
双向链表按照被使用的顺序存储了这些键值对#xff0c;靠近头部的键值对是最近使用的#xff0c;而靠近尾部的键值对是最久使用的哈希表即为普通的哈希映射#xff0…146.LRU缓存 方法一哈希表双向链表
使用一个哈希表和一个双向链表维护所有在缓存中的键值对
双向链表按照被使用的顺序存储了这些键值对靠近头部的键值对是最近使用的而靠近尾部的键值对是最久使用的哈希表即为普通的哈希映射通过缓存数据的键映射到其在双向链表中的位置
这样以来我们首先使用哈希表进行定位找出缓存项在双向链表中的位置随后将其移动到双向链表的头部即可在O(1)的时间内完成get或者put操作具体方法如下 对于get操作首先判断key是否存在 如果key不存在则返回-1如果key存在则key对应的节点是最近被使用的节点通过哈希表定位到该节点在双向链表中的位置并将其移动到双向链表的头部 最后返回该节点的值 对于put操作首先判断key是否存在 如果key不存在使用key和value创建一个新的节点在双向链表的头部添加该节点并将key和该节点添加进哈希表中然后判断双向链表的节点数是否超出容量如果超出容量则删除双向链表的尾部节点并删除哈希表中对应的项如果key存在则与get操作类似先通过哈希表定位再将对应的节点的值更新为value并将该节点移到双向链表的头部
class LRUCache {class DLinkedNode{int key;int value;DLinkedNode prev;DLinkedNode next;public DLinkedNode(){}public DLinkedNode(int _ket,int _value){key _ket;value _value;}}private MapInteger,DLinkedNode cache new HashMapInteger,DLinkedNode();private int size;private int capacity;private DLinkedNode head,tail;public LRUCache(int capacity) {this.size 0;this.capacity capacity;//使用伪头部和伪尾部节点head new DLinkedNode();tail new DLinkedNode();head.next tail;tail.prev head;}public int get(int key) {DLinkedNode node cache.get(key);if(node null){return -1;}//如果key存在先通过哈希表定位再移到头部moveToHead(node);return node.value;}public void put(int key, int value) {DLinkedNode node cache.get(key);if(node null){//如果key不存在创建一个新节点DLinkedNode newNode new DLinkedNode(key,value);//添加进哈希表cache.put(key,newNode);//添加至双向链表的头部addToHead(newNode);size;if(size capacity){//如果超出容量删除双向链表的尾部节点DLinkedNode tail removeTail();//删除哈希表中对应的项cache.remove(tail.key);--size;}}else{//如果key存在先通过哈希表定位再修改value,并移到头部node.value value;moveToHead(node);}}private void addToHead(DLinkedNode node){node.prev head;node.next head.next;head.next.prev node;head.next node;}private void removeNode(DLinkedNode node){node.prev.next node.next;node.next.prev node.prev;}private void moveToHead(DLinkedNode node){removeNode(node);addToHead(node);}private DLinkedNode removeTail(){DLinkedNode 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);*/
