JS/TS 手写 LRU（双向链表 + 哈希）

什么是 LRU

LRU（Least Recently Used）= 最近最少使用。当缓存满了需要淘汰一个时，淘汰最久没被访问的那个。

直觉是合理的：你刚刚用过的东西，大概率马上还会用；放了很久没碰的，留着也是占空间。

典型应用：

浏览器的 HTTP 缓存
Vue 的 <keep-alive>（用 LRU 决定哪些组件实例要被销毁）
Redis、MySQL Buffer Pool 的内存淘汰
算法面试题 LeetCode 146

接口长什么样

class LRUCache<K, V> {
  constructor(capacity: number);
  get(key: K): V | -1;        // 命中：返回值并把它"提到最前"；未命中：返回 -1
  put(key: K, value: V): void; // 已存在：更新并提前；不存在：插入；超容则淘汰最久未用的
}

核心要求：get 和 put 都要 O(1)。

思路：为什么是”双向链表 + 哈希表”

逐步推导：

要 O(1) 查 key → 用 Map / Object。但 Map 解决不了”提到最前”和”删最末尾”
要 O(1) 把元素移动到头部 → 用链表。但单向链表删除某个节点需要先 O(n) 找它的前驱
要 O(1) 删除任意节点 → 双向链表。每个节点都知道自己的 prev，删除只需改 4 个指针

最后两者结合：

Map: key  →  Node                  双向链表（按"最近使用"排序，head 是最新）
─────────────                      ─────────────────────────────────────────
'a'  →  ┌─────────┐                ┌──────┐  ┌──────┐  ┌──────┐
'b'  →  │ Node 'a'│ ←──────────→   │ head │ ⇄│ 'a'  │ ⇄│ 'b'  │ ⇄ ... ⇄ tail
'c'  →  └─────────┘                └──────┘  └──────┘  └──────┘

get(key)：Map 拿到 node → 把 node 移到链表头 → 返回 node.value
put(key, val)：
- key 已存在：更新值 + 移到头
- key 不存在：新建 node 插到头 + Map 记录；如果超容，删掉链表 tail 前的那个节点（最久未用）+ Map 删 key

每一步都是 O(1)。

实现一：用原生 `Map`（推荐，最短最快）

JS 的 Map 有一个冷门但关键的特性：它保留插入顺序，并且 delete + set 等价于”提到末尾”。利用这点几行代码搞定 LRU：

// lru.ts
export class LRUCache<K, V> {
  private cache = new Map<K, V>();

  constructor(private readonly capacity: number) {}

  get(key: K): V | -1 {
    if (!this.cache.has(key)) return -1;
    // 关键：删掉重新 set，相当于"提到最末尾"
    const value = this.cache.get(key)!;
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key: K, value: V): void {
    if (this.cache.has(key)) {
      this.cache.delete(key); // 已存在，先删，让它重新 set 到末尾
    } else if (this.cache.size >= this.capacity) {
      // 超容：淘汰最旧的（Map 的第一个 key 就是最老的）
      const oldestKey = this.cache.keys().next().value as K;
      this.cache.delete(oldestKey);
    }
    this.cache.set(key, value);
  }
}

约定：这里把”最近用的”放在 Map 的末尾（和上图相反），淘汰时取 keys().next().value 拿最老的——更省代码。

测试一下：

const lru = new LRUCache<string, number>(2);
lru.put("a", 1);
lru.put("b", 2);
lru.get("a");      // 1，此时顺序：b → a
lru.put("c", 3);   // 容量满，淘汰 b。顺序：a → c
lru.get("b");      // -1（已被淘汰）
lru.get("a");      // 1

这一版是面试时最快写完且不出错的版本。但面试官常追问：”不让你用 Map 的有序性，怎么写？”——下面这版手撕双向链表。

实现二：手撕双向链表 + 哈希

// lru-linked.ts
class DLinkedNode<K, V> {
  prev: DLinkedNode<K, V> | null = null;
  next: DLinkedNode<K, V> | null = null;
  constructor(public key: K, public value: V) {}
}

export class LRUCache<K, V> {
  private map = new Map<K, DLinkedNode<K, V>>();
  // 用伪头尾节点（dummy head / tail）省去边界判断
  private head: DLinkedNode<K, V>;
  private tail: DLinkedNode<K, V>;

  constructor(private readonly capacity: number) {
    this.head = new DLinkedNode<K, V>(null as any, null as any);
    this.tail = new DLinkedNode<K, V>(null as any, null as any);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key: K): V | -1 {
    const node = this.map.get(key);
    if (!node) return -1;
    this.moveToHead(node);
    return node.value;
  }

  put(key: K, value: V): void {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this.moveToHead(existing);
      return;
    }
    const node = new DLinkedNode(key, value);
    this.map.set(key, node);
    this.addToHead(node);

    if (this.map.size > this.capacity) {
      // 淘汰 tail 前的那个节点（最久未用）
      const lru = this.tail.prev!;
      this.removeNode(lru);
      this.map.delete(lru.key);
    }
  }

  // —— 链表辅助方法（都是 O(1)）——

  private addToHead(node: DLinkedNode<K, V>) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next!.prev = node;
    this.head.next = node;
  }

  private removeNode(node: DLinkedNode<K, V>) {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  private moveToHead(node: DLinkedNode<K, V>) {
    this.removeNode(node);
    this.addToHead(node);
  }
}

几个关键设计：

