题目

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

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

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

解题思路

见书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);
        
    }
}