LRU（最近最少使用）缓存

这道题是 LeetCode 中的第 146 号问题。LRU（Least Recently Used） 对计算机科班出身的同学应该不会陌生，那么今天就自己动手实现一个 LRU。

这是题目给出的模版：

class LRUCache {

    public LRUCache(int capacity) {

    }
    
    public int get(int key) {

    }
    
    public void put(int key, int value) {

    }
}

/**
 * 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);
 */
 
 特殊要求：get 和 put 方法都要是 O(1) 的时间复杂度

首先我们可以很容易想到，用 HashMap 来存储 LRUCache 的 <key, value> 对。

但是仅用简单的 HashMap<Integer, Integer> 是不行的，因为你需要保证「最近最少使用」。那怎么保证「最近最少使用」这一特性呢？有一个思路是：使用一种线性的数据结构来维护这个特性，让这个线性结构满足：越靠近头部就说明越是最近被用到的。相反，越靠近尾部就说明越是最久没被用到的。那么当超出缓存 capacity 以后，直接删除尾部值就相当于删除了最久没使用的。

照这样描述很容易想到这个线性结构可以是链表。而且需要该链表支持如下方法：头部添加结点、删除结点、删除尾结点、找到结点并将其移动到头部。

但是不要忘了，题目还要求 O(1) 的时间复杂度。显然在单链表中查找一个值的时间复杂度时 O(n) 的，是不满足 O(1) 时间复杂度的。

那么为了满足这个条件我们可以将单链表改为「双向链表」。

为什么选择双向链表呢？

双向链表可以在 O(1) 的时间复杂度：在头部添加结点、删除结点、删除尾结点。同时「找到结点并将其移动到头部」可以通过 「删除结点 + 头部添加结点」来实现。

Tips：建议使用带虚拟头、尾结点的双向量表

那么我们首先根据上面关于双向链表的描述将其相关的数据结构和方法写出来。

class DLinkedNode{
    int key;
    int value;
    DLinkedNode prev, next;

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

private DLinkedNode dummyHead, dummyTail;

private void addToHead(DLinkedNode node) {
    dummyHead.next.prev = node;
    node.next = dummyHead.next;
    dummyHead.next = node;
    node.prev = dummyHead;
}

private void removeNode(DLinkedNode node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

private DLinkedNode removeTail() {
    DLinkedNode tail = dummyTail.prev;

    removeNode(tail);

    return tail;
}

private void moveToHead(DLinkedNode node) {
    removeNode(node);
    addToHead(node);
}

现在我们的 HashMap 存的不再是 <Integer, Integer> 了，而是 <Integer, DLinkedNode>。

你可能会问，那 value 存哪去了？答案是存在了 DlinkedNode 中的 value 中了。DlinkedNode 中包含了 key 和 value。

数据结构选好了，实现 LRU 的思路其实是很简单的。照着题目中的文字描述就可以写出伪代码。

get 方法的伪代码是：

if (key 在 cache 中) {
     返回 key 对应的 value 值
     将双向链表中的 key 对应的结点移动到链表头部
} else {
     return -1;
}

put 方法的伪代码是：

if (key 在 cache 中) {
    将双向链表中的 key 对应的结点移动到链表头部
    更新 cache 中 key 对应的结点
} else {
    为新来的创建一个对象
    将新对象添加到 cache 中
    将新对象添加到双向链表的头部
    维护 size++

    if (size > capacity) {
        删除尾结点
        在 cache 中删除尾结点
        维护 size--
    }
}

根据以上伪代码，写出完整的代码：

class LRUCache {
    // 双向链表
    class DLinkedNode{
        int key;
        int value;
        DLinkedNode prev, next;

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

    private Map<Integer, DLinkedNode> cache;
    private int size;
    private int capacity;
    private DLinkedNode dummyHead, dummyTail;

    public LRUCache(int capacity) {
        cache = new HashMap<>();
        dummyHead = new DLinkedNode();
        dummyTail = new DLinkedNode();

        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;

        size = 0;
        this.capacity = capacity;
    }
    
    public int get(int key) {
        DLinkedNode node = cache.get(key);

        if (node != null) {
            moveToHead(node);

            return node.value;
        }

        return -1;
    }
    
    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);

        if (node == null) {
            node = new DLinkedNode(key, value);

            addToHead(node);
            cache.put(key, node);
            size++;

            if (size > capacity) {
                DLinkedNode tailNode = removeTail();
                cache.remove(tailNode.key);
                size--;
            }
        } else {
            node.value = value;
            moveToHead(node);
            // cache.put(key, node);
        }
    }

    // 双向链表有关操作
    private void addToHead(DLinkedNode node) {
        node.next = dummyHead.next;
        dummyHead.next.prev = node;
        dummyHead.next = node;
        node.prev = dummyHead;
        
    }

    private void removeNode(DLinkedNode node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;   
    }

    private void moveToHead (DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
        DLinkedNode node = dummyTail.prev;
        removeNode(node);

        return node;
    }
}