lfu cache的核心难点在于如何o(1)获取最小频次下最久未使用的节点。需用双哈希表（key→node、freq→双向链表）加min_freq变量协同维护频次与时间双维度，避免遍历导致退化。
LFU Cache的核心难点在哪
LFU（Least Frequently Used）缓存淘汰策略要求：当缓存满时，优先剔除访问频次最低的项；若多个项频次相同，则剔除最久未使用的那个。这比LRU多一层维度——既要维护频次，又要保证同频次下按时间排序。
Python标准库没有现成的LFU实现，functools.lru_cache 是LRU，不满足需求。手写时最容易卡在「如何高效获取当前最小频次对应的最老节点」上——不能每次淘汰都遍历全部键值对，否则 put 和 get 会退化到 O(n)。
用双哈希表 + 频次链表结构实现O(1)操作
主流高效做法是组合三类结构：
-
key_to_node：dict，映射 key → 节点（含 value、freq、prev/next） -
freq_to_list：dict，映射 freq → 双向链表头尾（该频次下所有节点组成的LRU链表） -
min_freq：int，记录当前所有存活节点中的最小频次
每次 get(key)：
- 若命中，从原频次链表中摘下该节点，插入
freq+1对应的链表头部（即“最新使用”），更新min_freq（若原链表为空且原频次等于min_freq，则min_freq += 1）
每次 put(key, value)：
- 若 key 已存在：同
get更新频次 - 若 key 不存在：
- 若缓存已满，从
freq_to_list[min_freq]的尾部（最老节点）删除 - 新建节点，插入
freq_to_list[1]头部，并设min_freq = 1
- 若缓存已满，从
注意：链表必须支持 O(1) 插入头部、O(1) 删除任意节点（所以得用双向链表，节点自带 prev/next）。
Python里别直接用list或deque模拟链表
有人尝试用 collections.deque 存每个频次的 key 列表，再配合 dict 存 value 和 freq —— 这会导致删除任意位置节点变成 O(n)，因为 deque 不支持 O(1) 删除中间元素；而 list 的 pop(0) 或 remove() 也是 O(n)。
正确做法是手写一个轻量 Node 类，并维护每个链表的 head 和 tail 哑节点（sentinel），例如：
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.freq = 1
self.prev = None
self.next = None
然后为每个频次维护独立的链表（可复用同一套增删逻辑）。不要图省事用索引或列表位置隐式表示顺序。
边界情况和易错点
-
min_freq 只在「删除节点导致某频次链表变空」且该频次恰好是当前 min_freq 时才更新；新增节点不会重置它（除非是首次 put）
- 删除节点时，务必同步从
key_to_node 中 pop 掉该 key，否则内存泄漏 + 逻辑错乱
- 插入新节点到
freq=1 链表后，如果原 min_freq > 1，要设为 1；但若之前已有 freq=1 的节点，min_freq 不变
- 所有链表操作（插入、删除、移动）必须同时更新节点的
prev/next 和对应链表头尾的指针，漏掉任一端都会断链
min_freq 只在「删除节点导致某频次链表变空」且该频次恰好是当前 min_freq 时才更新；新增节点不会重置它（除非是首次 put）key_to_node 中 pop 掉该 key，否则内存泄漏 + 逻辑错乱freq=1 链表后，如果原 min_freq > 1，要设为 1；但若之前已有 freq=1 的节点，min_freq 不变prev/next 和对应链表头尾的指针，漏掉任一端都会断链实际调试时，遇到 get 返回旧值、或淘汰了错误 key，八成是链表指针没更新全，或者 min_freq 没及时降级。
频次维度叠加时间维度后，状态分支明显变多，测试时至少覆盖：单 key 多次 get、跨频次 put、满容时连续 put 触发淘汰、同频次下多次 get 后淘汰行为——这些地方最容易露馅。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
