哈希表题目：LRU 缓存

文章目录

• 题目
• • 标题和出处
  • 难度
  • 题目描述
• 前言
• 解法

题目

标题和出处

标题：LRU 缓存

出处：146. LRU 缓存

难度

7 级

题目描述

要求

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

实现 LRUCache \texttt{LRUCache} LRUCache 类：

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

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

示例

示例 1：

输入：
["LRUCache",   "put",   "put",   "get",   "put",   "get",   "put",   "get",   "get",   "get"] \texttt{["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]} ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2],   [1,   1],   [2,   2],   [1],   [3,   3],   [2],   [4,   4],   [1],   [3],   [4]] \texttt{[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]} [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出：
[null,   null,   null,   1,   null,   -1,   null,   -1,   3,   4] \texttt{[null, null, null, 1, null, -1, null, -1, 3, 4]} [null, null, null, 1, null, -1, null, -1, 3, 4]
解释：
LRUCache   lruCache   =   new   LRUCache(2); \texttt{LRUCache lruCache = new LRUCache(2);} LRUCache lruCache = new LRUCache(2);
lruCache.put(1,   1); \texttt{lruCache.put(1, 1);} lruCache.put(1, 1); // 缓存是 {1=1} \texttt{\{1=1\}} {1=1}
lruCache.put(2,   2); \texttt{lruCache.put(2, 2);} lruCache.put(2, 2); // 缓存是 {1=1,   2=2} \texttt{\{1=1, 2=2\}} {1=1, 2=2}
lruCache.get(1); \texttt{lruCache.get(1);} lruCache.get(1); // 返回 1 \texttt{1} 1
lruCache.put(3,   3); \texttt{lruCache.put(3, 3);} lruCache.put(3, 3); // LRU 关键字是 2 \texttt{2} 2，逐出关键字 2 \texttt{2} 2，缓存是 {1=1,   3=3} \texttt{\{1=1, 3=3\}} {1=1, 3=3}
lruCache.get(2); \texttt{lruCache.get(2);} lruCache.get(2); // 返回 -1 \texttt{-1} -1（未找到）
lruCache.put(4,   4); \texttt{lruCache.put(4, 4);} lruCache.put(4, 4); // LRU 关键字是 1 \texttt{1} 1，逐出关键字 1 \texttt{1} 1，缓存是 {4=4,   3=3} \texttt{\{4=4, 3=3\}} {4=4, 3=3}
lruCache.get(1); \texttt{lruCache.get(1);} lruCache.get(1); // 返回 -1 \texttt{-1} -1（未找到）
lruCache.get(3); \texttt{lruCache.get(3);} lruCache.get(3); // 返回 3 \texttt{3} 3
lruCache.get(4); \texttt{lruCache.get(4);} lruCache.get(4); // 返回 4 \texttt{4} 4

数据范围

• 1 ≤ capacity ≤ 3000 \texttt{1} \le \texttt{capacity} \le \texttt{3000} 1≤capacity≤3000
• 0 ≤ key ≤ 10 4 \texttt{0} \le \texttt{key} \le \texttt{10}^\texttt{4} 0≤key≤104
• 0 ≤ value ≤ 10 5 \texttt{0} \le \texttt{value} \le \texttt{10}^\texttt{5} 0≤value≤105
• 最多调用 2 × 10 5 \texttt{2} \times \texttt{10}^\texttt{5} 2×105 次 get \texttt{get} get 和 put \texttt{put} put

前言

这道题要求在 O ( 1 ) O(1) O(1) 时间内执行 get \textit{get} get 和 put \textit{put} put 操作，满足该时间复杂度的数据结构是哈希表，即 Java 中的 HashMap \texttt{HashMap} HashMap。但是这道题还要求在关键字数量超出容量时逐出最久未使用的关键字，因此要求关键字按照访问顺序排列。由于 HashMap \texttt{HashMap} HashMap 中的关键字顺序不是按照访问顺序排列，因此需要将 HashMap \texttt{HashMap} HashMap 和双向链表结合才能实现题目的要求。

Java 中有 LinkedHashMap \texttt{LinkedHashMap} LinkedHashMap 类，该类是 HashMap \texttt{HashMap} HashMap 类的子类。和 HashMap \texttt{HashMap} HashMap 类相比， LinkedHashMap \texttt{LinkedHashMap} LinkedHashMap 类维护了双向链表，可以指定迭代顺序是插入顺序或者访问顺序。只要将迭代顺序指定为访问顺序，即可使用 LinkedHashMap \texttt{LinkedHashMap} LinkedHashMap 实现 LRU 缓存。

使用 LinkedHashMap \texttt{LinkedHashMap} LinkedHashMap 实现 LRU 缓存虽然可行，但是不适合在面试中使用。实现 LRU 缓存的标准解法是使用 HashMap \texttt{HashMap} HashMap 和双向链表自行实现，这也是面试官期望看到的解法。

以下是使用 LinkedHashMap \texttt{LinkedHashMap} LinkedHashMap 实现 LRU 缓存的代码，由于不适合在面试中使用，因此不具体说明。

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

        public LRUMap(int capacity) {
            super(capacity, 0.75f, true);
            this.capacity = capacity;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > capacity; 
        }
    }

    private LRUMap map;

    public LRUCache(int capacity) {
        map = new LRUMap(capacity);
    }
    
    public int get(int key) {
        return map.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        map.put(key, value);
    }
}

