LRU 缓存

约 1898 字大约 6 分钟

链表困难百度腾讯

2025-1-10

⭐ 题目日期：

百度 - 2025/1/7，腾讯 - 2024/12/17, 2024/9/12，小米 - 2024/11/1，虾皮 - 2024/10/26

🌳 题目描述：

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 作废，缓存是 {3=3, 1=1}
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

🕵🏽 面试评估：

这道题主要考察对缓存机制的理解、能否选用合适的数据结构实现目标操作时间复杂度、以及考察候选人代码的设计能力和实战水平 - 能否合理地拆分功能模块，提高代码的复用性和可读性。

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️ ⭐️

📝思路分析：

Get API 设计

get 为查询，要以 O(1) 的平均时间复杂度查询指定元素，可以用哈希表来存储。除了查询，还需更新查询到的元素的缓存顺序，因为刚刚查询的操作会让这个元素成为最近最多使用的元素。

如何做到仅用 O(1) 来更新缓存顺序呢？

加入到缓存系统里的所有元素，都维持了一个缓存的相对顺序。而通常维持顺序的数据结构为线性表，常见的线性表分为两种：数组和链表。

先看数组，假定缓存顺序如下：1 2 3 4 5 ... n；get(3), 由于数组的连续存储特性，我们需要将 3 之前的元素整体后移一位，再将3放在数组的首位，这是 O(n) 级的操作。不符合题目要求。

再看链表，1 -> 2 -> 3 -> 4 -> 5 -> ... -> n。但是链表不能像数组一样按照索引来快速访问，如何在 O(1) 的时间内找到指定的节点？

从表头开始一个一个访问是行不通的，因为时间复杂度为 O(n)。既然哈希表能在 O(1) 的时间内找到 <key, value>, 那我们将整个节点存进 value，再根据 key 来查询，就能实现 O(1) 找到目标节点。例如，我们将(3, 6) 加入缓存系统，哈希表里存: < 3, new Node(3, 6) >.

get(3), 找到了节点 3 的位置，将 3 移到表头，表头表明这是最近最多使用的元素，还需要在 O(1) 内将 2 4 相连，我们能根据 3 的 next 指针找到 4，那 2 如何找到呢？在节点里加一个 prev 来指向前一个节点，每个节点都有一个 prev 指针，这样就构成了一个双链表，从表头到尾依次代表从最近最多使用的元素到最近最少使用的元素。

Put API 设计

put(key, value) 将(key, value) 加入缓存。

如果 key 已经在缓存里，先去哈希表里找到已经存的节点，再更改新的 value 值，与 get 类似，需要将节点移至表头，再连接留下的空缺。
如果 key 不在缓存里，先创建一个 <key, new Node(key, value)> 存进哈希表里，再将其置于表头，此时，如果缓存容量溢出，需要移除尾部的元素。如何在 O(1) 的时间移除尾节点呢？要移除，我们先要 O(1) 找到尾节点，要O(1)的时间找到链表中的任何一个节点，我们都需要维护一个专门的指针，此处为尾指针，再将其移除即可。

由于 get 和 put 的频繁调用，需要频繁更新头尾指针，还有空表等边界条件要考虑，会增加实现的难度。对此，我们可以创建头尾节点的哑节点，这样所有的操作都在一个非空的、无需更换头尾节点的双链表(dummyHead -> ... -> dummyTail)中，大大降低了操作的复杂度。

💻代码：

