O(1) 操作的 LFU 缓存

功能说明

LfuCache 按访问频率淘汰数据：容量满时移除频率最低的条目；频率相同则移除最久未使用的条目。它比 LRU 更适合“热点数据长期稳定、偶尔访问的数据应尽快淘汰”的场景，例如 CDN 元数据、推荐候选和搜索结果缓存。实现使用 Map 定位节点、频率到双向链表的映射以及 lowestFrequency 指针，使 get 和 put 都保持 O(1)。

节点记录键、值、频率以及前后指针；同一频率的节点挂在一条链表中，新访问的节点放到链头，因此链尾就是该频率下最久未使用的节点。peek 可以查看值但不提升频率，适合统计或调试。delete 会同步维护频率桶和链表。

关键代码

提升频率时把节点从旧桶摘除，放入新频率桶的头部；如果旧桶空了并且它正是最低频率，就递增最低频率指针：

oldList.remove(node);
if (oldList.size === 0) {
  this.frequencies.delete(oldFrequency);
  if (this.lowestFrequency === oldFrequency) {
    this.lowestFrequency = oldFrequency + 1;
  }
}
node.frequency = oldFrequency + 1;
this.listFor(node.frequency).addFront(node);

淘汰时从最低频率链表的尾部取节点，并从主索引中删除。

使用注意

容量必须为正整数，构造后不能调整；需要动态扩容时应重建缓存。put 已存在的键会更新值并提升频率，这与某些只把 get 视为访问的实现不同。get 未命中返回 undefined，如果缓存值本身可能是 undefined，应改用 has 或哨兵值区分。

lowestFrequency 在删除节点后可能暂时指向空桶，但下一次 put 会重置为 1；在容量已满且最低频率桶确实存在时才会执行淘汰。该实现不是线程安全的，多线程环境需要外部加锁或分片。频率计数没有上限，极端情况下可能增长很大，但 JS 数字在此范围内仍可安全表示。

验证方式

示例容量为 2：写入 a、b 后访问 a，再写入 c 会淘汰频率更低的 b，所以 get("b") 为 undefined。随后访问 c 并写入 d，此时 a、c 频率相同，链表尾部是较早访问的 a，因此 a 被淘汰，get("a") 为 undefined，get("c") 和 get("d") 分别返回 3、4，最终大小为 2。可以调整访问顺序验证同频率下的 LRU 淘汰规则。