如何在Python中用双向链表和哈希表手写LFU缓存结构-Python教程-PHP中文网

不能只用 dict 实现 LFU，因为 dict 无法 O(1) 获取最小频次候选集及动态迁移节点；需结合双向链表（按频次组织节点）和两个哈希表（cache 索引节点、freq_map 管理频次链表），并维护 min_freq 与空链表清理逻辑。

如何在python中用双向链表和哈希表手写lfu缓存结构

为什么不能只用 `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+ 需要开启：辅助功能 + 屏幕录制权限

下载

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，不应影响前者频次