146. LRU 缓存机制（数据结构系列）

朴灿烈づ我的快乐病毒、 2023-10-05 20:16 15阅读 0赞

#### 146. LRU 缓存机制 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

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

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

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]

## 解题思路 ##

见书217面

## 代码 ##

**①使用了LinkedHashMap**

class LRUCache {
        
        int cap;//最大容量缓存
        LinkedHashMap<Integer, Integer> cache = new LinkedHashMap();
    
        public LRUCache(int capacity) {
        
            this.cap = capacity;
        }
    
        public int get(int key) {
        
            if (!cache.containsKey(key)) {
        
                return -1;
            }
            //key存在就把key提升为最近使用
            makeRecently(key);
    
            return cache.get(key);
        }
    
        public void put(int key, int value) {
        
            if (cache.containsKey(key)) {
        //key存在是覆盖的之前的key的位置，不用判断容量
                //修改key的值
                cache.put(key, value);
                //然后将key提升为最近使用的
                makeRecently(key);
                return;
            }
            //如果后台队列已经满了，就要排除最近最久没使用的
            if (cache.size() >= this.cap) {
        
                //链表头部就是最久未使用的key，因为是从链表尾部插入元素的
                int oldestKey = cache.keySet().iterator().next();
                cache.remove(oldestKey);
            }
            //将新的key添加到链表尾部
            cache.put(key, value);
    
    
        }
    
        public void makeRecently(int key) {
        
            int val = cache.get(key);
            //删除key再重新插入，就在队尾了
            cache.remove(key);
            cache.put(key, val);
        }
    }
    
    /**
     * 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);
     */

**②不使用内置的LinkedHashMap**

class LRUCache {
        
    
       /**
         * 创建双链表的基石
         */
        class Node {
        
            public int key;
            public int val;
            public Node next;
            public Node prev;
    
            public Node(int key, int val) {
        
                this.key = key;
                this.val = val;
            }
        }
    
        /**
         * 双向链表
         */
        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;
                size = 0;
            }
    
            /*
            在链表尾部添加节点x，时间复杂度是O(1)
            发现没有，在这里是给尾部插入x，用到的节点就只有tail和x，没有出现head
             */
            public void addLast(Node x) {
        
                x.prev = tail.prev;
                x.next = tail;
                tail.prev.next = x;
                tail.prev = x;
                size++;
            }
    
            /*
            删除链表中的节点x
            之和x有关，所以只出现了x
             */
            public void remove(Node x) {
        
                x.prev.next = x.next;
                x.next.prev = x.prev;
                size--;
            }
    
            /*
            删除链表中的第一个节点，并且返回该节点
             */
            public Node removeFirst() {
        
                if (head.next == tail) {
        
                    return null;
                }
                Node first = head.next;//注意！head是表头，并不是第一个节点
                remove(first);
                return first;
            }
    
            /*
            返回链表的长度
             */
            public int size() {
        
                return size;
            }
    
    
        }
    
        //哈希表和双向链表配合使用
        private HashMap<Integer, Node> map;
        private DoubleList cache;
        //最大容量
        private int cap;
    
        public LRUCache(int capacity){
        
            this.cap=capacity;
            map=new HashMap<>();
            cache=new DoubleList();
        }
    
        /**
         * 将某个key提升为最近使用的
         */
        private void makeRecently(int key){
        
            Node x=map.get(key);
            cache.remove(x);
            cache.addLast(x);
        }
    
        /**
         * 添加最近使用的元素
         */
        private void  addRecently(int key,int val){
        
            Node x = new Node(key, val);
            //链表的尾部就是最近使用的元素
            cache.addLast(x);
            //记住要在map中存放对应的映射，方便快速找到该节点
            map.put(key,x);
        }
    
        /**
         * 删除某一个key
         */
        private  void deleteKey(int key){
        
            Node x = map.get(key);
            cache.remove(x);
            //map的映射关系也记得要删除
            map.remove(key);
        }
    
        /**
         * 删除最近最久未使用元素
         */
        private  void removeLeastRecently(){
        
            //链表的第一个元素就是最近最久未使用的元素
            Node first = cache.removeFirst();
            //同时删除map中对应的映射
            map.remove(first.key);
        }
        
        
        /*以下就是向外暴露的方法 */
    
        public  int get(int key){
        
            if (!map.containsKey(key)){
        
                return  -1;
            }
            makeRecently(key);
            return map.get(key).val;
        }
        
        public  void put(int key,int val){
        
            if (map.containsKey(key)){
        
                //删除旧的数据
                deleteKey(key);
                //添加新插入的数据为最近使用的数据
                addRecently(key, val);
                return;
            }
            
            if (cache.size()==cap){
        //达到了最大容量
                //LRU淘汰
                removeLeastRecently();
            }
            addRecently(key, val);
            
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210223212049686.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70