伪头尾节点（dummy nodes）：addToHead / removeNode 不用判 null，省一堆 if
node 里要存 key：淘汰时要用 key 从 map 里删，没有 key 就只能反查
moveToHead = removeNode + addToHead：复用，少出 bug
map.size 判断在 set 之后：先无脑加，再统一处理超容

复杂度分析

操作	时间	空间
`get`	O(1)	—
`put`	O(1)	—
整体空间	—	O(capacity)

两种实现都是 O(1)。实现一（Map） 在 V8 引擎里实测比手写双向链表略快（Map 内部优化得很好），代码也短；实现二胜在面试时能展示对底层数据结构的理解。

业务里直接用：给函数结果加 LRU 缓存

把上面 LRUCache 包成一个高阶函数，瞬间给任意纯函数加 LRU 缓存：

// memoize-lru.ts
export function memoizeLRU<Args extends unknown[], R>(
  fn: (...args: Args) => R,
  capacity = 100,
  keyFn: (...args: Args) => string = (...a) => JSON.stringify(a),
) {
  const cache = new LRUCache<string, R>(capacity);

  return function memoized(...args: Args): R {
    const key = keyFn(...args);
    const hit = cache.get(key);
    if (hit !== -1) return hit as R;

    const result = fn(...args);
    cache.put(key, result);
    return result;
  };
}

// 用法
const heavyCalc = (n: number) => {
  console.log("calc", n);
  return n * n;
};

const cached = memoizeLRU(heavyCalc, 50);
cached(2); // calc 2 → 4
cached(2); // 直接命中 → 4

适合给”参数空间无限但热点集中”的函数加速：搜索结果、远程接口、复杂表达式求值等。

QA: 为什么不直接用 Map，还要"哈希 + 双向链表"？

💬点击展开/收起

JS 的 Map 之所以能省事，是因为它自带插入顺序——这是 V8 内部用类似双向链表的结构实现的。

但是：

不是所有语言都有”有序 Map”：Java 的 HashMap 不保证顺序（要用 LinkedHashMap），Go 的 map 顺序甚至是随机的。讲算法本身、跨语言移植时，必须用”哈希 + 双向链表”
面试考察的是数据结构能力：直接 Map.delete + set 等于在用别人造好的轮子，面试官想看你能不能造轮子
Map 的”提前”操作 O(1) 但常数较大：delete + set 有两次哈希计算 + 两次内部链表操作，手写双向链表只有指针赋值，理论上更快（实测 V8 下差距不大）

实践推荐：业务代码用实现一，面试 / 写库用实现二。

QA: LRU、LFU、FIFO 有什么区别？

💬点击展开/收起

三种都是缓存淘汰策略，区别在”淘汰谁”：

策略	淘汰依据	适用场景	数据结构
FIFO	最早进入的	顺序敏感、热点不明显	队列
LRU	最久没访问的	热点集中、有时间局部性	双向链表 + 哈希
LFU	访问次数最少的	长期热点稳定（如热门商品）	多个频率桶 + 哈希

LRU 是工程里的”默认选择”，因为：

实现简单、O(1)
时间局部性在大多数场景下都成立（刚用过的还会被用）
抗”突发冷数据冲刷”能力比 FIFO 好

LFU 在长期热点场景更优，但实现更复杂（LeetCode 460 是 hard），且对”过去很热但现在没人用”的数据反应迟钝（需要配合”老化”机制）。

踩坑提示

map.size > capacity 还是 >=：要在 set 之后判断 >，否则 capacity=2 时只能存 1 个
node 必须存 key：淘汰时要从 map 里删 key，不存就只能 O(n) 反查
get 时记得 moveToHead：忘了的话 LRU 就变成 FIFO 了
TypeScript 严格模式下 dummy node：new DLinkedNode(null as any, null as any) 是常见妥协；也可以让 key / value 类型加 | undefined，但代码会变啰嗦
多线程场景：浏览器主线程是单线程不用管；Node.js Worker 共享内存时要加锁，纯 JS LRU 不是线程安全的

小结

LRU = 最近最少使用，淘汰最久没碰的
要 O(1) 查 + O(1) 移动 + O(1) 删除任意节点 → 哈希表 + 双向链表
JS 里用 Map 的有序性 4 行能搞定，面试里手写双向链表版展示功底
一个通用 memoizeLRU 高阶函数就能让任何纯函数获得缓存能力

JS/TS 手写 LRU（双向链表 + 哈希）

O(1) 读写的缓存淘汰算法，前端面试高频题

什么是 LRU

接口长什么样

思路：为什么是”双向链表 + 哈希表”

实现一：用原生 `Map`（推荐，最短最快）

实现二：手撕双向链表 + 哈希

复杂度分析

业务里直接用：给函数结果加 LRU 缓存

QA: 为什么不直接用 Map，还要"哈希 + 双向链表"？

QA: LRU、LFU、FIFO 有什么区别？

踩坑提示

小结

CATALOG

FEATURED TAGS

FRIENDS

什么是 LRU

接口长什么样

思路：为什么是”双向链表 + 哈希表”

实现一：用原生 Map（推荐，最短最快）

实现二：手撕双向链表 + 哈希

复杂度分析

业务里直接用：给函数结果加 LRU 缓存

QA: 为什么不直接用 Map，还要"哈希 + 双向链表"？

QA: LRU、LFU、FIFO 有什么区别？

踩坑提示

小结

CATALOG

FEATURED TAGS

FRIENDS

实现一：用原生 `Map`（推荐，最短最快）