LRU 缓存

本章目标：从零实现 O(1) 操作的 LRU 缓存，掌握哈希表 + 双向链表的经典组合。

你将学到

LRU（最近最少使用）的淘汰策略
哈希表 + 双向链表的组合设计
O(1) get 和 put 的实现原理
LFU（最不经常使用）简介

1. 概念

LRU（Least Recently Used）是一种缓存淘汰策略：当缓存满时，淘汰最久没被访问的数据。操作系统页面置换、Redis 缓存淘汰、iOS NSCache 底层都用到类似策略。

实现 LRU 需要：

快速查找（O(1) get）→ 哈希表
快速调整顺序（O(1) 移动到头部/删除尾部）→ 双向链表

组合起来：哈希表的 value 指向双向链表节点，每次访问把节点移到头部（最新），淘汰时删尾部（最旧）。

2. 完整实现

Swift 版

swift

// 双向链表节点
class DLinkedNode {
    var key: Int = 0
    var val: Int = 0
    var prev: DLinkedNode?
    var next: DLinkedNode?
    init(_ key: Int = 0, _ val: Int = 0) {
        self.key = key
        self.val = val
    }
}

class LRUCache {
    private var capacity: Int
    private var cache: [Int: DLinkedNode] = [:]
    private let head = DLinkedNode()  // 虚拟头
    private let tail = DLinkedNode()  // 虚拟尾

    init(_ capacity: Int) {
        self.capacity = capacity
        head.next = tail
        tail.prev = head
    }

    func get(_ key: Int) -> Int {
        guard let node = cache[key] else { return -1 }
        moveToHead(node)  // 访问后移到头部
        return node.val
    }

    func put(_ key: Int, _ value: Int) {
        if let node = cache[key] {
            node.val = value
            moveToHead(node)
        } else {
            let newNode = DLinkedNode(key, value)
            cache[key] = newNode
            addToHead(newNode)
            if cache.count > capacity {
                let removed = removeTail()
                cache.removeValue(forKey: removed.key)
            }
        }
    }

    // 在头部添加节点
    private func addToHead(_ node: DLinkedNode) {
        node.prev = head
        node.next = head.next
        head.next?.prev = node
        head.next = node
    }

    // 移除节点
    private func removeNode(_ node: DLinkedNode) {
        node.prev?.next = node.next
        node.next?.prev = node.prev
    }

    // 移到头部
    private func moveToHead(_ node: DLinkedNode) {
        removeNode(node)
        addToHead(node)
    }

    // 移除尾部（最久未使用）
    private func removeTail() -> DLinkedNode {
        let node = tail.prev!
        removeNode(node)
        return node
    }
}

Python 版

python

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

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> DLinkedNode
        self.head = DLinkedNode()  # 虚拟头
        self.tail = DLinkedNode()  # 虚拟尾
        self.head.next = self.tail
        self.tail.prev = self.head

    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.val

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.val = value
            self._move_to_head(node)
        else:
            node = DLinkedNode(key, value)
            self.cache[key] = node
            self._add_to_head(node)
            if len(self.cache) > self.capacity:
                removed = self._remove_tail()
                del self.cache[removed.key]

    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

复杂度

get：时间 O(1)
put：时间 O(1)
空间：O(capacity)

3. 变式：LFU 简介

LFU（Least Frequently Used）淘汰访问频率最低的数据。LeetCode 460 需要维护两个哈希表：频率到节点链表 + key 到节点。

Python 简化实现思路：

python

# LFU 核心思想：
# freq_table[f] = 频率为 f 的所有节点（按 LRU 排序）
# key_table[key] = 节点
# min_freq = 当前最小频率
# get/put 时更新频率，频率变化时移动到新频率链表头部

4. 易错点

⚠️ 虚拟头尾节点要在初始化时互连，否则空指针
⚠️ 淘汰尾部时别忘了从哈希表中删除对应 key
⚠️ Swift 中链表节点是引用类型，修改 prev/next 会影响实际链表
⚠️ capacity 可能为 0，需要特殊处理（虽然 LeetCode 题目保证 >= 1）

5. 推荐刷题清单

题号	题名	难度	关键
146	LRU 缓存	Medium	哈希+双链表
460	LFU 缓存	Hard	频率+LRU
432	全 O(1) 的数据结构	Hard	双向链表+哈希

LRU 缓存 ​

你将学到 ​

1. 概念 ​

2. 完整实现 ​

Swift 版 ​

Python 版 ​

复杂度 ​

3. 变式：LFU 简介 ​

4. 易错点 ​

5. 推荐刷题清单 ​

延伸阅读 ​