Java

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

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<Integer, Node> map;
    private final Node dummyHead;
    private final Node dummyTail;

    // Constructor

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

        // 创建头、尾哑节点简化链表操作
        dummyHead = new Node(0, 0);
        dummyTail = new Node(0, 0);
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }

    // Public APIs

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

        Node node = map.get(key);
        updateHead(node, true);
        return node.value;
    }

    public void put(int key, int value) {
        if (!map.containsKey(key)) {
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            updateHead(newNode, false);
            if (map.size() > capacity) {
                map.remove(dummyTail.prev.key);
                remove(dummyTail.prev);
            }
        } else {
            Node node = map.get(key);
            node.value = value;
            updateHead(node, true);
        }
    }

    // Private Helpers

    private void updateHead(Node node, boolean isExisted) {
        if (isExisted) {
            remove(node);
        }

        node.prev = dummyHead;
        node.next = dummyHead.next;
        dummyHead.next.prev = node;
        dummyHead.next = node;
    }

    private void remove(Node node) {
        Node prev = node.prev;
        Node next = node.next;
        prev.next = next;
        next.prev = prev;
    }
}

Python

class Node:
    def __init__(self, key: int, value: int):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}  # 用字典代替 Java 的 HashMap
        self.dummy_head = Node(0, 0)  # 创建头哑节点
        self.dummy_tail = Node(0, 0)  # 创建尾哑节点
        self.dummy_head.next = self.dummy_tail
        self.dummy_tail.prev = self.dummy_head

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1

        node = self.map[key]
        self._update_head(node, is_existed=True)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.map:
            new_node = Node(key, value)
            self.map[key] = new_node
            self._update_head(new_node, is_existed=False)

            if len(self.map) > self.capacity:
                # 淘汰链表尾部的节点
                lru = self.dummy_tail.prev
                self.map.pop(lru.key)
                self._remove(lru)
        else:
            node = self.map[key]
            node.value = value
            self._update_head(node, is_existed=True)

    # 更新头节点
    def _update_head(self, node: Node, is_existed: bool) -> None:
        if is_existed:
            self._remove(node)

        # 插入到头部
        node.prev = self.dummy_head
        node.next = self.dummy_head.next
        self.dummy_head.next.prev = node
        self.dummy_head.next = node

    # 从链表中移除节点
    def _remove(self, node: Node) -> None:
        prev = node.prev
        nxt = node.next
        prev.next = nxt
        nxt.prev = prev

C++

#include <iostream>
#include <unordered_map>
using namespace std;

class LRUCache {
private:
    class Node {
    public:
        int key;
        int value;
        Node* prev;
        Node* next;

        Node(int key, int value) {
            this->key = key;
            this->value = value;
        }
    };

    int capacity;
    unordered_map<int, Node*> map;
    Node* dummyHead;
    Node* dummyTail;

public:
    // Constructor
    LRUCache(int capacity) {
        this->capacity = capacity;
        dummyHead = new Node(0, 0);
        dummyTail = new Node(0, 0);
        dummyHead->next = dummyTail;
        dummyTail->prev = dummyHead;
    }

    // Public APIs
    int get(int key) {
        if (map.find(key) == map.end()) {
            return -1;
        }

        Node* node = map[key];
        updateHead(node, true);
        return node->value;
    }

    void put(int key, int value) {
        if (map.find(key) == map.end()) {
            Node* newNode = new Node(key, value);
            map[key] = newNode;
            updateHead(newNode, false);
            if (map.size() > capacity) {
                map.erase(dummyTail->prev->key);
                remove(dummyTail->prev);
            }
        } else {
            Node* node = map[key];
            node->value = value;
            updateHead(node, true);
        }
    }

private:
    // Private Helpers
    void updateHead(Node* node, bool isExisted) {
        if (isExisted) {
            remove(node);
        }

        node->prev = dummyHead;
        node->next = dummyHead->next;
        dummyHead->next->prev = node;
        dummyHead->next = node;
    }

    void remove(Node* node) {
        Node* prev = node->prev;
        Node* next = node->next;
        prev->next = next;
        next->prev = prev;
    }
};

🚵🏻复杂度分析：

时间复杂度：get, put 的平均时间复杂度为 O(1)

空间复杂度：get 不增加缓存内元素的数量，空间复杂度为 O(1)；put 单次操作至多加一个元素，删除一个元素，平均的空间复杂度也为 O(1)

🔬在线评测(Online Judge):

题目链接