题目描述

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

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

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

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

https://leetcode-cn.com/problems/lru-cache/

解法1

使用链表维护Cache的顺序，使用Map记录Key-value。如果Key被访问或者被更新，则将key所对应的链表节点调整至链表第一个。如果发生插入操作，则新建节点放置链表头部，并向Map插入记录。如果遇到发生淘汰，则将链表中的节点和Map中的KV对一同删除。

该方法有一个缺点，当查找链表中Key所对应的节点需要顺序扫描。

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;

class LRUCache {
    int capacity;
    LinkedList<Integer> link;
    Map<Integer, Integer> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        link = new LinkedList<>();
        map = new HashMap<>(capacity);
    }

    public int get(int key) {
        Integer val = map.get(key);

        if (val == null)
            return -1;

        reorder(key);

        return val;
    }

    /**
     * 将key对应的node提到链表第一个
     *
     * @param key
     */
    void reorder(int key) {
        link.remove((Integer) key); // 导致顺序遍历链表
        link.add(0, key);
    }

    public void put(int key, int value) {
        // 替换已存在的元素，并且要把该元素拉到第一个位置
        if (map.containsKey(key)) {
            reorder(key);
            map.put(key, value);
        } else {
            if (capacity > map.size()) {
                map.put(key, value);
                link.add(0, key);
            } else {

                // 淘汰LRU
                int removedKey = link.removeLast();
                map.remove(removedKey);

                link.add(0, key);
                map.put(key, value);
            }
        }
    }
}

解法2

为了实现O(1)的时间复杂度，我使用了两个Map。第一个Map<Key, Node<Value>>保存Key与Key对应的双向链表的节点，这有助于快速根据Key取出Value，并调整节点的位置。另一个Map<Node<Value>, Key>保存了链表节点所对应的Key，这有助于快速找到被淘汰的节点以及对应的Key。

import java.util.*;

class LRUCache {
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

    int capacity;
    Map<Integer, Node<Integer>> key_node;
    Map<Node<Integer>, Integer> node_key;
    Node<Integer> head;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        key_node = new HashMap<>(capacity);
        node_key = new HashMap<>(capacity);
        head = new Node<>(null, null, null);
        head.next = head;
        head.prev = head;
    }

    public int get(int key) {
        Node<Integer> val = key_node.get(key);

        if (val == null)
            return -1;

        reorder(key);

        return val.item;
    }

    /**
     * 将key对应的node提到链表第一个
     *
     * @param key
     */
    private void reorder(int key) {
        Node<Integer> node = key_node.get(key);

        if (node.prev != null)
            node.prev.next = node.next;

        if (node.next != null)
            node.next.prev = node.prev;

        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    public void put(int key, int value) {
        // 替换已存在的元素，并且要把该元素拉到第一个位置
        Node<Integer> node = key_node.get(key);

        if (node != null) {
            reorder(key);
            node.item = value;
        } else {
            if (capacity > key_node.size()) {
                node = new Node<>(head, value, head.next);

                head.next.prev = node;
                head.next = node;

                key_node.put(key, node);
                node_key.put(node, key);
            } else {

                // 淘汰LRU, 不需要新建节点，直接将被淘汰的节点重用
                Node<Integer> removedNode = head.prev;
                int removedKey = node_key.put(removedNode, key);

                reorder(removedKey);
                key_node.remove(removedKey);

                removedNode.item = value;
                key_node.put(key, removedNode);
            }
        }
    }
}