LeetCode 146 LRU缓存：哈希表+双向链表实现O(1)操作

题目描述

请你设计并实现一个满足 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) 的平均时间复杂度运行。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

输入
["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 <= 10^4
• 0 <= value <= 10^5
• 最多调用 2 * 10^5 次 get 和 put 方法

解题思路

哈希表 + 双向链表

要实现O(1)时间复杂度的get和put操作，需要组合两种数据结构：

1. 哈希表实现O(1)的查找
2. 双向链表实现O(1)的插入和删除

关键点：

1. 双向链表按使用顺序存储节点，头部是最近使用的，尾部是最久未使用的
2. 哈希表存储key到链表节点的映射，实现快速查找
3. 每次访问节点时，把它移到链表头部

具体步骤：

1. 初始化：
   • 创建双向链表和哈希表
   • 设置容量限制
2. get操作：
   • key不存在返回-1
   • key存在就把节点移到链表头部，返回值
3. put操作：
   • key已存在，更新值并移到头部
   • key不存在：
     • 缓存满了就删除尾部节点
     • 创建新节点添加到头部

时间复杂度：O(1)，所有操作都是常数时间 空间复杂度：O(capacity)，最多存储capacity个键值对

图解思路

以示例操作序列为例，展示缓存的变化过程：

1. 初始状态：

capacity = 2
cache = {}

2. put(1,1):

cache = {1=1}
链表：[1]

3. put(2,2):

cache = {1=1, 2=2}
链表：[2] <-> [1]

4. get(1):

cache = {1=1, 2=2}
链表：[1] <-> [2]  // 1被访问，移到头部

5. put(3,3):

cache = {1=1, 3=3}  // 2被逐出
链表：[3] <-> [1]

代码实现

C# 实现

public class LRUCache {
    private class DLinkedNode {
        public int key;
        public int value;
        public DLinkedNode prev;
        public DLinkedNode next;
        
        public DLinkedNode() {}
        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private Dictionary<int, DLinkedNode> cache;
    private DLinkedNode head;
    private DLinkedNode tail;
    private int capacity;
    private int size;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.cache = new Dictionary<int, DLinkedNode>();
        
        // 使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    
    public int Get(int key) {
        if (!cache.ContainsKey(key)) {
            return -1;
        }
        
        DLinkedNode node = cache[key];
        // 将节点移到头部
        MoveToHead(node);
        return node.value;
    }
    
    public void Put(int key, int value) {
        if (cache.ContainsKey(key)) {
            // 如果key存在，更新值并移到头部
            DLinkedNode node = cache[key];
            node.value = value;
            MoveToHead(node);
        } else {
            // 如果key不存在，创建新节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            cache.Add(key, newNode);
            AddToHead(newNode);
            size++;
            
            if (size > capacity) {
                // 如果超出容量，删除尾部节点
                DLinkedNode tail = RemoveTail();
                cache.Remove(tail.key);
                size--;
            }
        }
    }
    
    private void AddToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    
    private void RemoveNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    private void MoveToHead(DLinkedNode node) {
        RemoveNode(node);
        AddToHead(node);
    }
    
    private DLinkedNode RemoveTail() {
        DLinkedNode res = tail.prev;
        RemoveNode(res);
        return res;
    }
}

Python 实现

class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = {}
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.size = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self.move_to_head(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self.move_to_head(node)
        else:
            new_node = DLinkedNode(key, value)
            self.cache[key] = new_node
            self.add_to_head(new_node)
            self.size += 1
            if self.size > self.capacity:
                removed = self.remove_tail()
                self.cache.pop(removed.key)
                self.size -= 1

    def add_to_head(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def move_to_head(self, node):
        self.remove_node(node)
        self.add_to_head(node)

    def remove_tail(self):
        node = self.tail.prev
        self.remove_node(node)
        return node

C++ 实现

struct DLinkedNode {
    int key;
    int value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int capacity;
    int size;

public:
    LRUCache(int _capacity): capacity(_capacity), size(0) {
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    ~LRUCache() {
        while (head != nullptr) {
            DLinkedNode* tmp = head;
            head = head->next;
            delete tmp;
        }
    }
    
    int get(int key) {
        if (!cache.count(key)) {
            return -1;
        }
        DLinkedNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if (cache.count(key)) {
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        } else {
            DLinkedNode* node = new DLinkedNode(key, value);
            cache[key] = node;
            addToHead(node);
            ++size;
            if (size > capacity) {
                DLinkedNode* removed = removeTail();
                cache.erase(removed->key);
                delete removed;
                --size;
            }
        }
    }

private:
    void addToHead(DLinkedNode* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    
    void removeNode(DLinkedNode* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    
    void moveToHead(DLinkedNode* node) {
        removeNode(node);
        addToHead(node);
    }
    
    DLinkedNode* removeTail() {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};

性能分析

各语言的性能对比：

实现语言	执行用时	内存消耗
C++	380 ms	161.2 MB
C#	452 ms	115.8 MB
Python	628 ms	75.3 MB

C++性能最好，但内存占用较大。这题的关键是理解如何组合两种数据结构来实现O(1)操作。

补充说明

代码亮点

1. 双向链表和哈希表的组合实现了O(1)时间复杂度
2. 用伪头部和伪尾部节点简化了边界情况处理
3. 封装了链表操作的辅助函数，代码更清晰

常见错误

1. 删除节点时忘记同时更新哈希表
2. 链表操作时没有正确维护前后指针
3. 没有正确处理容量限制

相关题目

• 460. LFU 缓存
• 432. 全 O(1) 的数据结构
• 1756. 设计最近使用（MRU）队列

讨论

有几个问题可以思考一下：

1. 为什么用双向链表而不是单向链表？单向链表能实现O(1)的删除操作吗？
2. 伪头部和伪尾部节点的作用是什么？如果不用它们会怎样？
3. LRU缓存在实际项目中有哪些应用场景？你遇到过吗？

欢迎在评论区讨论。

---

如果你都看到这里了，说明还是有点收获的吧？给个赞鼓励一下呗。