146. LRU 缓存

Origin: LeetCode 146

题目描述

设计并实现满足 LRU（最近最少使用）缓存约束的数据结构。支持 get 和 put 操作，均摊 O(1)。

• get(key)：如果 key 存在返回 value，否则返回 -1
• put(key, value)：如果 key 存在更新 value，否则插入。当容量达到上限时，删除最近最少使用的 key

示例

LRUCache lRUCache = new LRUCache(2)
lRUCache.put(1, 1)     // 缓存 {1=1}
lRUCache.put(2, 2)     // 缓存 {1=1, 2=2}
lRUCache.get(1)        // 返回 1，缓存 {2=2, 1=1}（1 被使用了，移到最近）
lRUCache.put(3, 3)     // 淘汰 key 2，缓存 {1=1, 3=3}
lRUCache.get(2)        // 返回 -1
lRUCache.put(4, 4)     // 淘汰 key 1，缓存 {3=3, 4=4}
lRUCache.get(1)        // 返回 -1
lRUCache.get(3)        // 返回 3
lRUCache.get(4)        // 返回 4

约束

• 1 <= capacity <= 3000
• 0 <= key <= 10
• 0 <= value <= 10
• 最多调用 2 × 10^5 次 get 和 put

关键信息

• 面试超高频设计题
• 哈希表 + 双向链表
• 哈希表存 key → node，O(1) 查找
• 双向链表维护使用顺序，最近使用的在头部，最久没用的在尾部
• 你做过第 41 题（双栈队列）和第 155 题（双栈），设计题思路有

Resolution

我的解法

class LRUCache {
    capacity: number
    map: Map<number, number> = new Map()
 
    constructor(capacity: number) {
        this.capacity = capacity
    }
 
    get(key: number): number {
        if (!this.map.has(key)) return -1
        const value = this.map.get(key)!
        this.map.delete(key)
        this.map.set(key, value)  // 重新 set，移到最新位置
        return value
    }
 
    put(key: number, value: number): void {
        if (this.map.has(key)) {
            this.map.delete(key)  // 已存在，先 delete 再 set 更新位置
        } else if (this.map.size >= this.capacity) {
            const deleteKey = Array.from(this.map.keys())[0]
            this.map.delete(deleteKey)
        }
        this.map.set(key, value)
    }
}

解题思路

利用 JS Map 保持插入顺序的特性，不用手写双向链表：

V8 引擎 Map 实现（为什么能用 Map 模拟 LRU）

V8 的 Map 底层是哈希表（开放寻址法），但额外维护了一个双向链表来记录插入顺序。每次 set/delete 时同步更新这个链表。所以：

• Map 保持插入顺序 = 底层有双向链表
• delete + set = 把节点从链表中删掉再插到尾部（最新位置）
• map.keys().next() = 链表头部（最旧位置）
• 所有操作 O(1) = 哈希表查找 + 链表操作

所以用 Map 模拟 LRU 不是取巧，是直接用了 V8 已经实现好的”哈希表 + 双向链表”。

操作逻辑

• get：delete + set 把 key 移到最新位置
• put：已存在的 key 先 delete 再 set 更新位置；容量满时删第一个（最久没用的）
• 淘汰：Array.from(map.keys())[0] 拿最旧的 key

踩坑

• get 不能只读不写，必须 delete + set 更新使用顺序，否则淘汰时删错
• put 已存在的 key 也要 delete + set，不能直接 set（set 不改变已有 key 的位置）
• 面试时如果面试官要求不用 Map，要能用哈希表 + 双向链表实现

复杂度

• get/put：均摊 O(1)
• 空间：O(capacity)

标准解法（哈希表 + 双向链表）

class DLinkedNode {
    key: number
    val: number
    prev: DLinkedNode | null = null
    next: DLinkedNode | null = null
    constructor(key: number = 0, val: number = 0) {
        this.key = key
        this.val = val
    }
}
 
class LRUCache {
    capacity: number
    cache: Map<number, DLinkedNode> = new Map()
    head: DLinkedNode  // 虚拟头节点
    tail: DLinkedNode  // 虚拟尾节点
 
