Java 实现 LRU 缓存模型

LRC 缓存模型其实是很常见的，像 InnoDB 的缓存池，虚拟内存的调度算法，重点是数据结构的实现，值得单独记录一下，对理解也有很大的帮助

LeetCode 地址

这道题其实更多的是考察数据结构和集合的使用，所以也放到了实现题这里

思路：
LRU 直译为最近最少未使用，要想实现首先要搞清它的特点

• 新进来的缓存结点放在最近被使用位
• 每被使用一次的结点放在最近被使用位

根据这两个特点我们可以使用链表存储每一个缓存结点，新放入或者被使用的结点直接放在链表头，当需要淘汰最近最少未使用的结点时直接去掉尾结点就可以，为了存取方便这里使用双向链表

接下来再分析题目需要我们实现的方法

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

根据存取特点，我们需要使用 Map 存储对应关系；根据构造方法，我们在 put 时还应根据 capacity 的值动态决定是否移除尾结点

代码：

class LRUCache {
    // 结点结构 
    class DLinkedNode {
        private int key;    // 此处的 key 方便在链表和 Map 同时移除 
        private int value;
        DLinkedNode prev;
        DLinkedNode next;

        public DLinkedNode() {
        }

        public DLinkedNode(int _key, int _value) {
            key = _key;
            value = _value;
        }
    }

    Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;   // 当前存储大小 
    private int capacity;   // 指定容量 
    private DLinkedNode head, tail;

    // 默认构造器 
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        // 先判断是否存在，存在更改值，不存在放入 
        if (node == null) {
            DLinkedNode newNode = new DLinkedNode(key, value);

            cache.put(key, newNode);
            // 放入后置于链表头 
            addHead(newNode);
            ++size;
            // 超过最大容量清除 
            if (size > capacity) {
                DLinkedNode reTail = removeTail();
                cache.remove(reTail.key);
                --size;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    public void addHead(DLinkedNode node) {
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
        node.prev = head;
    }

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

    public void moveToHead(DLinkedNode node) {
        removeNode(node);
        addHead(node);
    }

    public DLinkedNode removeTail() {
        DLinkedNode result = tail.prev;
        removeNode(result);
        return result;
    }
}