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 Map<Integer,DLinkedNode> cache = new HashMap<Integer,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);*/