LRU 与 LFU 的缓存淘汰策略

LRU 淘汰最久未使用的键。JavaScript 的 Map 保持插入顺序，因此命中一个键时先删除再写回，就能把它移动到队尾；容量超限时删除 map.keys().next().value 即可。

LFU 淘汰访问频率最低的键。只有一个 Map 已经不够，因为每次访问都可能把节点从频率 f 移到 f + 1。

LFU 的三个索引

要让 get 和 put 保持均摊 O(1)，实现通常维护：

• key -> node：直接找到缓存节点；
• frequency -> doubly linked list：管理同频节点的最近使用顺序；
• minFreq：直接定位当前应淘汰的频率。

节点访问后，从旧频率链表移除并插入新频率链表头部。如果旧链表清空且它正是 minFreq，最小频率增加。同频淘汰时选择链表尾部，于是规则变成“先淘汰最低频率；频率相同再淘汰最久未使用”。

LRU 的状态只有一条时间顺序，LFU 则是“频率分桶 + 桶内时间顺序”。后者命中策略更细，但状态和维护成本也更高；选择哪一种取决于访问模式，而不是复杂实现天然更好。