LeetCode-146. LRU 缓存

ゝ一纸荒年。 2024-03-24 13:07 29阅读 0赞

#### 目录 ####

*   *  LRU理论
     *  题目思路
     *  代码实现一
     *  代码实现二

题目来源  
[146. LRU 缓存][146. LRU]

### LRU理论 ###

LRU 是 Least Recently Used 的缩写，这种算法认为最近使用的数据是热门数据，下一次很大概率将会再次被使用。而最近很少被使用的数据，很大概率下一次不再用到。当缓存容量的满时候，优先淘汰最近很少使用的数据。

假设现在缓存内部数据如图所示：  
**这里我们将列表第一个节点称为头结点，最后一个节点为尾结点。(可以想象成队列)**  
![在这里插入图片描述][8ef734033686442398314d6dc3d03901.png]

当调用缓存获取 key=1 的数据，LRU 算法需要将 1 这个节点移动到头结点，其余节点不变  
![在这里插入图片描述][b87d0c1df1374ed5a03dd5ee94513dc9.png]

然后我们插入一个 key=8 节点，此时缓存容量到达上限，所以加入之前需要先删除数据。由于每次查询都会将数据移动到头结点，未被查询的数据就将会下沉到尾部节点，尾部的数据就可以认为是最少被访问的数据，所以删除尾结点的数据。  
![在这里插入图片描述][8204ea9ff0924cfba0265018920c391e.png]  
然后我们直接将数据添加到头结点。  
![在这里插入图片描述][e6fe225f15d7475fa0db23745e33f2eb.png]  
这里总结一下 LRU 算法具体步骤：

*  新数据直接插入到列表头部
 *  缓存数据被命中，将数据移动到列表头部
 *  缓存已满的时候，移除列表尾部数据。

### 题目思路 ###

实现本题的两种操作，需要用到一个哈希表和一个双向链表。

### 代码实现一 ###

继承java自带的LinkedHashMap

class LRUCache extends LinkedHashMap<Integer,Integer>{
        
    
        private int capacity;
    
        public LRUCache(int capacity) {
        
            super(capacity,0.75F,true);
            this.capacity = capacity;
        }
        
        public int get(int key) {
        
            return super.getOrDefault(key,-1);
        }
        
        public void put(int key, int value) {
        
            super.put(key, value);
        }
    
        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        
            return size() > capacity; 
        }
    }
    
    /**
     * 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);
     */

![在这里插入图片描述][317c6b807637463ca6badc85d1d61452.png]

### 代码实现二 ###

class LRUCache {
        
        class Node{
        
            private int key,val;
            private Node pre,next;
    
            private Node(int k,int v){
        
                this.key = k;
                this.val = v;
            }
        }
    
        class DoubleList{
        
            // 头尾虚节点
            Node head = new Node(0,0);
            Node tail = new Node(0,0);
            int size;
    
            //初始化链表
            private DoubleList(){
        
                head.next = tail;
                tail.pre = head;
                size = 0;
            }
    
            //头插入
            void addFirst(Node n){
        
                head.next.pre = n;
                n.next = head.next;
                n.pre = head;
                head.next = n;
                size++;
            }
    
            //删除链表的某一个元素
            void remove(Node n){
        
                n.pre.next = n.next;
                n.next.pre = n.pre;
                size--;
            }
    
            //删除尾结点，并返回该节点
            Node removeLast(){
        
                Node res = tail.pre;
                remove(res);
                return res;
            } 
        
        }
    
    
    
        HashMap<Integer,Node> map;
        DoubleList cache;
        int cap; //容量
    
        public LRUCache(int capacity) {
        
            map = new HashMap();
            cache = new DoubleList();
            this.cap = capacity;
        }
        
        public int get(int key) {
        
            if(!map.containsKey(key)){
          //该节点不存在
                return -1;
            }
            Node res = map.get(key);
            cache.remove(res);
            cache.addFirst(res);
            return res.val;
            
        }
        
        public void put(int key, int value) {
        
            Node n = new Node(key,value);
            if(map.containsKey(key)){
          //若该节点已经存在
                cache.remove(map.get(key));
            }else if(map.size() == cap){
          //该节点不存在，但是cache已满
                Node last = cache.removeLast();
                map.remove(last.key);
            }
            cache.addFirst(n);
            map.put(key,n);
        }
    }
    
    /**
     * 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);
     */

![在这里插入图片描述][b9465edf4fb440f99e94f287ec0f8c48.png]

[146. LRU]: https://leetcode.cn/problems/lru-cache/
[8ef734033686442398314d6dc3d03901.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/ba3a245eeae14cb1b8ebdfccb7b5ef31.png
[b87d0c1df1374ed5a03dd5ee94513dc9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/d033999665744306aca66875a2945633.png
[8204ea9ff0924cfba0265018920c391e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/d4d4889eccb34fe6a27228f8c94f114e.png
[e6fe225f15d7475fa0db23745e33f2eb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/d2f8443abab942e98f917229c850b5b7.png
[317c6b807637463ca6badc85d1d61452.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/981dcca19ba046688d5a32766360d1dd.png
[b9465edf4fb440f99e94f287ec0f8c48.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/82c5a3116f3d40c3aaed430f38532293.png