解法

思路和算法

实现 LRU 缓存需要使用哈希表和双向链表。双向链表中的每个结点存储键值对以及该结点的前一个结点和后一个结点，结点顺序为从头结点到尾结点依次按照最近访问时间降序排列。哈希表存储每个关键字对应的双向链表中的结点。

为了便于操作，双向链表需要维护伪头结点和伪尾结点，链表的实际头结点为伪头结点的后一个结点，链表的实际尾结点为伪尾结点的前一个结点（只有当链表不为空时才存在实际头结点和实际尾结点）。初始时，伪头结点和伪尾结点相邻。

构造方法中，将容量初始化为参数值，将哈希表初始化，将双向链表初始化为包含伪头结点和伪尾结点。

对于 get \textit{get} get 操作，做法如下。

• 如果哈希表中存在关键字 key \textit{key} key，则在哈希表中得到 key \textit{key} key 对应的结点，将该结点移动到双向链表的头部，返回结点的值。

• 如果哈希表中不存在关键字 key \textit{key} key，返回 − 1 -1 −1。

由于 get \textit{get} get 操作只是根据关键字 key \textit{key} key 从缓存中得到对应的值，虽然改变了关键字的顺序，但是并没有添加新的关键字，因此关键字的数量不变，不会出现关键字数量超过容量的情况，不需要逐出最久未使用的关键字。

对于 put \textit{put} put 操作，参考 get \textit{get} get 操作，必要的操作如下。

• 如果哈希表中存在关键字 key \textit{key} key，则在哈希表中得到 key \textit{key} key 对应的结点，将该结点的值设为 value \textit{value} value，并将该结点移动到双向链表的头部。

• 如果哈希表中不存在关键字 key \textit{key} key，则根据 key \textit{key} key 和 value \textit{value} value 创建结点，将该结点添加到双向链表的头部，并在哈希表中添加 key \textit{key} key 和该结点的对应关系。

上述操作并不完整。和 get \textit{get} get 操作不同， put \textit{put} put 操作可能添加新的关键字，因此需要判断关键字数量是否超过容量，在关键字数量超过容量的情况下需要逐出最久未使用的关键字。

• 如果哈希表中存在关键字 key \textit{key} key，则 put \textit{put} put 操作只是更新 key \textit{key} key 对应的值和改变关键字的顺序，并没有添加新的关键字，因此关键字的数量不变，不会出现关键字数量超过容量的情况，不需要逐出最久未使用的关键字。

• 如果哈希表中不存在关键字 key \textit{key} key，则 put \textit{put} put 操作添加了新的关键字，因此关键字的数量增加了 1 1 1 个，此时如果哈希表中的关键字数量超过容量，则需要逐出最久未使用的关键字，具体做法是：得到伪尾结点的前一个结点 tail \textit{tail} tail，该结点是实际尾结点，将实际尾结点从双向链表中删除，并将实际尾结点的关键字从哈希表中删除。

在 get \textit{get} get 和 put \textit{put} put 操作中，对双向列表的具体操作包括：将结点移动到双向链表的头部、将结点添加到双向链表的头部和将结点从双向链表中删除。由于将结点移动到双向链表的头部的操作可以通过将结点从双向链表中删除和将结点添加到双向链表的头部实现，因此对双向列表的具体操作包括将结点从双向链表中删除和将结点添加到双向链表的头部。

