不能只用 dict 实现 LFU，因为 dict 无法 O(1) 获取最小频次候选集及动态迁移节点；需结合双向链表（按频次组织节点）和两个哈希表（cache 索引节点、freq_map 管理频次链表），并维护 min_freq 与空链表清理逻辑。
为什么不能只用 dict 实现 LFU？
LFU（Least Frequently Used）要求每次淘汰访问频次最低、且在频次相同时淘汰最久未使用的项。单纯用 dict 只能 O(1) 查，但无法 O(1) 找出当前最小频次的候选集，更无法在频次提升时快速把某个节点从“频次 f”链表移到“频次 f+1”链表——这就需要双向链表按频次组织节点，再用哈希表做快速索引。
核心结构怎么搭：两个哈希表 + 频次双向链表
关键不是写一个链表类，而是明确三者分工：
-
self.cache：dict，键为 key，值为指向双向链表节点的引用（不是数据本身） -
self.freq_map：dict，键为频次f，值为该频次对应的双向链表头节点（或整个链表对象） - 每个链表节点存
key、value、freq，并带prev/next指针；所有同频次节点串成一条双向链表，新访问的节点插在链表尾（便于淘汰头部） - 额外维护
self.min_freq，记录当前所有存活节点中的最小频次，避免每次遍历找最小
注意：self.freq_map 中的链表必须支持 O(1) 头/尾插入、O(1) 中间节点删除（所以必须是双向链表，且节点需持有对所在链表的引用或通过哈希反查）。
get() 和 put() 里频次更新怎么不出错？
这是最容易漏掉逻辑分支的地方：
macOS UI 自动化技能包 —— 用 Python 控制你的 Mac
下载
让 macOS 自动化像说话一样简单 —— 用代码控制你的 Mac，无需学习 AppleScript 系统要求 macOS 14+ (Sonoma) Python 3.9+ 需要开启：辅助功能 + 屏幕录制权限
立即学习“Python免费学习笔记（深入）”；
-
get(key)命中时：先从self.cache[key]拿到节点 → 从原频次链表中删掉它（注意：若该链表因此为空，要更新self.freq_map并检查是否影响self.min_freq）→ 将节点freq+1 → 插入freq+1对应的链表尾部 -
put(key, value)未命中且满容时：必须先淘汰self.freq_map[self.min_freq]的头部节点（即最久未用的那个），删掉它在self.cache中的条目；再插入新节点到freq=1链表尾；此时self.min_freq重置为 1 -
put(key, value)命中时：行为和get类似，只是还要更新value字段，且不改变容量判断逻辑
常见错误：忘记在删除节点后清空空链表（导致 self.freq_map[f] 是空链表，后续 self.min_freq 判断失效）；或在 put 更新已有 key 后没重置 self.min_freq（它只在新增 key 时才确定为 1，更新时不改）。
Python 实现时哪些细节会崩？
不是语法问题，而是设计隐含约束：
- 节点类必须可被哈希（如果用作字典键），但通常我们不用节点做键，而是用
key做键，所以节点无需实现__hash__；但务必实现__eq__如果你打算比较节点（一般不需要） - 不要在链表节点里存强引用到链表本身，否则造成循环引用，影响 GC；用弱引用或干脆不存，靠
self.freq_map[f]查链表 - 初始化时
self.min_freq = 0，但首次put后它变成 1；之后只有当self.freq_map[self.min_freq]被清空时，才执行self.min_freq += 1—— 这个递增必须严格发生在「某次淘汰或更新导致该频次链表变空」之后，不能提前 - 测试边界：连续
put相同 key 五次，它的频次应为 5，且始终在freq_map[5]链表里；中间穿插一次get另一个 key，不应影响前者频次
真正卡住人的永远不是“怎么连指针”，而是 min_freq 的维护时机、空链表的清理节奏、以及命中更新时要不要动 min_freq——这三个点错一个，缓存行为就不可预测。