    constructor(capacity: number) {
        this.capacity = capacity
        this.head = new DLinkedNode()
        this.tail = new DLinkedNode()
        this.head.next = this.tail
        this.tail.prev = this.head
    }
 
    // 删除节点
    removeNode(node: DLinkedNode): void {
        node.prev!.next = node.next
        node.next!.prev = node.prev
    }
 
    // 添加到头部（最近使用）
    addToHead(node: DLinkedNode): void {
        node.prev = this.head
        node.next = this.head.next
        this.head.next!.prev = node
        this.head.next = node
    }
 
    // 移到头部
    moveToHead(node: DLinkedNode): void {
        this.removeNode(node)
        this.addToHead(node)
    }
 
    // 删除尾部（最久未使用）
    removeTail(): DLinkedNode {
        const node = this.tail.prev!
        this.removeNode(node)
        return node
    }
 
    get(key: number): number {
        if (!this.cache.has(key)) return -1
        const node = this.cache.get(key)!
        this.moveToHead(node)
        return node.val
    }
 
    put(key: number, value: number): void {
        if (this.cache.has(key)) {
            const node = this.cache.get(key)!
            node.val = value
            this.moveToHead(node)
        } else {
            const node = new DLinkedNode(key, value)
            this.cache.set(key, node)
            this.addToHead(node)
            if (this.cache.size > this.capacity) {
                const removed = this.removeTail()
                this.cache.delete(removed.key)
            }
        }
    }
}

虚拟头尾节点简化边界处理，哈希表存 key → node 实现快速查找，双向链表维护使用顺序。

数组模拟双向链表解法

class LRUCache {
    capacity: number
    // 数组模拟双向链表：用下标代替指针
    keys: number[] = []     // keys[i] = 节点 i 的 key
    vals: number[] = []     // vals[i] = 节点 i 的 val
    prev: number[] = []     // prev[i] = 节点 i 的前驱下标
    next: number[] = []     // next[i] = 节点 i 的后继下标
    map: Map<number, number> = new Map()  // key -> 数组下标
    idx: number = 2         // 0 是虚拟头，1 是虚拟尾，从 2 开始分配
 
    constructor(capacity: number) {
        this.capacity = capacity
        // 初始化虚拟头尾
        this.keys = [0, 0]
        this.vals = [0, 0]
        this.prev = [1, 0]  // head.prev 无意义，tail.prev = head
        this.next = [1, 0]  // head.next = tail，tail.next 无意义
    }
 
    // 删除下标 i 的节点
    remove(i: number): void {
        const p = this.prev[i]
        const n = this.next[i]
        this.next[p] = n
        this.prev[n] = p
    }
 
    // 在虚拟头之后插入下标 i（最近使用）
    addToHead(i: number): void {
        this.prev[i] = 0
        this.next[i] = this.next[0]
        this.prev[this.next[0]] = i
        this.next[0] = i
    }
 
    // 移到头部
    moveToHead(i: number): void {
        this.remove(i)
        this.addToHead(i)
    }
 
    // 删除尾部（最久未使用），返回下标
    removeTail(): number {
        const i = this.prev[1]  // tail.prev
        this.remove(i)
        return i
    }
 
    get(key: number): number {
        if (!this.map.has(key)) return -1
        const i = this.map.get(key)!
        this.moveToHead(i)
        return this.vals[i]
    }
 
    put(key: number, value: number): void {
        if (this.map.has(key)) {
            const i = this.map.get(key)!
            this.vals[i] = value
            this.moveToHead(i)
        } else {
            // 分配新下标
            const i = this.idx++
            this.keys[i] = key
            this.vals[i] = value
            this.map.set(key, i)
            this.addToHead(i)
            if (this.map.size > this.capacity) {
                const removed = this.removeTail()
                this.map.delete(this.keys[removed])
            }
        }
    }
}

用数组下标代替指针，prev[i] 和 next[i] 存的是下标而不是对象引用。性能更好（连续内存、无 GC），适合大数据量。