哈希 - 146. LRU 缓存机制 - 《算法刷题》

解法1：双向链表+哈希表，时间复杂度o(1)，空间复杂度o(n+n)

题目：运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例：

输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <= 104
最多调用 3 * 104 次 get 和 put
解法1：双向链表+哈希表，时间复杂度o(1)，空间复杂度o(n+n)

类比于LinkedHashMap，用哈希表存放key/value缓存，双向链表记录访问key的顺序
自定义双向链表，并且提供头尾两个虚节点，让head.next = tail,tail.prev = next
提供链表的头增、尾删以及删除一个节点等方法
get时，先从map中获取，如果结果为null，则返回-1；否则返回对应值，同时把该节点移动到链表头部
put时，根据key和value创建新节点，先从map中查询是否有该节点缓存，如果没有则新建一个节点，此时需要考虑是否超出容量的情况：
1. 没有超出容量，直接添加，且在双向链表中把它添加为头节点
2. 如果超出容量，则删除双向链表尾部节点，将该节点设置为头节点

put时，如果有当前节点存在，则直接覆盖对应节点的value，且把该节点设置为链表头节点 ```java class LRUCache { class MyDNode{

 int key;
 int val;
 MyDNode prev;
 MyDNode next;
 public MyDNode(int key,int val){
     this.key = key;
     this.val = val;
 }
 public MyDNode(){
 }

} MyDNode head; MyDNode tail; int capacity = 0; int size = 0; Map cache; public LRUCache(int capacity) {

 this.capacity = capacity;
 cache = new HashMap<>();
 head = new MyDNode();
 tail = new MyDNode();
 // 两个头尾虚节点，防止链表空的情况
 head.next = tail;
 tail.prev = head;

}

public int get(int key) {

 // 先从哈希表中获取
 MyDNode node = cache.get(key);
 // 获取不到，则返回-1
 if(node == null){
     return -1;
 }
 // 如果找到了，则返回对应值，且把该节点放入双向链表头部
 moveToHead(node);
 return node.val;

}

public void put(int key, int value) {

 // 从map先查询是否有该节点
 MyDNode node = cache.get(key);
 // 如果没有
 if(node == null){
      // 如果put后达到容量上限
     if(size == capacity){
         // 删除一个节点
         MyDNode removeNode = removeFromTail();
         size--;
         // 哈希表中也删除
         cache.remove(removeNode.key);
     }
     // 没有就创建新节点
     MyDNode newNode = new MyDNode(key,value);
     // 直接put进入哈希表中
     cache.put(key,newNode);
     size++;
     // 加入双向链表中
     addToHead(newNode);
 }else{// 如果找到了，则直接覆盖值且双向链表头部设置该节点
     node.val = value;
     moveToHead(node);
 }

}

public void addToHead(MyDNode node){

 // 把节点插入到虚节点头后
 node.prev = head;
 node.next = head.next;
 head.next.prev = node;
 head.next = node;

}

public void remove(MyDNode node){

 // 删除对应节点
 node.prev.next = node.next;
 node.next.prev = node.prev;

}

public void moveToHead(MyDNode node){

 // 删除对应节点后，从头再次添加
 remove(node);
 addToHead(node);

} public MyDNode removeFromTail(){

 // 删除尾虚节点的前一个节点
 MyDNode node = tail.prev;
 remove(node);
 return node;

}

} ```

146. LRU 缓存机制

解法1：双向链表+哈希表，时间复杂度o(1)，空间复杂度o(n+n)