lfu缓存不能只用collections.counter，因为counter仅统计频次，无法在o(1)内淘汰“频次最低且最久未用”的项；必须用哈希表映射key到节点、频次到双向链表，并维护全局最小频次min_freq以支持o(1)淘汰与频次迁移。
LFU缓存为什么不能只用 collections.Counter？
因为 Counter 只能统计频次，无法在 O(1) 时间内淘汰「频次最低且最久未用」的项。LFU 要求每次 get 或 put 都更新频次，并在满时快速定位最小频次组里的最老节点——这必须靠双向链表维护访问时序，再配合频次字典分组管理。
常见错误是试图用两个哈希表（key→freq + freq→[key]）硬凑，结果删除时无法知道哪个 key 在同频次下更早插入，导致淘汰逻辑错乱。
- 频次变化必须触发节点在不同频次链表间迁移，不是简单加一
- 每个频次对应一个独立的双向链表（按访问时间从新到旧排列）
- 要额外记录当前全局最小频次
min_freq，避免遍历所有频次找最小
LFUCache 类里必须维护的三个核心结构
不是「一个字典 + 一个列表」能搞定的。实际需要：
-
self.cache：哈希表，key → node，支持 O(1) 查找节点 -
self.freq_map：哈希表，freq → doubly-linked list，每个频次下挂一个按 LRU 顺序组织的链表 -
self.min_freq：整数，指向当前所有存活 key 中最小频次，put淘汰时直接取self.freq_map[self.min_freq]尾部节点
注意：self.freq_map 的 value 不是 list，而是自定义链表头（带 dummy 节点），否则无法 O(1) 删除尾部；node 实例需包含 key、val、freq、prev、next 五个属性。
get 和 put 中频次更新的陷阱
看似只是 freq += 1，但漏掉链表迁移就全盘失效：
-
get(key)命中后，要把该node从freq_map[old_freq]中移出，再插入到freq_map[old_freq + 1]的头部（表示最新访问） -
put(key, value)若 key 已存在，同样要迁移节点；若不存在且缓存满，则先删freq_map[min_freq]尾部节点，再插入新节点到freq_map[1]头部 - 删节点后，若
freq_map[old_freq]变空，且old_freq == self.min_freq，则必须更新self.min_freq += 1
示例片段（迁移逻辑）：
old_list = self.freq_map[node.freq]<br>old_list.remove(node)<br>node.freq += 1<br>if node.freq not in self.freq_map:<br> self.freq_map[node.freq] = DoublyLinkedList()<br>self.freq_map[node.freq].append_head(node)<br>if node.freq == 1:<br> self.min_freq = 1<br>elif node.freq - 1 == self.min_freq and old_list.is_empty():<br> self.min_freq += 1
Python 实现中容易被忽略的链表细节
不用 collections.deque，它不支持 O(1) 中间删除；也不用手写 list.pop(0)，那是 O(n)。必须自己实现带 dummy head/tail 的双向链表：
- 每个链表实例含
head和tail两个 dummy 节点，head.next是最新项，tail.prev是最老项 -
append_head(node)：插在head.next前；remove(node)：断开前后指针即可，无需遍历 - 判空不能用
len(list) == 0，而要看head.next is tail - 所有链表操作必须同时更新节点的
prev/next，漏一个就会断链
真正麻烦的不是逻辑，是节点指针在多个链表间切换时，哪一步该清 prev、哪一步该重连 next——写完一定要用「插入-访问-再访问-淘汰」四步走一遍单测。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
