146.LRU缓存
方法一：哈希表+双向链表
使用一个哈希表和一个双向链表维护所有在缓存中的键值对
- 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久使用的
- 哈希表即为普通的哈希映射，通过缓存数据的键映射到其在双向链表中的位置
这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在O(1)的时间内完成get或者put操作，具体方法如下：
-
对于get操作，首先判断key是否存在文章来源：https://www.toymoban.com/news/detail-744954.html
- 如果key不存在，则返回-1
- 如果key存在，则key对应的节点是最近被使用的节点，通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部， 最后返回该节点的值
-
对于put操作，首先判断key是否存在文章来源地址https://www.toymoban.com/news/detail-744954.html
- 如果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);
*/
到了这里，关于【LeetCode刷题-链表】--146.LRU缓存的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
