Skip to content

LRU 缓存

中等 约 50 分钟

你将构建什么

一个 LRUCache 类,get(key) 和 put(key, value) 均为 O(1),在超出容量时淘汰最久未使用的条目。

学习目标

  • 结合哈希表(O(1) 查找)与双向链表(O(1) 更新访问顺序)
  • 实现带溢出淘汰的 get 和 put
  • 推理操作复杂度
  • 在注释中论证设计选择

前置要求

  • 对象作为哈希表
  • 链表概念(见 project-11)
  • O(1) 复杂度推理

步骤

  1. 1

    选择数据结构

    决定如何实现 O(1) 的 get 和 put。经典做法:用 Map(或对象)做 key→node 查找,用双向链表跟踪访问顺序。在注释中记录你的选择。

  2. 2

    定义节点与缓存骨架

    定义双向链表节点(value、prev、next)和接受 capacity 的 LRUCache 构造函数。初始化 map 和链表 head/tail 哨兵。

  3. 3

    实现 get

    get(key) 存在则返回值并将该节点移到头部(最近使用);不存在返回 -1。验收标准:缺失键返回 -1;存在键返回值并标记为最近使用。

  4. 4

    实现带淘汰的 put

    put(key, value):键存在则更新值并移到头部;新键则加到头部并增加 size。若 size 超过容量,淘汰最久未使用(尾部)并从 map 移除。验收:超出容量后最旧条目被移除。

  5. 5

    用场景验证

    编写测试:缓存容量 2; put(1,1), put(2,2), get(1)→1, put(3,3)(淘汰键 2), get(2)→-1, get(3)→3, put(4,4)(淘汰键 1), get(1)→-1, get(3)→3, get(4)→4。所有断言必须通过。

自己动手试试

你学到了什么

你组合两种数据结构以在一个真实抽象上实现 O(1) 操作——LRU 缓存用于 CPU 缓存、浏览器缓存、Redis 及许多数据库。

相关资源

相关课程

  • 对象

    map 提供 O(1) 键查找。

  • 循环

    链表操作使用指针重赋值。

相关术语

  • 缓存

    近期数据的快速存储。

相关术语

新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。

  • 缓存

    近期数据的快速存储。

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误

← 返回主题