将结点从双向链表中删除的操作如下：定位到待删除结点的前一个结点 prev \textit{prev} prev 和后一个结点 next \textit{next} next，将 prev \textit{prev} prev 的后一个结点设为 next \textit{next} next，将 next \textit{next} next 的前一个结点设为 prev \textit{prev} prev。由于待删除结点一定不是伪头结点和伪尾结点，因此 prev \textit{prev} prev 和 next \textit{next} next 一定不为空，不需要判断是否为空。

将结点添加到双向链表的头部的操作如下：定位到伪头结点和伪头结点的后一个结点即原实际头结点（在添加新结点之前的实际头结点），将待添加结点添加到伪头结点和原实际头结点之间，将待添加结点的前一个结点和后一个结点分别设为伪头结点和原实际头结点，将伪头结点的后一个结点设为待添加结点，将原实际头结点的前一个结点设为待添加结点，即完成添加操作。由于伪头结点和原实际头结点一定不为空，因此不需要判断是否为空。当链表为空时，虽然在添加新节点之前不存在实际头结点，但是可以将伪尾结点看成原实际头结点，将结点添加到双向链表的头部的逻辑是一样的。

对于将结点从双向链表中删除和将结点添加到双向链表的头部的操作，定位到相应结点以及更新相应结点的前一个结点和后一个结点的时间都是 O ( 1 ) O(1) O(1)，因此将结点从双向链表中删除和将结点添加到双向链表的头部的操作的时间都是 O ( 1 ) O(1) O(1)。又由于哈希表操作的时间都是 O ( 1 ) O(1) O(1)，因此 get \textit{get} get 操作和 put \textit{put} put 操作的时间复杂度都是 O ( 1 ) O(1) O(1)。

代码

class LRUCache {
    private class Node {
        private int key;
        private int value;
        private Node prev;
        private Node next;

        public Node() {
            this(-1, -1);
        }

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            prev = null;
            next = null;
        }

        public int getKey() {
            return key;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Node getPrev() {
            return prev;
        }

        public void setPrev(Node prev) {
            this.prev = prev;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }

    private int capacity;
    private Map<Integer, Node> map;
    private Node pseudoHead;
    private Node pseudoTail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<Integer, Node>();
        pseudoHead = new Node();
        pseudoTail = new Node();
        pseudoHead.setNext(pseudoTail);
        pseudoTail.setPrev(pseudoHead);
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            remove(node);
            addAtHead(node);
            return node.getValue();
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.setValue(value);
            remove(node);
            addAtHead(node);
        } else {
            Node node = new Node(key, value);
            addAtHead(node);
            map.put(key, node);
            if (map.size() > capacity) {
                Node tail = pseudoTail.getPrev();
                map.remove(tail.getKey());
                remove(tail);
            }
        }
    }

    private void remove(Node node) {
        Node prev = node.getPrev(), next = node.getNext();
        prev.setNext(next);
        next.setPrev(prev);
    }

    private void addAtHead(Node node) {
        Node prevHead = pseudoHead.getNext();
        node.setPrev(pseudoHead);
        node.setNext(prevHead);
        pseudoHead.setNext(node);
        prevHead.setPrev(node);
    }
}

复杂度分析

• 时间复杂度：构造方法和各项操作的时间复杂度都是 O ( 1 ) O(1) O(1)。

• 空间复杂度： O ( capacity ) O(\textit{capacity}) O(capacity)，其中 capacity \textit{capacity} capacity 是 LRU 缓存的容量。每次 get \textit{get} get 和 put \textit{put} put 操作之后，哈希表中的键值对数量和双向链表中的结点数量（不包括伪头结点和伪尾结点）不会超过 capacity \textit{capacity} capacity。在 put \textit{put} put 操作过程中，哈希表中的键值对数量和双向链表中的结点数量（不包括伪头结点和伪尾结点）不会超过 capacity + 1 \textit{capacity} + 1 capacity+1，且如果达到 capacity + 1 \textit{capacity} + 1 capacity+1，则将删除双向链表中的实际尾结点和该结点的关键字在哈希表中的键值对，使哈希表中的键值对数量和双向链表中的结点数量（不包括伪头结点和伪尾结点）变成 capacity \textit{capacity} capacity。