LFU缓存淘汰机制的核心逻辑是优先淘汰访问频率最低的缓存项，因此最小频率查找算法的效率直接决定了整个缓存的读写性能。在C++中实现该算法时，需要平衡数据结构的内存开销和操作的时间复杂度，避免最小频率查找成为性能瓶颈。
核心数据结构设计
要实现高效的最小频率查找，首先需要设计合适的数据结构。我们可以采用三层结构来存储缓存信息：
- 键到缓存节点的映射：使用
unordered_map<KeyType, Node*>实现O(1)时间复杂度的键查找 - 频率到节点链表的映射：使用
unordered_map<int, list<Node*>>存储同一访问频率下的所有节点，方便频率更新时移动节点 - 最小频率记录变量：用
int min_freq直接记录当前缓存中的最小访问频率，避免遍历所有频率查找
其中缓存节点Node的结构定义如下：
struct Node {
int key; // 缓存键
int value; // 缓存值
int freq; // 访问频率
Node(int k, int v) : key(k), value(v), freq(1) {}
};
最小频率查找算法实现逻辑
最小频率查找的核心目标是快速获取当前访问频率最低的节点列表，因此我们不需要每次都遍历所有频率，而是通过min_freq变量直接定位：
1. 初始化与更新最小频率
当新节点加入缓存时，初始频率为1，此时如果缓存为空，直接将min_freq设为1；如果缓存非空，不需要修改min_freq。
当节点被访问时，频率增加，需要从原频率对应的链表中移除，加入新频率对应的链表。如果原频率对应的链表移除节点后为空，且原频率等于min_freq，则将min_freq加1。
2. 淘汰节点时的查找逻辑
当缓存达到容量上限需要淘汰节点时，直接根据min_freq找到对应的链表，移除链表头部的节点（最早加入的低频率节点），同时从键映射中删除该节点的键即可。
完整源码实现
以下是完整的C++ LFU缓存最小频率查找相关实现代码：
#include <unordered_map>
#include <list>
#include <iostream>
using namespace std;
struct Node {
int key;
int value;
int freq;
Node(int k, int v) : key(k), value(v), freq(1) {}
};
class LFUCache {
private:
int capacity; // 缓存容量
int min_freq; // 当前最小访问频率
unordered_map<int, Node*> key_map; // 键到节点的映射
// 频率到双向链表的映射，链表存储同一频率下的节点，头部是最新访问的，尾部是最早访问的
unordered_map<int, list<Node*>> freq_map;
// 更新节点的访问频率
void update_freq(Node* node) {
int old_freq = node->freq;
// 从原频率链表中移除节点
freq_map[old_freq].remove(node);
// 如果原频率链表为空，且原频率是最小频率，更新最小频率
if (freq_map[old_freq].empty()) {
freq_map.erase(old_freq);
if (min_freq == old_freq) {
min_freq++;
}
}
// 节点频率加1，加入新频率链表
node->freq++;
freq_map[node->freq].push_front(node);
}
public:
LFUCache(int cap) : capacity(cap), min_freq(0) {}
// 获取缓存值
int get(int key) {
if (capacity <= 0) return -1;
auto it = key_map.find(key);
if (it == key_map.end()) {
return -1;
}
Node* node = it->second;
update_freq(node);
return node->value;
}
// 插入或更新缓存
void put(int key, int value) {
if (capacity <= 0) return;
auto it = key_map.find(key);
if (it != key_map.end()) {
// 键已存在，更新值并提升频率
Node* node = it->second;
node->value = value;
update_freq(node);
return;
}
// 键不存在，需要插入新节点
if (key_map.size() >= capacity) {
// 缓存已满，淘汰最小频率的节点
list<Node*>& nodes = freq_map[min_freq];
Node* del_node = nodes.back();
nodes.pop_back();
if (nodes.empty()) {
freq_map.erase(min_freq);
}
key_map.erase(del_node->key);
delete del_node;
}
// 创建新节点，频率为1
Node* new_node = new Node(key, value);
key_map[key] = new_node;
freq_map[1].push_front(new_node);
min_freq = 1; // 新节点频率为1，最小频率一定是1
}
// 析构函数释放内存
~LFUCache() {
for (auto& pair : key_map) {
delete pair.second;
}
}
};
// 测试代码
int main() {
LFUCache cache(2);
cache.put(1, 1);
cache.put(2, 2);
cout << cache.get(1) << endl; // 返回1，节点1频率变为2
cache.put(3, 3); // 淘汰节点2（频率1）
cout << cache.get(2) << endl; // 返回-1
cout << cache.get(3) << endl; // 返回3
cache.put(4, 4); // 淘汰节点1（频率2）
cout << cache.get(1) << endl; // 返回-1
cout << cache.get(3) << endl; // 返回3
cout << cache.get(4) << endl; // 返回4
return 0;
}
性能分析
该实现中，所有核心操作的时间复杂度均为O(1)：
- get操作：键查找O(1)，频率更新O(1)
- put操作：键查找O(1)，淘汰节点时直接通过
min_freq定位O(1)，频率更新O(1) - 最小频率查找：直接读取
min_freq变量，时间复杂度O(1)，避免了遍历所有频率的开销
这种实现方式适合对性能要求较高的场景，相比遍历查找最小频率的实现，在高并发或高频访问场景下性能优势明显。