请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 105
  • 最多调用 2 * 105 次 get 和 put

思路

基本的想法是，用一个HashMap来存储键值对，再用一个LinkedList来存储访问序列。这样是可以做到get操作查询是的，由于我们每次put和get都要维护访问链，就导致时间复杂度增加至了。所以自己编写相应的数据结构来实现比较麻烦。

好消息是，Java为我们提供了一个非常有用的类LinkedHashMap。虽然LinkedHashMap增加了时间和空间上的开销，但是它通过维护一个额外的双向链表保证了迭代顺序。特别地，该迭代顺序可以是插入顺序，也可以是访问顺序。因此，根据链表中元素的顺序可以将LinkedHashMap分为：保持插入顺序的LinkedHashMap和保持访问顺序的LinkedHashMap，其中LinkedHashMap的默认实现是按插入顺序排序的。

LinkedHashMap增加了两个属性用于保证迭代顺序，分别是 双向链表头结点header 和 标志位accessOrder (值为true时，表示按照访问顺序迭代；值为false时，表示按照插入顺序迭代)。

/**
* The iteration ordering method for this linked hash map: {@code true}
* for access-order, {@code false} for insertion-order.
*
* @serial
*/
final boolean accessOrder;

LinkedHashMap 一共提供了五个构造函数，它们都是在HashMap的构造函数的基础上实现的，分别如下：

/**
* Constructs an empty insertion-ordered {@code LinkedHashMap} instance
* with the default initial capacity (16) and load factor (0.75).
*/
public LinkedHashMap() {
    super();
    accessOrder = false;
}

该构造函数意在构造一个指定初始容量和默认负载因子 (0.75)的空LinkedHashMap

/**
* Constructs an empty insertion-ordered {@code LinkedHashMap} instance
* with the specified initial capacity and a default load factor (0.75).
*
* @param  initialCapacity the initial capacity
* @throws IllegalArgumentException if the initial capacity is negative
*/
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

该构造函数意在构造一个指定初始容量和指定负载因子的空LinkedHashMap

/**
* Constructs an empty insertion-ordered {@code LinkedHashMap} instance
* with the specified initial capacity and load factor.
*
* @param  initialCapacity the initial capacity
* @param  loadFactor      the load factor
* @throws IllegalArgumentException if the initial capacity is negative
*         or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

该构造函数意在构造一个与指定Map具有相同映射的LinkedHashMap，其 初始容量不小于16（具体依赖于指定Map的大小），负载因子是 0.75，是 Java Collection Framework 规范推荐提供的，

/**
 * Constructs an insertion-ordered {@code LinkedHashMap} instance with
 * the same mappings as the specified map.  The {@code LinkedHashMap}
 * instance is created with a default load factor (0.75) and an initial
 * capacity sufficient to hold the mappings in the specified map.
 *
 * @param  m the map whose mappings are to be placed in this map
 * @throws NullPointerException if the specified map is null
 */
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

该构造函数意在构造一个指定初始容量和指定负载因子的具有指定迭代顺序的LinkedHashMap

/**
* Constructs an empty {@code LinkedHashMap} instance with the
* specified initial capacity, load factor and ordering mode.
*
* @param  initialCapacity the initial capacity
* @param  loadFactor      the load factor
* @param  accessOrder     the ordering mode - {@code true} for
*         access-order, {@code false} for insertion-order
* @throws IllegalArgumentException if the initial capacity is negative
*         or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

注意到我们在前面介绍的LinkedHashMap的五种构造方法，前四个构造方法都将accessOrder设为false，说明默认是按照插入顺序排序的；而第五个构造方法可以自定义传入的accessOrder的值，因此可以指定双向循环链表中元素的排序规则。特别地，当我们要用LinkedHashMap实现LRU算法时，就需要调用该构造方法并将accessOrder置为true。

所以我们可以直接使用LinkedHashMap，并指定它维护访问顺序，实现LRU算法。在本题中，我们还需要重写LinkedHashMap的removeEldestEntry方法。该方法的描述如下。

/**
* Returns {@code true} if this map should remove its eldest entry.
* This method is invoked by {@code put} and {@code putAll} after
* inserting a new entry into the map.  It provides the implementor
* with the opportunity to remove the eldest entry each time a new one
* is added.  This is useful if the map represents a cache: it allows
* the map to reduce memory consumption by deleting stale entries.
*
* @param    eldest The least recently inserted entry in the map, or if
*           this is an access-ordered map, the least recently accessed
*           entry.  This is the entry that will be removed it this
*           method returns {@code true}.  If the map was empty prior
*           to the {@code put} or {@code putAll} invocation resulting
*           in this invocation, this will be the entry that was just
*           inserted; in other words, if the map contains a single
*           entry, the eldest entry is also the newest.
* @return   {@code true} if the eldest entry should be removed
*           from the map; {@code false} if it should be retained.
*/
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
}

简单来说，就是若该方法返回true则会将访问链尾部的元素剔除。该方法的调用时机是每次put方法插入新元素之后。

class LRUCache {

    Map<Integer, Integer> cache = null;

    LinkedList<Integer> visit = new LinkedList<>();

    int capacity, size;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        cache = new LinkedHashMap<>(capacity << 2, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return cache.size() > capacity;
            }
        };
    }
    
    public int get(int key) {
        return cache.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        cache.put(key, value);
    }
}

复杂度

  • 时间复杂度：。
  • 空间复杂度：。