Walkthrough ｜ LRU Cache 实现（阶段 4 练习答案）¶

对应练习：phase-04-components.md 4.9 练习任务 2 应用：topics/markdown-rendering-optimization.md 的 tokenCache

目标¶

实现一个 O(1) 读 / 写 / 删除的 LRU Cache： - get(key) —— O(1) 读，更新访问顺序 - set(key, value) —— O(1) 写，超过容量淘汰最旧 - delete(key) —— O(1) 删 - 容量 = 500（参考 Claude Code TOKEN_CACHE_MAX）

关键洞察：JS 的 `Map` 天然保序¶

JavaScript 的 Map 保留插入顺序。Map.keys().next().value 取最旧插入的 key。

const m = new Map()
m.set('a', 1)
m.set('b', 2)
m.set('c', 3)

// 第一次插入的 key
const oldest = m.keys().next().value  // 'a'

这意味着 LRU 可以用 Map 实现，O(1)！

完整实现（30 行）¶

export class LRUCache<K, V> {
  private cache = new Map<K, V>()

  constructor(private maxSize: number = 500) {}

  get(key: K): V | undefined {
    if (!this.cache.has(key)) return undefined

    // ⭐ 关键：刷新访问顺序
    // 删除再重新插入，让它变成"最新"
    const value = this.cache.get(key)!
    this.cache.delete(key)
    this.cache.set(key, value)

    return value
  }

  set(key: K, value: V): void {
    // 如果 key 已存在，先删除（避免重复 set 后位置不变）
    if (this.cache.has(key)) {
      this.cache.delete(key)
    } else if (this.cache.size >= this.maxSize) {
      // ⭐ 容量满：淘汰最旧的（第一个 key）
      const oldestKey = this.cache.keys().next().value
      if (oldestKey !== undefined) {
        this.cache.delete(oldestKey)
      }
    }

    this.cache.set(key, value)
  }

  has(key: K): boolean {
    return this.cache.has(key)
  }

  delete(key: K): boolean {
    return this.cache.delete(key)
  }

  get size(): number {
    return this.cache.size
  }

  clear(): void {
    this.cache.clear()
  }
}

测试（10 个）¶

import { describe, expect, it } from 'vitest'
import { LRUCache } from './lru.js'

describe('LRUCache', () => {
  it('1. get returns undefined for missing key', () => {
    const c = new LRUCache<string, number>(3)
    expect(c.get('x')).toBeUndefined()
  })

  it('2. set and get', () => {
    const c = new LRUCache<string, number>(3)
    c.set('a', 1)
    expect(c.get('a')).toBe(1)
  })

  it('3. set overwrites existing', () => {
    const c = new LRUCache<string, number>(3)
    c.set('a', 1)
    c.set('a', 2)
    expect(c.get('a')).toBe(2)
    expect(c.size).toBe(1)
  })

  it('4. exceeds maxSize → evicts oldest', () => {
    const c = new LRUCache<string, number>(3)
    c.set('a', 1)
    c.set('b', 2)
    c.set('c', 3)
    c.set('d', 4)  // 'a' 被淘汰
    expect(c.get('a')).toBeUndefined()
    expect(c.get('b')).toBe(2)
    expect(c.get('c')).toBe(3)
    expect(c.get('d')).toBe(4)
  })

  it('5. get on existing key updates recency', () => {
    const c = new LRUCache<string, number>(3)
    c.set('a', 1)
    c.set('b', 2)
    c.set('c', 3)
    c.get('a')  // 刷新 'a' 的访问顺序
    c.set('d', 4)  // 'b' 被淘汰（不是 'a'）
    expect(c.get('a')).toBe(1)
    expect(c.get('b')).toBeUndefined()
    expect(c.get('c')).toBe(3)
    expect(c.get('d')).toBe(4)
  })

  it('6. delete removes key', () => {
    const c = new LRUCache<string, number>(3)
    c.set('a', 1)
    expect(c.delete('a')).toBe(true)
    expect(c.get('a')).toBeUndefined()
    expect(c.size).toBe(0)
  })

  it('7. has works', () => {
    const c = new LRUCache<string, number>(3)
    c.set('a', 1)
    expect(c.has('a')).toBe(true)
    expect(c.has('b')).toBe(false)
  })

  it('8. size is correct', () => {
    const c = new LRUCache<string, number>(3)
    expect(c.size).toBe(0)
    c.set('a', 1)
    expect(c.size).toBe(1)
    c.set('a', 2)  // 覆盖
    expect(c.size).toBe(1)
  })

  it('9. clear works', () => {
    const c = new LRUCache<string, number>(3)
    c.set('a', 1)
    c.set('b', 2)
    c.clear()
    expect(c.size).toBe(0)
    expect(c.get('a')).toBeUndefined()
  })

  it('10. handles complex values', () => {
    const c = new LRUCache<string, { x: number }>(3)
    c.set('a', { x: 1 })
    expect(c.get('a')).toEqual({ x: 1 })
  })
})

应用到 Claude Code 的 tokenCache¶

// src/components/Markdown.tsx 推测
import { LRUCache } from '../utils/lruCache.js'  // 我们手写的

const TOKEN_CACHE_MAX = 500
const tokenCache = new LRUCache<string, Token[]>(TOKEN_CACHE_MAX)

function getTokensFromCache(text: string): Token[] | null {
  return tokenCache.get(text) ?? null
}

