LFU缓存通过频次桶链表+双向哈希映射实现O(1)操作，辅以时间戳支持同频LRU淘汰，用计数器数组加速minFreq查找，并采用原子操作与内存池提升并发性能。

如果您需要在 C++ 中实现一个高性能的 LFU（Least Frequently Used）缓存淘汰机制，并要求支持 O(1) 时间复杂度的最小频率查找与键值访问，则必须打破传统哈希表+优先队列组合带来的性能瓶颈。以下是实现该优化算法的核心步骤：

一、基于频次桶链表 + 双向哈希映射的结构设计

该方法通过维护一个按访问频次分层的双向链表（每个节点为一个频次桶），配合两个哈希表：一个映射 key → value/freq/node_ptr，另一个映射 freq → 桶链表头节点，从而保证 get 和 put 操作均摊 O(1) 时间复杂度。最小频率始终为当前非空桶中最低 freq 值，可实时追踪。

1、定义 CacheNode 结构体，包含 key、value、freq 字段，并保留前驱与后继指针。

2、声明 unordered_map::iterator> keyTable，用于 O(1) 定位任意 key 对应的缓存节点迭代器。

3、声明 unordered_map> freqBuckets，以频次为键，存储对应频次下所有节点组成的链表。

4、维护 minFreq 整型变量，在每次 put 导致新频次桶创建或旧桶清空时更新其值。

5、在 get 操作中，先查 keyTable 获取节点，将其从原 freqBuckets[freq] 中移除，插入 freqBuckets[freq + 1] 头部，并更新 keyTable 中的迭代器位置，最后检查并更新 minFreq。

6、在 put 操作中，若 key 存在则执行 get 后更新 value；若不存在且 size 达上限，则从 freqBuckets[minFreq] 尾部删除节点，并从 keyTable 中擦除对应项；随后将新节点插入 freqBuckets[1] 头部，设置 keyTable 映射，并置 minFreq = 1。

二、引入时间戳辅助的频次桶内 LRU 排序

当多个键具有相同最小频次时，传统 LFU 未规定淘汰顺序，易导致抖动。本方法在每个频次桶内部采用 LRU 策略，即按最近访问时间排序，确保同频次下最久未用者优先淘汰，提升缓存命中率。

1、扩展 CacheNode 结构，增加 timestamp 字段（如 std::chrono::steady_clock::now().time_since_epoch().count()）。

2、修改 freqBuckets 的 value 类型为 list，并在每次 get 或 put 触发频次提升时，将节点移至对应 freq+1 桶的头部；同时在同频次桶内调整位置时，仅需在该桶内执行 splice 操作。

3、在淘汰阶段，遍历 freqBuckets[minFreq] 链表尾部节点，选取 timestamp 最小者（即最久未访问）执行删除。

4、为避免 timestamp 溢出或精度问题，使用 unsigned long long 存储毫秒级时间戳，并在构造函数中初始化 baseTime 作为偏移参考。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

三、使用计数器数组替代哈希桶加速 minFreq 查找

针对高频更新场景下频繁查询 minFreq 的开销，本方法改用固定长度数组 + 栈式索引管理，将 minFreq 查询降为 O(1)，适用于最大频次可预估（如 ≤ 10000）的嵌入式或高吞吐服务场景。

1、声明 vector> freqStack，索引 i 对应频次 i，栈中压入该频次下所有活跃 key 值。

2、声明 vector freqCount，记录每个频次当前活跃 key 数量，用于快速判断某频次桶是否为空。

3、维护 minFreq 变量，每次 put 新 key 时设为 1；每次淘汰后，自增 minFreq 直至 freqCount[minFreq] > 0。

4、在 get 操作中，先从 freqStack[freq] 弹出 key，再压入 freqStack[freq + 1]，同步更新 freqCount[freq] 和 freqCount[freq + 1]。

5、在 put 淘汰阶段，直接访问 freqStack[minFreq].top() 获取待删 key，调用 erase 删除 keyTable 中条目，并更新 freqCount[minFreq]；若此时 freqCount[minFreq] == 0，则递增 minFreq 直至非零。

四、无锁原子计数器 + 内存池优化并发访问性能

在多线程环境下，频次更新和 minFreq 维护易成竞争热点。本方法采用 std::atomic 替代普通 int，并结合对象内存池减少 new/delete 开销，使 LFU 缓存在高并发读写下仍保持低延迟。

1、将 freq 字段声明为 std::atomic，所有 increment 使用 fetch_add(1, std::memory_order_relaxed)。

2、实现简易内存池类 PoolAllocator，预先分配 N 个 CacheNode 对象并以单向链表组织空闲列表。

3、重载 CacheNode 的 operator new 和 operator delete，分别从池中获取和归还节点。

4、将 keyTable 和 freqBuckets 声明为 mutable，并在 get/put 方法中使用 shared_mutex（C++17）进行读写分离保护：读操作使用 lock_shared()，写操作使用 lock()

5、minFreq 变量声明为 std::atomic，在每次更新时使用 store(new_val, std::memory_order_relaxed)，读取时使用 load(std::memory_order_relaxed)。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！