Skip to content
LRU 缓存的 Map 实现：从 V8 OrderedHashMap 到前端缓存架构
概述
ES6 的 Map 对象根据插入顺序保存迭代顺序，利用这一特性可以免去额外的双向链表，直接基于 Map 实现完整的 LRU 缓存。
基本概念
LRU（Least Recently Used）是一种基于访问时间顺序的淘汰策略：当缓存达到容量上限时，移出最近最少被使用的条目。它的基础是时间局部性假设——近期访问过的数据在短时间内更有可能被再次访问。这一假设在分页数据、翻译缓存、API 响应缓存等场景中成立，但在访问分布均匀或随机的模式下帮助有限。
淘汰决策可以看作一条时间线：
text
访问序列: A → B → C → A → D (maxSize = 3)
A: [A] ← A 最新
B: [A, B] ← B 最新
C: [A, B, C] ← C 最新，缓存满
A: [B, C, A] ← A 被重新访问，移到末尾
D: [C, A, D] ← D 插入，B 最久未用，被淘汰基本用法
Map 的迭代顺序与插入顺序一致，因此队尾始终对应最近访问的条目，队首对应最久未访问的条目。每次读取或更新条目时，先将其删除再重新插入，就能让该条目移动到队尾。
LRUCache 类对外只暴露 get 和 put 两个方法：
js
class LRUCache {
constructor(maxSize) {
this.maxSize = maxSize;
this.cache = new Map();
}
get(key) {
if (!this.cache.has(key)) return undefined;
const value = this.cache.get(key);
// 删除再重新插入，将 key 移到队尾
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
put(key, value) {
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);
}
}使用方式：
js
const cache = new LRUCache(3);
cache.put('a', 1);
cache.put('b', 2);
cache.put('c', 3);
cache.get('a'); // 返回 1，同时 'a' 被移到队尾
cache.put('d', 4); // 淘汰 'b'
[...cache.cache.keys()]; // ['c', 'a', 'd']get('a') 命中后，'a' 被删除并重新插入，成为最新条目。插入 'd' 时，'b' 作为最久未访问的键被淘汰。
API
get(key)
- 若
key存在，返回对应的值，并将该键标记为最近使用； - 若
key不存在，返回undefined。 - 副作用：命中时重新排列内部迭代顺序，将命中键移到末尾。
put(key, value)
- 若
key已存在，先移除旧条目，再将新值放入缓存末尾； - 若
key不存在且缓存已满，淘汰队首（最久未访问）的键，然后插入新条目； - 若
key不存在且缓存未满，直接在末尾插入。 - 副作用：可能触发淘汰。
get 未命中时返回 undefined，而非 -1 之类的哨兵值。即使缓存中存储了 undefined，也可以通过 has 方法与未命中区分。如果需要明确的命中标记，可以使用可区分的返回类型：
ts
type CacheResult<V> = { hit: true; value: V } | { hit: false };工作原理
V8 OrderedHashMap 的布局
Map 在 V8 中的底层基于 OrderedHashMap，这是一种将哈希桶与数据条目分离存储的确定性哈希表。其 backing store 是一个连续的 FixedArray，布局如下：
text
┌──────────┬──────────────┬─────────────────────────────────┐
│ Header │ Buckets │ Entries │
│ (3 槽) │ (2ⁿ 个槽) │ (capacity × 3 个槽) │
└──────────┴──────────────┴─────────────────────────────────┘
Header 槽:
[0] numberOfElements — 存活条目数
[1] numberOfDeletedElements — 已删除条目（hole）数
[2] numberOfBuckets — 哈希桶数量
Bucket 槽:
[i] chain_head_index — 该桶链表的首条目索引，-1 表示空桶
Entry 槽 (每组 3 个):
[k] key — 键
[k+1] value — 值
[k+2] chain — 同桶下一个条目的索引，-1 表示链尾查找路径（hash → bucket → 链遍历）与遍历路径（Entries 数组线性扫描）完全解耦。map.keys() 等迭代器直接扫描 Entries 数组并跳过 hole，无需经过哈希桶。这正是 Map 能替换双向链表用于 LRU 的关键——插入顺序天然保存在连续的 Entries 数组中。
Delete 的真实行为
Map.prototype.delete(key) 不会释放条目槽位。它把对应的 key 和 value 槽位替换为内部哨兵 the_hole，并递增 numberOfDeletedElements。这些 hole 只在下一次 rehash（扩容或缩容）时被真正回收。
在 LRU 场景中，每次 get 触发一次 delete（产生一个 hole）加一次 set（在 Entries 末尾追加新条目）。只要 live + deleted < capacity，就不会触发 rehash，操作保持 O(1)。但频繁 put 新键（淘汰旧键）会不断积累 hole，最终可能触发一次 O(N) 的 rehash。
扩容与缩容
| 参数 | 值 |
|---|---|
| 初始 buckets | 2 |
| 初始 capacity | 4 |
| 负载关系 | capacity = buckets × 2 |
| 扩容触发 | live + deleted >= capacity |
| 缩容触发 | live < capacity / 4（即 live < buckets / 2） |
| 64 位最大容量 | 2²⁷（约 1.34 亿条目） |
扩容序列为 4 → 8 → 16 → 32 → 64 …，每次扩大 2 倍。Map 的初始 capacity 为 4，容量随 set 调用逐步增长。若缓存最终达到 512 个条目，期间共经历 8 次 rehash，累计搬迁约 1020 个槽位——这些开销分散在插入过程中，不在构造函数阶段。缩容条件为存活条目数小于 capacity 的四分之一（即桶数的一半），由于 LRU 缓存通常接近满容量，缩容很少发生。
注意点
与 Object 的键顺序对比
Object 的键遍历顺序虽然自 ES2015 起有了规范约束，但行为仍依赖属性类型：整数索引键按数值升序排列，字符串键按插入顺序排列。如果缓存中混合使用数字键和字符串键，for...in 的输出顺序会变得难以预测。Map 对所有键类型统一采用插入顺序，行为更可控。
对象键的哈希与内存
Map 支持对象作为键。V8 在对象内部存储一个随机生成的 32 位哈希值（lazy 生成，之后不变），因此比较基于引用相等（SameValueZero）。结构相同但引用不同的两个对象被视为不同的键。Map 对对象键持有强引用，长生命周期缓存中的对象键会阻止其被垃圾回收，需注意意外的内存驻留。
时间复杂度
| 操作 | 稳态复杂度 | 退化条件 |
|---|---|---|
| get (命中) | O(1) | rehash 时 O(N) |
| get (未命中) | O(1) | — |
| put (不淘汰) | O(1) | rehash 时 O(N) |
| put (淘汰) | O(1) | rehash 时 O(N) |
| keys().next() | O(1) | Entries 中存在大量 hole 时退化 |
稳态下所有操作均为 O(1)。rehash 为 O(N)，通常在 load factor 达到阈值时触发。对于容量在几千以内的缓存，单次 rehash 耗时通常在 0.05–3 ms，对前端渲染帧预算（16.6 ms）影响有限；只有容量达到数万时，才需要关注 rehash 对长任务的贡献。
应用
缓存层解耦
将 LRU 缓存封装为独立层，通过 get / put 与上层交互。使用高阶函数可以进一步分离缓存逻辑与数据获取：
js
function withCache(fetchFn, cache) {
return async (key) => {
const cached = cache.get(key);
if (cached !== undefined) return cached;
const result = await fetchFn(key);
cache.put(key, result);
return result;
};
}这样缓存策略可以独立测试、替换或叠加 TTL 失效层，而不影响数据获取逻辑本身。
并发请求控制
多个并发请求访问同一个未缓存的 key 时，会同时穿透到外部资源（缓存击穿）。可以在缓存外层加入一个 in-flight promise map，让同一个 key 的第一个请求创建 promise，后续请求复用同一个 promise：
js
const inflight = new Map();
async function cachedFetch(key) {
const cached = cache.get(key);
if (cached !== undefined) return cached;
if (inflight.has(key)) return inflight.get(key);
const promise = fetchData(key);
inflight.set(key, promise);
try {
const result = await promise;
cache.put(key, result);
return result;
} finally {
inflight.delete(key);
}
}失效策略
LRU 只负责淘汰，不关心数据是否过期。实际使用时常叠加其他失效维度：
- TTL：为条目附加过期时间，读取时检查是否失效；
- 版本标记：将数据版本号、API 模型版本等放入缓存键，上游数据变更后新键自然命中；
- 主动失效：通过事件或消息队列清除特定 key。
防雪崩与防污染
大量 key 在相近时间过期会造成瞬时负载升高（缓存雪崩）。为 TTL 加上随机抖动（例如 [0.8, 1.2] 倍原始 TTL）可以使过期时间分散。对于顺序翻页类操作污染缓存的问题（例如遍历 1→50 把热点数据挤出），可以考虑 LRU-K 或按访问模式分片，但多数场景下控制 maxSize 已经足够。
可观测性
实际运行中，仅靠 LRU 本身难以判断缓存效果。可以在 LRUCache 中内嵌简单的计数器：
js
class LRUCache {
constructor(maxSize) {
this.maxSize = maxSize;
this.cache = new Map();
this.hits = 0;
this.misses = 0;
this.evictions = 0;
}
get(key) {
if (!this.cache.has(key)) {
this.misses++;
return undefined;
}
this.hits++;
const value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
put(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key);
} else if (this.cache.size >= this.maxSize) {
this.cache.delete(this.cache.keys().next().value);
this.evictions++;
}
this.cache.set(key, value);
}
get hitRate() {
const total = this.hits + this.misses;
return total === 0 ? 0 : this.hits / total;
}
}命中率持续低于 0.3 且淘汰数稳定增长，通常意味着 maxSize 过小或访问模式不适合 LRU。
适用场景与限制
LRU 最大的收益来自减少外部 I/O（网络请求、磁盘读取）。如果缓存的数据仅涉及轻量计算，维护缓存的开销（delete + set）可能已经和重新计算的成本接近，此时引入缓存并不划算。以下场景同样不适合 LRU：
- 数据总量始终小于缓存容量，淘汰逻辑从不触发；
- 访问分布均匀，时间局部性假设不成立，命中率接近随机淘汰；
- 每次访问都使用新的键，缓存一直 miss，put 只消耗内存和 CPU。
在这些情况下，不引入缓存往往是更合适的选择。
演化方向
缓存系统很少一次设计到位，通常会根据实际需求逐步演变。一个常见路径是：无缓存 → 固定容量 LRU → LRU + TTL → 增加版本标记 → IndexedDB 持久化 → 多 Tab 同步。多数前端场景达到 LRU + TTL 就已足够，后续步骤主要在数据一致性要求极高时才需要。