Skip to content

IMPLEMENTATION_DETAILS.md

Latest commit

 

History

History
203 lines (135 loc) · 5.03 KB

IMPLEMENTATION_DETAILS.md

File metadata and controls

203 lines (135 loc) · 5.03 KB

LRU Cache 实现细节

1. 问题本质

LRU 是 Least Recently Used 的缩写，意思是“最近最少使用”。缓存容量固定时，如果插入新数据导致容量超限，就淘汰最久没有被访问的数据。

本题的难点是同时满足：

  • 能快速根据 key 找到 value。
  • 能快速知道谁是最近使用、谁是最久未使用。
  • 命中、更新、淘汰都要尽量做到 O(1)。

单独使用数组或链表，查找 key 太慢。单独使用哈希表，又无法直接维护使用顺序。因此经典解法是：

哈希表 + 双向链表

2. 数据结构

当前实现的核心成员：

std::lent cap;
std::unordered_map<int, Node*> cache;
Node* head;
Node* tail;
  • cap：缓存最大容量。
  • cache：key 到链表节点的映射。
  • head：最近使用节点。
  • tail：最久未使用节点。

节点结构：

struct Node {
    int key;
    int value;
    Node* prev;
    Node* next;
};

节点里必须保存 key，因为淘汰尾节点时，需要用这个 key 从哈希表里删除对应记录。

3. 核心不变量

实现过程中要保持这些关系：

  • head 指向最近使用的节点。
  • tail 指向最久未使用的节点。
  • 空缓存时：head == nullptr，tail == nullptr，cache.empty()。
  • 非空缓存时：head->prev == nullptr，tail->next == nullptr。
  • cache 中的每个 key 都指向链表里的一个有效节点。
  • 链表中的每个节点，都能在 cache 中通过自己的 key 找到。
  • cache.size() <= cap。

只要这些关系成立，缓存行为就是稳定的。

4. get(key)

流程：

  1. 在 cache 中查找 key。
  2. 找不到，返回 -1。
  3. 找到节点，说明这次访问了它。
  4. 把节点移动到链表头部。
  5. 返回节点保存的 value。

为什么要移动到头部：

被 get 命中的 key 刚刚被使用过，所以它变成最近使用。

复杂度：

  • 哈希表查找平均 O(1)。
  • 双向链表移动节点 O(1)。
  • 总体平均 O(1)。

5. put(key, value)

put 有两种情况。

key 已存在

流程：

  1. 在 cache 中找到节点。
  2. 更新节点的 value。
  3. 把节点移动到链表头部。

更新也算一次使用，因此需要移动到头部。

key 不存在

流程：

  1. 如果容量是 0，直接返回。
  2. 创建新节点。
  3. 把新节点插到链表头部。
  4. 在 cache 中记录 key -> node。
  5. 如果容量超限，删除尾节点。
  6. 从 cache 中删除被淘汰节点的 key。
  7. 释放被淘汰节点。

复杂度平均 O(1)。

6. 为什么使用双向链表

当一个节点被访问后，需要从原位置删除，再插入到头部。

如果使用单向链表，只知道当前节点地址时，无法 O(1) 找到它的前驱节点，删除会比较麻烦。

双向链表节点保存 prev 和 next，所以删除当前节点只需要：

node->prev->next = node->next;
node->next->prev = node->prev;

再处理头尾边界即可。

7. 辅助函数

add_to_front

把节点插入到链表头部。

需要处理：

  • 原链表为空：head 和 tail 都指向新节点。
  • 原链表非空：新节点成为头节点，旧头节点的 prev 指向新节点。

remove_node

把一个已存在的节点从链表中摘下来，但不释放内存。

需要处理：

  • 删除头节点。
  • 删除尾节点。
  • 删除中间节点。
  • 删除唯一节点。

move_to_front

如果节点已经是头节点，什么都不用做。

否则：

先 remove_node，再 add_to_front

remove_tail

删除链表尾节点并返回该节点指针，由调用方负责从哈希表删除 key 并释放内存。

8. 容量为 0 的情况

如果 cap == 0，任何 put 都不应该保存数据。

这个边界很容易漏掉。如果不提前返回，插入后又立刻淘汰也能工作，但逻辑更绕，还容易引出空指针处理问题。

9. 测试覆盖点

当前测试覆盖了：

  • 基本插入和淘汰。
  • get 命中后更新最近使用顺序。
  • 更新已有 key 的 value。
  • 容量为 1。
  • 容量为 0。
  • 查询不存在 key 不改变顺序。

这些场景基本能覆盖 LRU 手写题里最常见的错误。

10. 复杂度

操作 时间复杂度 说明
get 平均 O(1) 哈希查找 + 链表移动
put 平均 O(1) 哈希查找/插入 + 链表插入/删除
contains 平均 O(1) 哈希查找
keys O(n) 用于测试和调试，需要遍历链表

空间复杂度是 O(capacity)。

11. 面试讲解顺序

推荐这样讲：

  1. 先说只用哈希表无法知道淘汰谁，只用链表查找太慢。
  2. 引出“哈希表 + 双向链表”。
  3. 说明链表头是最近使用，链表尾是最久未使用。
  4. 讲 get：查到后移动到头部。
  5. 讲 put：更新已有节点或插入新节点。
  6. 讲容量超限：删除尾节点，同时从哈希表删除 key。
  7. 强调节点必须保存 key，否则淘汰时不知道从哈希表删谁。