LeetCode-146. LRU 缓存

LRU理论

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

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

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

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

这里总结一下 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);
 */

在这里插入图片描述

代码实现二

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);
 */