LC 146：LRU 缓存

题目

题目链接

请你设计并实现一个满足 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 <= 10^5
• 最多调用 2 * 10^5 次 get 和 put

尝试

思路

可以用一个双向链表来模拟缓存，最近使用过的键值对将自动插入到链表首部，链表的容量超出限制则删除链表尾部的键值对。由于查询和插入都要求常数时间，可以用一个哈希表来快速定位特定键值对在链表中的位置。

复杂度分析

• 时间复杂度: 查询和插入操作均为 $\mathcal{O}(1)$。
• 空间复杂度: $\mathcal{O}(\min (\text{the number of } \texttt{put} \text{ operation}, \text{capacity}))$。

代码

/**  
 * Map + DoubleLinkedList 
 * DoubleLinkedList: 哨兵节点，head <=> tail  
 * Map: key - Node 
 * Node: key, val, prev, next 
 * 
 * get: 查询 Map，存在则直接返回 val，否则返回 -1
 * put：  
 *   1. 不存在则新建节点放到 head 后。若超出容量则删除 tail 前的节点。更新 Map。  
 *   2. 存在则更新 Map，并将节点移动到 head 后。  
 */
class LRUCache {  
    class Node {  
        int key;  
        int val;  
        Node prev;  
        Node next;  
  
        public Node(int key, int val) {  
            this.key = key;  
            this.val = val;  
        }  
    }  
  
    Node head, tail;  
    Map<Integer, Node> map;  
    int capacity;  
    int curSize = 0;  
  
    public LRUCache(int capacity) {  
        this.capacity = capacity;  
        head = new Node(-1, -1);  
        tail = new Node(-1, -1);  
        head.next = tail;  
        head.prev = tail;  
        tail.next = head;  
        tail.prev = head;  
        map = new HashMap<>();  
    }  
  
    public int get(int key) {  
        if (map.containsKey(key)) {  
            Node node = map.get(key);  
            delete(node);  
            addFirst(node);  
            return node.val;  
        }  
        return -1;  
    }  
  
    public void put(int key, int value) {  
        if (map.containsKey(key)) {  
            Node node = map.get(key);  
            node.val = value;  
            delete(node);  
            addFirst(node);  
        } else {  
            Node node = new Node(key, value);  
            map.put(key, node);  
            addFirst(node);  
            curSize++;  
            deleteLast();  
        }  
    }  
  
    private void delete(Node node) {  
        Node prevNode = node.prev;  
        Node nextNode = node.next;  
        prevNode.next = nextNode;  
        nextNode.prev = prevNode;  
    }  
  
    private void addFirst(Node node) {  
        Node oldFirst = head.next;  
        head.next = node;  
        node.prev = head;  
        oldFirst.prev = node;  
        node.next = oldFirst;  
    }  
  
    private void deleteLast() {  
        if (curSize > capacity) {  
            Node node = tail.prev;  
            delete(node);  
            map.remove(node.key);  
            curSize--;  
        }  
    }  
}

优化

根据 灵神题解 进行优化。双向链表的哨兵节点只需要一个就够了。

复杂度分析

• 时间复杂度: 查询和插入操作均为 $\mathcal{O}(1)$。
• 空间复杂度: $\mathcal{O}(\min (\text{the number of } \texttt{put} \text{ operation}, \text{capacity}))$。

优化版代码

class LRUCache {  
    class Node {  
        int key;  
        int val;  
        Node prev;  
        Node next;  
  
        public Node(int key, int val) {  
            this.key = key;  
            this.val = val;  
        }  
    }  
  
    Node dummy;  
    Map<Integer, Node> map;  
    int capacity;  
    int curSize = 0;  
  
    public LRUCache(int capacity) {  
        this.capacity = capacity;  
        dummy = new Node(-1, -1);  
        dummy.next = dummy;  
        dummy.prev = dummy;  
        map = new HashMap<>();  
    }  
  
    public int get(int key) {  
        if (map.containsKey(key)) {  
            Node node = map.get(key);  
            delete(node);  
            addFirst(node);  
            return node.val;  
        }  
        return -1;  
    }  
  
    public void put(int key, int value) {  
        if (map.containsKey(key)) {  
            Node node = map.get(key);  
            node.val = value;  
            delete(node);  
            addFirst(node);  
        } else {  
            Node node = new Node(key, value);  
            map.put(key, node);  
            addFirst(node);  
            curSize++;  
            deleteLast();  
        }  
    }  
  
    private void delete(Node node) {  
        Node prevNode = node.prev;  
        Node nextNode = node.next;  
        prevNode.next = nextNode;  
        nextNode.prev = prevNode;  
    }  
  
    private void addFirst(Node node) {  
        Node oldFirst = dummy.next;  
        dummy.next = node;  
        node.prev = dummy;  
        oldFirst.prev = node;  
        node.next = oldFirst;  
    }  
  
    private void deleteLast() {  
        if (curSize > capacity) {  
            Node node = dummy.prev;  
            delete(node);  
            map.remove(node.key);  
            curSize--;  
        }  
    }  
}