题目链接

146. LRU 缓存

题目描述

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

实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value)如果关键字key已经存在，则变更其数据值；如果关键字不存在，则插入该组「key-value」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

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

解题思路

1. 使用 LinkedHashMap

本题需要借助「双向链表 + 哈希表」的数据结构，双向链表可以维护缓存中元素的顺序，哈希表可以加快向缓存中添加元素以及从缓存中获取元素的速度，使得 get 和 put 的以 O(1) 的平均时间复杂度运行。

Java 中提供了LinkedHashMap底层封装了「双向链表 + 哈希表」可以直接使用。

LinkedHashMap 的排列顺序

LinkedHashMap中存在一个名为accessOrder的成员变量，默认值为false，它的作用如下：

当accessOrder为false时，新元素会插入到链表尾部；当再次读取该元素时，并不会改变该元素的排列顺序。（使LinkedHashMap按照插入顺序排序）
当accessOrder为true时，新元素会插入到链表尾部；当再次读取该元素时，会将该元素移动到链表尾部。（使LinkedHashMap按照读取顺序排序）
LinkedHashMap 的构造函数

无参构造函数，直接调用父类HashMap的构造函数。

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {}
/**
 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
 * with the default initial capacity (16) and load factor (0.75).
 */
public LinkedHashMap() {
    super();
    accessOrder = false;
}

可以设置排列顺序的构造函数。

如果想实现 LRU 缓存，需要让LinkedHashMap按照读取顺序排列，所以需要将accessOrder设置为true。

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
  super(initialCapacity, loadFactor);
  this.accessOrder = accessOrder;
}

LinkedHashMap 的回调函数

在每次向 LinkedHashMap 中访问、插入、删除元素后，都会调用某个函数来维护双向链表中节点的顺序，这些函数如下：

**void **afterNodeAccess**_(_**Node**_<_**K,V**_> _**e**_) {}_**

在访问元素之后，将该元素放到双向链表的尾部，该函数只有在accessOrder设置为true时才会执行。

**void **afterNodeInsertion**_(_boolean **evict**_) {}_**

在插入新元素之后，调用该函数来移除最久未使用的元素，默认情况下不会删除任何元素。

**void **afterNodeRemoval**_(_**Node**_<_**K,V**_> _**e**_) {}_**

在删除元素之后（从 map 中），将元素从双向链表中删除。

向 LinkedHashMap 插入元素的流程

向LinkedHashMap中添加元素的流程（这里我们假设每次插入的元素都不在 HashMap 中）：

调用继承自父类的put()方法，put()方法会调用putVal()方法，然后调用newNode()方法，该方法在LinkedHashMap中被重写。
newNode()方法调用linkNodeLast()方法，将元素按照插入顺序添加到LinkedHashMap中，每个新元素都插入到链表尾部。
在putVal()方法最后（也就是插入元素后）会调用afterNodeInsertion()方法，该方法会根据removeEldestEntry()方法的返回结果来决定是否移除最久未使用的元素。
- removeEldestEntry()方法默认返回false，也就是不删除任何元素。该函数用来实现自定义的缓存策略。 ```java public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }

Node newNode(int hash, K key, V value, Node e) { LinkedHashMap.Entry p = new LinkedHashMap.Entry(hash, key, value, e); linkNodeLast(p); return p; }

// link at the end of list private void linkNodeLast(LinkedHashMap.Entry p) { LinkedHashMap.Entry last = tail; tail = p; if (last == null) head = p; else { p.before = last; last.after = p; } }

void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } }

protected boolean removeEldestEntry(Map.Entry eldest) { return false; }

将`accessOrder`设置为`true`后，调用`get(key)`方法后会将 key 所对应的元素移动到链表尾部。这样实现了将元素按照**读取顺序**排列。

- `get()`方法（也就是访问某个元素后）会调用`afterNodeAccess()`来实现将某个节点移动到链表尾部的逻辑。
```java
public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

LinkedHashMap 实现 LRU 代码实现

有了上面的知识，使用 LinkedHashMap 实现 LRU 的流程如下：

构造LinkedHashMap时，将accessOrder设置为true。
重写removeEldestEntry()方法的逻辑，也就是什么情况下需要删除最久未使用的元素。根据题目要求可知，当缓存已满时需要删除最久未使用的元素。
题目要求当某个元素不存在缓存中时，返回 -1，可以通过getOrDefault()方法来实现。

最终代码如下：

public class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;

    public LRUCache(int capacity) {
        // 构造函数，设置 accessOrder 为 true 
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        // 当缓存容量已满时，就要删除最久未使用的元素
        // 为什么不是 size == capacity ? 因为 size 是先自增的
        return super.size() > capacity;
    }
}

2. 哈希表 + 手写双向链表

LRU 缓存可以通过哈希表 + 双向链表实现，在面中通常会被要求自己实现简单的双向链表。

双向链表按照被访问的顺序存储键值对。规定：靠近头部的键值对是最近最久未使用的，靠近尾部的键值对是最近使用的。
通过哈希表来快速获取键值对在双向链表中的位置。

这样一来，我们首先使用哈希表进行定位，找出缓存数据在双向链表中的位置，随后将其移动到链表尾部，即可在 LeetCode146. LRU 缓存 - 图1 的时间内完成 get 或者 put 操作。具体过程如下：

对于get操作，首先判断key是否存在：
- 如果key不存在，返回 -1；
- 如果key存在，则key对应的节点就是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表尾部，最后返回该节点的值。
对于put操作，首先判断key是否存在：
- 如果key存在，先通过哈希表定位，将节点值更新为value，然后移动到双向链表尾部；
- 如果key不存在，判断缓存容量是否已满，如果已满，则删除最久未使用的节点（双向链表的头部节点），并删除哈希表中对应的项。然后使用key和value创建一个新的节点，在双向链表尾部添加该节点，并将key和该节点添加进哈希表中。

在双向链表实现中，使用伪头部和伪尾部标记节点，这样在添加节点和删除节点时就不需要检查相邻的节点的是否存在，减少了边界条件的判断。

代码实现：

class LRUCache {
    private class DoubleLinkedList {
        private int key;
        private int value;
        private DoubleLinkedList pre;
        private DoubleLinkedList next;
        public DoubleLinkedList() {}
        public DoubleLinkedList(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    private HashMap<Integer, DoubleLinkedList> map;
    private int capacity;
    private DoubleLinkedList head;
    private DoubleLinkedList tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new DoubleLinkedList();
        tail = new DoubleLinkedList();
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            move2Tail(key);
            return map.get(key).value;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            map.get(key).value = value;
            move2Tail(key);
            return;
        }
        if (map.size() == capacity) {
            DoubleLinkedList node = removeHead();
            map.remove(node.key);
        }
        DoubleLinkedList node = new DoubleLinkedList(key, value);
        add2Tail(node);
        map.put(key, node);
    }

    private void add2Tail(DoubleLinkedList node) {
        node.next = tail;
        node.pre = tail.pre;
        tail.pre.next = node;
        tail.pre = node;
    }

    private DoubleLinkedList removeHead() {
        DoubleLinkedList node = head.next;
        node.pre.next = node.next;
        node.next.pre = node.pre;
        node.next = null;
        node.pre = null;
        return node;
    }

    private void move2Tail(int key) {
        DoubleLinkedList node = map.get(key);
        node.pre.next = node.next;
        node.next.pre = node.pre;
        add2Tail(node);
    }
}

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

LeetCode146. LRU 缓存