题解 | #设计LRU缓存结构#

基本思路

使用HashMap作为缓存，key就是传进来的key，但是value需要包装成一个双向链表的节点，通过双向链表连接HashMap中所有Entry的value，双向链表的头部节点表示最近使用的节点，尾部节点表示最近最少使用的节点，因此缓存满时移除的是尾部节点。

双向链表中的节点也需要保存key，因为在LRU缓存达到最大容量时，需要根据双向链表中尾部节点的key，来给HashMap移除这个键值对，此时双向链表也需要去掉这个最后的尾部节点。

双向链表应该有一个head指针和tail指针指向双向链表的第一个节点和最后一个节点，如果是链表中只有一个节点，则head指针和tail指针都指向该节点，但是要注意head指针的pre为null，tail指针的next为null，也就是说head和tail并不是相连的，不是循环链表。

无论是存取缓存都需要判断原缓存中是否有该key，在取缓存时没有该key则返回-1，如果有该key，则将该key移动到双向链表的头部，然后返回缓存中该key的value。

在存缓存时，如果原缓存中有该key，则将该key移动到双向链表头部，并更新缓存中该key的值，如果没有该key，需要将该key插入到链表头部，此时就需要判断缓存是否满了，如果缓存满了就需要移除尾部节点，然后再将该key插入链表头部。

size和capacity的类型应该是基本类型的int，使用Integer会导致最后一个用例过不了，不知道是什么原因。

此题还可以直接用JAVA的LinkedHashMap实现，但是面试可能需要自己写数据结构。

参考

参考题解一

参考题解二

import java.util.*;


public class Solution {
    // 双向链表节点，HashMap中key对应的value被封装成Node节点，通过双向链表可以实现移除最近未使用的元素。
    static class Node {  
        int key;
        int val;
        Node pre;
        Node next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
            this.pre = null;
            this.next = null;
        }
    }

    private HashMap<Integer, Node> mp;  // LRU缓存，value被封装成双向链表的Node
    // 下面两个类型不能用Integer，而是得用基本类型int，不然最后一个用例过不了
    private int size;  // LRU缓存中已经使用的容量
    private int capacity;  // LRU缓存中最大的容量
    private Node head;  // 由于需要实现双向链表，所以得有head指针记录头节点
    private Node tail;  // 由于需要实现双向链表，所以得有tail指针记录尾节点

    public Solution(int capacity) {
        // write code here
        this.mp = new HashMap<>();
        this.size = 0;
        this.capacity = capacity;
        this.head = null;
        this.tail = null;
    }

    public int get(int key) {
        // write code here
        if (!this.mp.containsKey(key)) {
            return -1;
        }

        makeRecently(key);
        return this.mp.get(key).val;
    }

    public void set(int key, int value) {
        // write code here
        if (this.mp.containsKey(key)) {  // 缓存中存在该key，进行更新操作
            makeRecently(key);
            this.mp.get(key).val = value;
            return;
        }

        if (this.size == capacity) {  // 缓存满了，先移除链表尾结点
            this.mp.remove(this.tail.key);
            this.tail = this.tail.pre;
            this.tail.next = null;
            this.size--;
        }

        // 将当前节点插入链表头部
        Node node = setNode(key, value);
        this.mp.put(key, node);
    }

    // 设置双向链表节点
    private Node setNode(int key, int value) {
        Node node = new Node(key, value);
        if (this.size == 0) {
            this.head = node;
            this.tail = node;
        }
        else {  // 新节点是插入头部，头部是最近使用的节点
            node.next = this.head;
            this.head.pre = node;
            this.head = node;
        }
        this.size++;

        return node;
    }

    // 使用过key，就要将key移动到双向链表节点的头部，作为最近使用的key
    private void makeRecently(int key) {
        Node node = this.mp.get(key);
        if (node != this.head) {  // 如果node不是头节点，就需要移动该节点到链表头部
            if (node == this.tail) {
                this.tail = this.tail.pre;
                this.tail.next = null;
            }
            else {  // 将当前节点移除链表
                node.pre.next = node.next;
                node.next.pre = node.pre;
            }

            node.next = this.head;
            node.pre = null;
            this.head.pre = node;
            this.head = node;
        }
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */