Java 实现 LRU 算法

力扣题目：146. LRU 缓存

最近最少使用算法。一个队列，将最近使用的元素放到队列的头部，当队列长度不够时，移除队列的最后一个元素，也就是最近最少使用的元素。

投机取巧解法（最好还是自己实现），利用 Java 的 linkedHashMap 已经实现好的方法，所以直接继承 linkedHashMap 为父类即可。

有兴趣可以自己阅读 linkedHashMap 源码。重点关注这三个方法：

• afterNodeAccess()：访问元素之后，将元素放到双向链表的尾部
• afterNodeRemoval()：删除元素之后，同时将元素也从双向链表中删除
• afterNodeInsertion()：插入元素之后，是否需要移除最近最少使用的元素

class LRUCache extends linkedHashMap {

    
    private int capacity;

    
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }
    
    
    public int get(int key) {
        return (int) super.getOrDefault(key, -1);
    }
    
    
    public void put(int key, int value) {
        super.put(key, value);
    }

    
    @Override
    public boolean removeEldestEntry(Map.Entry eldest) {
        return super.size() > capacity;
    }
}

很重要，面试官需要你写出来的是这个，要能够手写！

class LRUCache {

    
    private int size;

    
    private int capacity;

    
    private Map cache;

    
    private DoublelinkedNode head;

    
    private DoublelinkedNode tail;

    
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new DoublelinkedNode();
        this.tail = new DoublelinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    
    
    public int get(int key) {
        DoublelinkedNode node = this.cache.get(key);

        // 如果要获取的节点不存在
        if (node == null) {
            return -1;
        }
        // 移动到双向链表头部
        moveToHead(node);
        // 返回值
        return node.value;
    }
    
    
    public void put(int key, int value) {
        DoublelinkedNode node = cache.get(key);
        // 如果元素不存在
        if (node == null) {
            node = new DoublelinkedNode(key, value);
            // 添加到哈希表中
            cache.put(key, node);
            // 双向链表长度加 1
            size++;
            // 添加到双向链表头部
            addToHead(node);
            // 如果长度大于容量，说明要删除元素了
            if (size > capacity) {
                // 从双向链表中删除最后一个元素
                DoublelinkedNode tail = removeTail();
                // 同时从哈希表中删除对应的元素
                cache.remove(tail.key);
                // 长度减 1
                size--;
            }
        // 如果元素存在
        } else {
            // 修改值
            node.value = value;
            // 移动到双向链表头部
            moveToHead(node);
        }
    }

    
    class DoublelinkedNode {

        
        int key;

        
        int value;

        
        DoublelinkedNode prev;

        
        DoublelinkedNode next;

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

    
    private void addToHead(DoublelinkedNode node) {
        node.next = head.next;
        node.prev = head;
        node.next.prev = node;
        head.next = node;
    }

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

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

    
    private DoublelinkedNode removeTail() {
        DoublelinkedNode node = this.tail.prev;
        removeNode(node);
        return node;
    }
}