146. LRU 缓存

力扣题目链接 (opens new window)

题目描述

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

实现 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

思路

LRU（Least Recently Used）是操作系统中常见的缓存淘汰算法，面试高频题。

核心要求：

1. get 和 put 都要 O(1) 时间复杂度
2. 能快速找到最久未使用的元素

要在 O(1) 时间内查找元素，想到哈希表。

但哈希表无法维护"使用顺序"，怎么办？

关键思路：哈希表 + 双向链表

• 哈希表：实现 O(1) 查找
• 双向链表：维护使用顺序

为什么用双向链表？

链表可以维护顺序，我们可以这样设计：

• 链表头部：最近使用的元素
• 链表尾部：最久未使用的元素

每次访问（get 或 put）一个元素时，把它移到链表头部，表示刚刚使用过。

当缓存满了要淘汰元素时，直接删除链表尾部的元素。

为什么必须是双向链表？

因为要在 O(1) 时间内删除某个节点。

单向链表删除节点需要找到它的前驱节点，需要 O(n) 时间遍历。双向链表有 prev 指针，可以直接找到前驱，删除操作 O(1)。

数据结构设计

struct DLinkedNode {
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
};

• unordered_map<int, DLinkedNode*> cache：哈希表，key → 节点指针的映射
• DLinkedNode* head, * tail：虚拟头尾节点，简化边界处理
• int size, capacity：当前大小和容量

操作流程

get(key)：

1. 在哈希表中查找 key
2. 如果不存在，返回 -1
3. 如果存在，将对应节点移到链表头部（表示刚使用过），返回 value

put(key, value)：

1. 在哈希表中查找 key
2. 如果存在，更新 value，将节点移到头部
3. 如果不存在：
   • 创建新节点，添加到头部，更新哈希表
   • 如果超过容量，删除尾部节点（最久未使用），并从哈希表中移除

模拟过程

以示例为例：容量为 2

初始状态：空链表

put(1, 1)：插入到头部

链表：1

put(2, 2)：插入到头部

链表：2 → 1

get(1)：访问节点1，移到头部

链表：1 → 2

put(3, 3)：容量满，删除尾部节点2，插入3

链表：3 → 1

get(2)：节点2已被淘汰，返回 -1

put(4, 4)：容量满，删除尾部节点1，插入4

链表：4 → 3

解题代码

struct DLinkedNode {
    int key, 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 size;
    int capacity;

public:
    LRUCache(int _capacity): capacity(_capacity), size(0) {
        // 虚拟头尾节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        }
        DLinkedNode* node = cache[key];
        moveToHead(node); // 移到头部，表示最近使用
        return node->value;
    }
    
    void put(int key, int value) {
        if (cache.find(key) == cache.end()) {
            // 新节点
            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;
            }
        } else {
            // 已存在，更新value并移到头部
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }
    
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;
    }
};

复杂度分析

• 时间复杂度：get 和 put 都是 O(1)
• 空间复杂度：O(capacity)，哈希表和链表的空间

其他语言

Python3

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 not in self.cache:
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self.add_to_head(node)
            self.size += 1
            if self.size > self.capacity:
                removed = self.remove_tail()
                del self.cache[removed.key]
                self.size -= 1
        else:
            node = self.cache[key]
            node.value = value
            self.move_to_head(node)

    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

Java

class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            DLinkedNode newNode = new DLinkedNode(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                DLinkedNode tail = removeTail();
                cache.remove(tail.key);
                --size;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }

    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;
    }
}

Go

type DLinkedNode struct {
    key, value int
    prev, next *DLinkedNode
}

type LRUCache struct {
    size       int
    capacity   int
    cache      map[int]*DLinkedNode
    head, tail *DLinkedNode
}

func Constructor(capacity int) LRUCache {
    lru := LRUCache{
        cache:    map[int]*DLinkedNode{},
        head:     &DLinkedNode{},
        tail:     &DLinkedNode{},
        capacity: capacity,
    }
    lru.head.next = lru.tail
    lru.tail.prev = lru.head
    return lru
}

func (this *LRUCache) Get(key int) int {
    if node, ok := this.cache[key]; ok {
        this.moveToHead(node)
        return node.value
    }
    return -1
}

func (this *LRUCache) Put(key int, value int) {
    if node, ok := this.cache[key]; ok {
        node.value = value
        this.moveToHead(node)
    } else {
        node := &DLinkedNode{key: key, value: value}
        this.cache[key] = node
        this.addToHead(node)
        this.size++
        if this.size > this.capacity {
            removed := this.removeTail()
            delete(this.cache, removed.key)
            this.size--
        }
    }
}

func (this *LRUCache) addToHead(node *DLinkedNode) {
    node.prev = this.head
    node.next = this.head.next
    this.head.next.prev = node
    this.head.next = node
}

func (this *LRUCache) removeNode(node *DLinkedNode) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

func (this *LRUCache) moveToHead(node *DLinkedNode) {
    this.removeNode(node)
    this.addToHead(node)
}

func (this *LRUCache) removeTail() *DLinkedNode {
    node := this.tail.prev
    this.removeNode(node)
    return node
}

JS

class DLinkedNode {
    constructor(key = 0, value = 0) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

class LRUCache {
    constructor(capacity) {
        this.cache = new Map();
        this.head = new DLinkedNode();
        this.tail = new DLinkedNode();
        this.head.next = this.tail;
        this.tail.prev = this.head;
        this.capacity = capacity;
        this.size = 0;
    }

    get(key) {
        if (!this.cache.has(key)) {
            return -1;
        }
        const node = this.cache.get(key);
        this.moveToHead(node);
        return node.value;
    }

    put(key, value) {
        if (!this.cache.has(key)) {
            const node = new DLinkedNode(key, value);
            this.cache.set(key, node);
            this.addToHead(node);
            this.size++;
            if (this.size > this.capacity) {
                const removed = this.removeTail();
                this.cache.delete(removed.key);
                this.size--;
            }
        } else {
            const node = this.cache.get(key);
            node.value = value;
            this.moveToHead(node);
        }
    }

    addToHead(node) {
        node.prev = this.head;
        node.next = this.head.next;
        this.head.next.prev = node;
        this.head.next = node;
    }

    removeNode(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    moveToHead(node) {
        this.removeNode(node);
        this.addToHead(node);
    }

    removeTail() {
        const node = this.tail.prev;
        this.removeNode(node);
        return node;
    }
}

与代码随想录联系

这道题是数据结构设计题，综合了两个核心知识点：

1. 哈希表 — 实现 O(1) 查找，在代码随想录 哈希表章节 有详细讲解
2. 双向链表 — 维护使用顺序，在代码随想录链表章节有基础操作讲解

LRU 是工业界常用的缓存淘汰策略，Redis、操作系统页面置换都会用到。

很多录友第一次做这道题，会纠结"为什么一定要双向链表"。想清楚删除节点需要 O(1) 时间这个需求，就理解了。

建议录友们把链表和哈希表的基础题都做透，再来做这道综合题会轻松很多。