Leetcode 146. LRU 缓存机制以及 LRU算法实现概述

- 日理万妓 2022-09-03 07:21 171阅读 0赞

## 题目 ##

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。  
实现 **LRUCache** 类：

*  `LRUCache(int capacity)` 以正整数作为容量 `capacity` 初始化 LRU 缓存
 *  `int get(int key)` 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 *  `void put(int key, int value)` 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

#### 示例： ####

##### 输入 #####

["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 <= 10000  
0 <= value <= 105  
最多调用 2 \* 105 次 get 和 put

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/lru-cache  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 思路 ##

#### LRU算法 ####

简单点讲，LRU算法就是最近最久未使用算法，即当我们必须删除时，考虑删除最近最久未使用的即可。

除此之外，需要注意两个点，第一个点是，根据LRU算法，无论get还是put操作，被操作的点都应该放到前面，算做是“最近使用的”

由前面也可以知道第二个点，即题目中所给的示例并不是真的顺序，比如  
![在这里插入图片描述][d5837221758f4f069eb5fd03a5c321d3.png]  
put（2，2）后 真正顺序应该是2=2，1=1

#### 为什么需要哈希表？ ####

哈希表可以帮助我们实现查找O(1)的时间复杂度。

#### 为什么需要双向链表？ ####

需要删除操作。删除⼀个节点不光要得到该节点本⾝的指针，也需要操作其前驱节  
点的指针，⽽双向链表才能⽀持直接查找前驱，保证操作的时间复杂度O(1) 。

## Java实现 ##

我们先手动实现一下双向链表

class Node {
        
        public int key, val;
        public Node next, prev;
    
        public Node(int k, int v) {
        
            this.key = k;
            this.val = v;
        }
    
    }
    
    class DoubleList {
        
        private Node head;
        private Node tail;
        private int size;
        public DoubleList() {
        
            head = new Node(0,0);
            tail = new Node(0,0);
            head.next = tail;
            tail.prev = head;
        }
    
        public void addFirst(Node x) {
        
            x.prev = head;
            x.next = head.next;
            head.next.prev = x;
            head.next = x;
            size++;
        }
        
        public void remove(Node x) {
        
            x.prev.next = x.next;
            x.next.prev = x.prev;
            size--;
        }
    
        public Node removeLast() {
        
            Node result = tail.prev;
            remove(result);
            return result;
        }
    
        public int size() {
        
            return size;
        }
    
    }

之后结合hashmap就可以实现LRU缓存机制了！

import java.util.HashMap;
    import java.util.Map;
    
    //leetcode submit region begin(Prohibit modification and deletion)
    class LRUCache {
        
        private Map<Integer,Node> map ;
        DoubleList cache ;
        private int maxSize;
        public LRUCache(int capacity) {
        
            map = new HashMap<>();
            maxSize = capacity;
            cache = new DoubleList();
        }
        // 2,1
        public int get(int key) {
        
            if(map.containsKey(key))
            {
        
                int result = map.get(key).val;
                Node node = map.get(key);
                // 移动到开头
                cache.remove(node);
                cache.addFirst(node);
                map.replace(node.key,node);
                return result;
            }
    
            return -1;
    
        }
    
        public void put(int key, int value) {
        
            // 若已经存在，更新value即可
            if(map.containsKey(key))
            {
        
                // 移动到开头
                Node t = map.get(key);
                cache.remove(t);
                cache.addFirst(t);
                t.val = value;
    
            }else{
        // 不存在，则插入
                // 若已满，删除最后一个结点
                if(cache.size() == maxSize)
                {
        
                    Node lastNode = cache.removeLast();
                    map.remove(lastNode.key);
                }
                // 插入
                Node t = new Node(key,value);
                // 加到头部
                cache.addFirst(t);
                map.put(key,t);
            }
        }
    }

[d5837221758f4f069eb5fd03a5c321d3.png]: /images/20220829/f0e3ec658b534319b4e6b513dd7e835e.png