LFU（Least Frequently Used）缓存淘汰机制的核心逻辑是优先淘汰访问频率最低的数据，当缓存满时，把使用次数最少的元素移除。传统LFU实现中，每次淘汰都需要遍历所有元素的频率来找到最小值，时间复杂度较高，在高并发场景下会成为性能瓶颈。我们可以通过优化数据结构，将最小频率查找的时间复杂度从O(n)降到O(1)。
核心数据结构设计
要实现高性能的LFU缓存，需要组合使用三种结构：
- 哈希表 key_to_node：存储键到缓存节点的映射，用于O(1)时间找到对应缓存元素
- 哈希表 freq_to_list：存储频率到双向链表的映射，每个频率对应一个双向链表，链表中是该频率下的所有缓存节点，方便按频率顺序维护节点
- 最小频率变量 min_freq：记录当前缓存中的最小访问频率，淘汰时直接从这个频率对应的链表中取尾部节点即可
缓存节点需要包含键、值、访问频率、以及所在双向链表的前后指针，具体定义如下：
struct LFUNode {
int key;
int value;
int freq;
LFUNode* prev;
LFUNode* next;
LFUNode(int k, int v) : key(k), value(v), freq(1), prev(nullptr), next(nullptr) {}
};
双向链表操作封装
为了方便操作每个频率对应的双向链表，我们封装一个双向链表类，支持添加节点到头部、移除节点、移除尾部节点（淘汰用）的操作：
class DoubleList {
private:
LFUNode* head;
LFUNode* tail;
int size;
public:
DoubleList() {
head = new LFUNode(-1, -1);
tail = new LFUNode(-1, -1);
head->next = tail;
tail->prev = head;
size = 0;
}
// 添加节点到链表头部
void addToHead(LFUNode* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
size++;
}
// 移除指定节点
void removeNode(LFUNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
size--;
}
// 移除尾部节点（最久未访问的，用于淘汰）
LFUNode* removeTail() {
if (size == 0) return nullptr;
LFUNode* node = tail->prev;
removeNode(node);
return node;
}
int getSize() {
return size;
}
};
LFU缓存核心实现
接下来实现LFU缓存的主体类，包含构造函数、get方法、put方法，以及频率更新和最小频率维护的逻辑：
#include <unordered_map>
using namespace std;
class LFUCache {
private:
unordered_map<int, LFUNode*> key_to_node;
unordered_map<int, DoubleList*> freq_to_list;
int capacity;
int min_freq;
// 更新节点的频率
void updateFreq(LFUNode* node) {
int old_freq = node->freq;
// 从旧频率的链表中移除节点
freq_to_list[old_freq]->removeNode(node);
// 如果旧频率的链表为空，且旧频率是最小频率，更新最小频率
if (freq_to_list[old_freq]->getSize() == 0) {
delete freq_to_list[old_freq];
freq_to_list.erase(old_freq);
if (min_freq == old_freq) {
min_freq++;
}
}
// 更新节点频率
node->freq++;
int new_freq = node->freq;
// 如果新频率对应的链表不存在，创建新链表
if (freq_to_list.find(new_freq) == freq_to_list.end()) {
freq_to_list[new_freq] = new DoubleList();
}
// 将节点添加到新频率链表的头部
freq_to_list[new_freq]->addToHead(node);
}
public:
LFUCache(int cap) : capacity(cap), min_freq(0) {}
int get(int key) {
if (capacity == 0) return -1;
// 如果键不存在，返回-1
if (key_to_node.find(key) == key_to_node.end()) {
return -1;
}
LFUNode* node = key_to_node[key];
// 更新节点频率
updateFreq(node);
return node->value;
}
void put(int key, int value) {
if (capacity == 0) return;
// 如果键已经存在，更新值并调整频率
if (key_to_node.find(key) != key_to_node.end()) {
LFUNode* node = key_to_node[key];
node->value = value;
updateFreq(node);
return;
}
// 如果缓存已满，淘汰最小频率的节点
if (key_to_node.size() == capacity) {
// 从最小频率对应的链表中移除尾部节点
DoubleList* min_freq_list = freq_to_list[min_freq];
LFUNode* removed_node = min_freq_list->removeTail();
// 如果链表为空，删除链表并清理映射
if (min_freq_list->getSize() == 0) {
delete min_freq_list;
freq_to_list.erase(min_freq);
}
// 从键映射中删除被淘汰的节点
key_to_node.erase(removed_node->key);
delete removed_node;
}
// 创建新节点
LFUNode* new_node = new LFUNode(key, value);
// 新节点频率为1，添加到频率1的链表中
if (freq_to_list.find(1) == freq_to_list.end()) {
freq_to_list[1] = new DoubleList();
}
freq_to_list[1]->addToHead(new_node);
// 更新键映射
key_to_node[key] = new_node;
// 新插入的节点频率为1，所以最小频率重置为1
min_freq = 1;
}
~LFUCache() {
// 清理所有节点和链表
for (auto& pair : key_to_node) {
delete pair.second;
}
for (auto& pair : freq_to_list) {
delete pair.second;
}
}
};
优化点说明
上述实现的核心优化在于最小频率查找的O(1)复杂度：
- 传统LFU实现需要遍历所有节点找最小频率，时间复杂度O(n)，本实现通过维护
min_freq变量，直接记录当前最小频率，淘汰时直接从对应链表取节点 - 每次更新节点频率时，会检查旧频率的链表是否为空，如果为空且旧频率等于
min_freq，就将min_freq加1，保证min_freq始终有效 - 新插入的节点频率固定为1，所以每次插入后
min_freq都会重置为1，符合LFU的逻辑
使用示例
以下是该LFU缓存的使用示例，验证功能正确性：
#include <iostream>
using namespace std;
int main() {
LFUCache* cache = new LFUCache(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，键2已被淘汰
cout << cache->get(3) << endl; // 返回3
cache->put(4, 4); // 淘汰键3（频率为1）
cout << cache->get(1) << endl; // 返回1
cout << cache->get(3) << endl; // 返回-1，键3已被淘汰
cout << cache->get(4) << endl; // 返回4
delete cache;
return 0;
}
该实现的所有操作（get、put）时间复杂度均为O(1)，空间复杂度为O(capacity)，适合对性能要求较高的缓存场景使用。