C++实现高性能LFU缓存淘汰机制 _ 频率链表与时间复杂度分析【源码】

LFU缓存需O(1)定位最低频且最久未用的key，故须用“频率链表+每频LRU双向链表”结构；std::list因无法O(1)定位节点而不适用，须手写Node并用unordered_map映射指针；minFreq通过淘汰时动态检查freq_to_head并均摊O(1)维护。 LFU 缓存不是靠“最近用没用”淘汰，而是靠“总共用了多少次”；直接用 套计数再排序， 和 都会退化到 O(n)，根本达不到高性能要求。 为什么必须拆成频率链表 + 最小堆或双向链表嵌套？ 核心矛盾在于：要 O(1) 找到当前最低频次的 key，还要 O(1) 在该频次内剔除最久未使用的那个——单层结构做不到。所以标准解法是「频率为维度建链表，每个频率节点挂一个 LRU 风格的双向链表」。 这样： 只需把 key 从 freq 链表的旧节点移到 freq+1 节点头部； 溢出时直接取 minFreq 对应链表的尾部节点即可。 minFreq 不能只靠遍历找，必须在每次 或 后动态维护 每个 节点的链表必须支持 O(1) 插入、删除、移动，所以得用自定义双向链表（不用 ，因为没法 O(1) 定位某 node） 映射必须用 ，否则定位开销毁掉整体复杂度 为什么不适合做内部链表？ 是 O(1)，但前提是你得先拿到 iterator。而你在 时只知道 key，不知道它在哪个 freq 链表里的位置——除非你额外存一个 映射，但这会让插入/移动逻辑变得极易出错（迭代器失效、跨 list 移动需先 erase 再 splice）。 立即学习 “ C++免费学习笔记（深入） ”； 更稳的做法是手写一个 结构，含 / 指针，并用 存 key 到节点指针的映射。 示例片段： C知道 CSDN推出的一款AI技术问答工具 下载 如何 O(1) 维护 minFreq？ minFreq 不是静态值，它会在以下情况变化： 新 key 插入时，minFreq = 1 某个 freq 链表被清空（比如所有 freq=2 的 key 全被 get 升到 freq=3），此时若原 minFreq == 2，就得往上涨 关键点：**只在 触发淘汰时才需要检查并更新 minFreq**； 不会降低任何 freq 链表长度，所以不影响 minFreq。 做法是：用一个 记录每个 freq 对应的链表头（或哨兵），再配一个 变量。每次淘汰前，检查 是否为空（或只剩哨兵），为空则 并重试，直到非空。 注意：这个 while 循环看似不 O(1)，但均摊下来仍是 O(1)，因为每个 freq 最多被“跳过”一次。 实际编码最容易漏掉的三个细节 很多人实现能跑通基础 case，但一压测就丢 key 或频次错乱，问题常出在这三处： 时若 key 存在，必须先从原 freq 链表中 unlink 该 node，再插入到 freq+1 链表头部；漏掉 unlink 就会造成 node 出现在两个链表里 替换老 key 时，如果 key 已存在，要复用原 node（只改 和 ，并移动位置），而不是 new 一个——否则内存泄漏 + 原 key 还挂在旧链表里 所有链表操作（insert head / remove node / move node）必须同时更新 node 的 / 和对应链表头尾指针，少更新一个就会断链 高频缓存场景下， 值可能很大，但真正活跃的 freq 很少，所以 map 实际大小远小于最大 freq，空间可控。真正的瓶颈往往不在算法，而在指针操作的手动管理是否严密。