function setTokensInCache(text: string, tokens: Token[]): void {
  tokenCache.set(text, tokens)
}

// 改进：用 hash 作 key（注释里提到 #24180 RSS regression 修复）
function getTokensFromCacheByHash(text: string): Token[] | null {
  const hash = hashContent(text)
  return tokenCache.get(hash) ?? null
}

为什么用 hash 而不是 text： - text 可能 100K 字符 → key 占大量内存 - hash 永远 16~64 字节 - 500 项 × 16 bytes = 8KB（key 占用）

性能测试¶

// 性能基准
const c = new LRUCache<number, number>(10_000)

// set 10K 项
const t0 = performance.now()
for (let i = 0; i < 10_000; i++) c.set(i, i)
const t1 = performance.now()
console.log(`set 10K: ${t1 - t0}ms`)  // ~1ms

// get 10K 次
for (let i = 0; i < 10_000; i++) c.get(i)
const t2 = performance.now()
console.log(`get 10K: ${t2 - t1}ms`)  // ~1ms

// 总共 ~2ms（10K 操作）

O(1) 实测确认。

常见错误¶

错误 1：用 Array 实现（O(n) 复杂度）¶

// ❌ 错的
class BadLRU<K, V> {
  private items: Array<[K, V]> = []
  get(key: K): V | undefined {
    return this.items.find(([k]) => k === key)?.[1]  // O(n)
  }
}

// ✅ 对的
class GoodLRU<K, V> {
  private cache = new Map<K, V>()  // O(1)
  get(key: K): V | undefined {
    return this.cache.get(key)  // O(1)
  }
}

错误 2：get 不更新访问顺序¶

// ❌ 错的（虽然简单，但不是真正的 LRU）
get(key: K): V | undefined {
  return this.cache.get(key)  // 不更新顺序
}

// ✅ 对的（真正的 LRU）
get(key: K): V | undefined {
  if (!this.cache.has(key)) return undefined
  const value = this.cache.get(key)!
  this.cache.delete(key)
  this.cache.set(key, value)  // 刷新到最新
  return value
}

错误 3：set 超过容量时淘汰错的¶

// ❌ 错的：淘汰"刚加的"（逻辑反了）
set(key: K, value: V): void {
  if (this.cache.size >= this.maxSize) {
    const newestKey = this.cache.keys().next().value  // ❌ 第一个是最旧，不是最新
    this.cache.delete(newestKey)
  }
  this.cache.set(key, value)
}

// ✅ 对的
set(key: K, value: V): void {
  if (this.cache.has(key)) {
    this.cache.delete(key)  // 重新插入以刷新
  } else if (this.cache.size >= this.maxSize) {
    const oldestKey = this.cache.keys().next().value  // ✅ 第一个插入的 = 最旧
    this.cache.delete(oldestKey)
  }
  this.cache.set(key, value)
}

错误 4：边界 - 容量为 0 或负数¶

// ❌ 错的：没处理
constructor(maxSize: number) {
  this.maxSize = maxSize
}

// ✅ 对的：处理 0 / 负数
constructor(maxSize: number) {
  this.maxSize = Math.max(0, maxSize)
}

进阶：用 WeakMap 替代¶

如果 key 是对象，且想让 key 被 GC 时自动清缓存，用 WeakMap：

// WeakMap 没有迭代能力（不能做 LRU）
// 但如果只想要"key 不再被引用就清掉"，用 WeakMap
const cache = new WeakMap<object, V>()

限制：WeakMap 不能迭代，所以不能做 LRU（无法找最旧的 key）。

Claude Code 的选择： - tokenCache 用 Map（LRU 淘汰最旧） - StructuredDiff 的 NAPI cache 用 WeakMap（patch 对象 GC 时自动清）

进阶：泛型 LRU¶

// 泛型版本
export class LRUCache<K, V> {
  private cache = new Map<K, V>()

  constructor(private readonly maxSize: number) {
    if (maxSize < 0) throw new Error('maxSize must be >= 0')
  }

  get(key: K): V | undefined { /* ... */ }
  set(key: K, value: V): void { /* ... */ }
  // ...
}

// 用法
const stringCache = new LRUCache<string, number>(100)
const objCache = new LRUCache<{ id: string }, User>(100)

关键洞察¶

1. JS 的 `Map` 天然保序 → LRU 用 Map¶

不用自己实现双向链表。
Map.keys().next().value = 最旧的 key。
delete + set = 移到最新。

2. "delete + set" 是 LRU 的核心操作¶

O(1) 删除 + O(1) 插入 = O(1) 移到最新。
这是 Map 比 Object 强的地方（Object 没保序）。

3. 选择 Map vs WeakMap¶

Map：需要迭代、LRU 淘汰 → 选 Map
WeakMap：key 是对象、希望自动 GC → 选 WeakMap
Claude Code 两种都用（按场景选）

4. 容量大小的 trade-off¶

大容量 → 命中率高 + 内存大
小容量 → 命中率低 + 内存小
Claude Code TOKEN_CACHE_MAX = 500 是经验值（注释说踩过 "turn50→turn99 RSS regression" 坑）

配套资源¶

真实用法：src/components/Markdown.tsx（推测）
LRU 应用清单：
Markdown token cache
任何"昂贵计算的 memoize"场景
对比 WeakMap：topics/native-napi-integration.md 的 cache 选择