题解 | 实现一个LRU 缓存

题目描述：

设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。

它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

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

题解思路：

通过一个哈希表 + 一个双向链表实现，时间复杂度（O(1)）。 双向链表的头部存放最近访问的节点，尾部存放最久未访问的节点

• 对于get()操作：
  • 先判断哈希表中是否存在key。
  • 如果不存在则直接返回-1；
  • 如果存在，则通过hashmap定位到链表中key对应的节点，删除该节点，然后在链表头部插入一个相同的节点（通过删除+添加 替换移动操作，因为移动时间复杂度更高），返回key对应节点的value值。
• 对于put()操作：
  • 先判断哈希表中是否存在key。
  • 如果不存在，则在链表头部插入新节点（同时往hashmap中添加key），再判断链表长度是否超过缓存容量上限，如果超了，则删掉链表的尾部节点（同时删除hashmap中对应的key），如果没超，不做任何处理；
  • 如果存在，则通过hashmap定位到链表中key对应的节点，更新该节点的value为put的新value值，删掉，然后在头部插入一个相同的节点。

核心实现代码：

class LRUCache {

    // 定义链表节点类
    class LinkedNode{
        int key;
        int value;
        LinkedNode pre;
        LinkedNode next;

        public LinkedNode(){}

        public LinkedNode(int key, int value){
            this.key = key;
            this.value = value;
        }
    }

    private Map<Integer, LinkedNode> cacheMap = new HashMap<>(); // 定义一个Hashmap
    private int size; // 链表长度
    private int capacity; // 缓存容量
    private LinkedNode head; // 链表头节点
    private LinkedNode tail; // 链表尾节点
    
    // LRUCache的构造函数
    public LRUCache(int capacity) {
        this.size = 0; // 链表初始长度为0
        this.capacity = capacity;
        head = new LinkedNode(); // 虚拟头节点
        tail = new LinkedNode(); // 虚拟尾节点
        head.next = tail;
        tail.pre = head;
    }
    
    // LRUCache缓存的get方法
    public int get(int key) {
        LinkedNode node = cacheMap.get(key);
        if(node == null){
            return -1;
        }
        moveNode(node);
        return node.value;
    }
    
    // LRUCache缓存的put方法
    public void put(int key, int value) {
        LinkedNode node = cacheMap.get(key);
        if(node == null){
            LinkedNode newNode = new LinkedNode(key, value); // 新添加的节点
            cacheMap.put(key, newNode); // 别忘记更新cachaMap
            addNodeToHead(newNode);
            size++; // 插入新节点，链表长度+1
            if(size > capacity){ // 如果链表长度超过缓存容量上限，则删除链表尾部的节点
                LinkedNode node2 = removeTailNode();
                cacheMap.remove(node2.key);
                size--;
            }
        }else{
            node.value = value; // 先更新cachaMap中对应节点的value值
            moveNode(node); // 移动节点
        }
    }

    // 移动节点到链表头部
    public void moveNode(LinkedNode node){
        removeNode(node); // 先删除节点
        addNodeToHead(node); // 再在链表头部添加相同内容的节点
    }

    // 删除链表中某个节点
    public void removeNode(LinkedNode node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    // 在链表头部添加一个节点
    public void addNodeToHead(LinkedNode node){
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }

    // 删除链表尾部节点，并返回
    public LinkedNode removeTailNode(){
        LinkedNode tailNode = tail.pre;
        removeNode(tailNode);
        return tailNode;
    }
}