LFU缓存淘汰机制的核心原理
LFU（Least Frequently Used）缓存淘汰机制的核心逻辑是优先淘汰访问频率最低的数据，当多个数据频率相同时，通常再按照最近访问时间淘汰最久未访问的数据。相比LRU缓存仅关注访问时间，LFU更适配访问频率稳定的业务场景，比如静态资源缓存、热点数据缓存等。
核心数据结构设计
要实现高性能的LFU缓存，需要结合三种核心结构：哈希表、频率链表、双向链表。哈希表用于快速定位缓存节点，频率链表按访问频率从小到大组织，每个频率节点下挂载一个双向链表，存储该频率下所有缓存节点的访问顺序。
- 缓存节点：存储键、值、当前访问频率、前后指针
- 频率节点：存储频率值、前后指针、该频率下的缓存节点链表头尾指针
- 全局哈希表：键映射到缓存节点，快速查找
- 最小频率变量：记录当前缓存中的最小访问频率，淘汰时快速定位
C++实现完整源码
以下是完整的LFU缓存实现代码，包含插入、访问、淘汰所有核心逻辑：
#include <unordered_map>
#include <iostream>
// 缓存节点定义
struct CacheNode {
int key;
int value;
int freq; // 当前访问频率
CacheNode* prev;
CacheNode* next;
CacheNode(int k, int v) : key(k), value(v), freq(1), prev(nullptr), next(nullptr) {}
};
// 频率节点定义，每个频率对应一个双向链表存储该频率的缓存节点
struct FreqNode {
int freq; // 频率值
FreqNode* prev;
FreqNode* next;
CacheNode* head; // 该频率下缓存节点链表头（最近访问）
CacheNode* tail; // 该频率下缓存节点链表尾（最久未访问）
FreqNode(int f) : freq(f), prev(nullptr), next(nullptr), head(nullptr), tail(nullptr) {}
};
class LFUCache {
private:
int capacity;
int minFreq; // 当前最小访问频率
std::unordered_map<int, CacheNode*> keyMap; // 键到缓存节点的映射
std::unordered_map<int, FreqNode*> freqMap; // 频率到频率节点的映射
FreqNode* freqHead; // 频率链表头（最小频率）
FreqNode* freqTail; // 频率链表尾（最大频率）
// 从缓存节点链表中移除指定节点
void removeCacheNode(CacheNode* node, FreqNode* fNode) {
if (node->prev) {
node->prev->next = node->next;
} else {
// 是链表头节点
fNode->head = node->next;
}
if (node->next) {
node->next->prev = node->prev;
} else {
// 是链表尾节点
fNode->tail = node->prev;
}
// 如果该频率下没有缓存节点了，删除频率节点
if (fNode->head == nullptr) {
removeFreqNode(fNode);
// 如果删除的是最小频率节点，更新最小频率
if (fNode->freq == minFreq) {
minFreq++;
}
}
delete node;
}
// 从频率链表中移除指定频率节点
void removeFreqNode(FreqNode* fNode) {
if (fNode->prev) {
fNode->prev->next = fNode->next;
} else {
freqHead = fNode->next;
}
if (fNode->next) {
fNode->next->prev = fNode->prev;
} else {
freqTail = fNode->prev;
}
freqMap.erase(fNode->freq);
delete fNode;
}
// 将缓存节点添加到指定频率节点的缓存链表头部（最近访问位置）
void addCacheToFreqHead(CacheNode* node, FreqNode* fNode) {
node->next = fNode->head;
node->prev = nullptr;
if (fNode->head) {
fNode->head->prev = node;
} else {
// 链表为空，头尾都指向该节点
fNode->tail = node;
}
fNode->head = node;
}
// 新增频率节点到频率链表头部（最小频率位置）
FreqNode* addFreqNodeToHead(int freq) {
FreqNode* newNode = new FreqNode(freq);
newNode->next = freqHead;
if (freqHead) {
freqHead->prev = newNode;
} else {
freqTail = newNode;
}
freqHead = newNode;
freqMap[freq] = newNode;
return newNode;
}
public:
LFUCache(int cap) : capacity(cap), minFreq(0), freqHead(nullptr), freqTail(nullptr) {}
~LFUCache() {
// 释放所有缓存节点
for (auto& pair : keyMap) {
delete pair.second;
}
// 释放所有频率节点
FreqNode* cur = freqHead;
while (cur) {
FreqNode* next = cur->next;
delete cur;
cur = next;
}
}
int get(int key) {
if (capacity <= 0) return -1;
auto it = keyMap.find(key);
if (it == keyMap.end()) {
return -1;
}
CacheNode* node = it->second;
// 更新节点频率
int oldFreq = node->freq;
FreqNode* oldFreqNode = freqMap[oldFreq];
// 从旧频率节点中移除该缓存节点
removeCacheNode(node, oldFreqNode);
// 新频率
int newFreq = oldFreq + 1;
node->freq = newFreq;
// 查找或创建新频率节点
FreqNode* newFreqNode = nullptr;
auto freqIt = freqMap.find(newFreq);
if (freqIt == freqMap.end()) {
// 频率节点不存在，创建并插入到频率链表对应位置（按频率递增，插入到旧频率节点后面）
newFreqNode = new FreqNode(newFreq);
newFreqNode->prev = oldFreqNode;
newFreqNode->next = oldFreqNode->next;
if (oldFreqNode->next) {
oldFreqNode->next->prev = newFreqNode;
} else {
freqTail = newFreqNode;
}
oldFreqNode->next = newFreqNode;
freqMap[newFreq] = newFreqNode;
} else {
newFreqNode = freqIt->second;
}
// 将缓存节点添加到新频率节点的链表头部
addCacheToFreqHead(node, newFreqNode);
return node->value;
}
void put(int key, int value) {
if (capacity <= 0) return;
auto it = keyMap.find(key);
if (it != keyMap.end()) {
// 键已存在，更新值并调用get逻辑更新频率
it->second->value = value;
get(key);
return;
}
// 键不存在，需要插入新节点
if (keyMap.size() >= capacity) {
// 缓存已满，执行淘汰：淘汰最小频率下的最久未访问节点
FreqNode* minFreqNode = freqMap[minFreq];
CacheNode* toRemove = minFreqNode->tail;
keyMap.erase(toRemove->key);
removeCacheNode(toRemove, minFreqNode);
}
// 创建新缓存节点，频率为1
CacheNode* newNode = new CacheNode(key, value);
// 查找频率1的节点是否存在
auto freqIt = freqMap.find(1);
FreqNode* freq1Node = nullptr;
if (freqIt == freqMap.end()) {
// 频率1节点不存在，创建并放到频率链表头部
freq1Node = addFreqNodeToHead(1);
minFreq = 1; // 新插入的节点频率为1，是最小频率
} else {
freq1Node = freqIt->second;
}
// 将新节点添加到频率1节点的链表头部
addCacheToFreqHead(newNode, freq1Node);
keyMap[key] = newNode;
}
};
频率链表相关操作的时间复杂度分析
我们通过频率链表的特性来分析核心操作的时间复杂度：
| 操作类型 | 时间复杂度 | 说明 |
|---|---|---|
| get操作 | O(1) | 哈希表查找缓存节点O(1)，频率链表和缓存链表的插入删除都是指针操作O(1)，整体常数时间 |
| put操作（插入新键） | O(1) | 哈希表插入O(1)，缓存满时淘汰最小频率节点也是O(1)，其余操作和get一致 |
| put操作（更新已有键） | O(1) | 等同于先get再更新值，所有操作都是常数时间 |
| 淘汰操作 | O(1) | 通过minFreq变量直接定位最小频率节点，再取该节点链表尾的节点淘汰，无需遍历 |
实现注意事项
在实际使用上述实现时，需要注意以下几点：
- 当缓存容量为0时，所有操作都应直接返回空或失败，避免无效操作
- 频率节点的删除需要同步更新minFreq变量，否则会出现淘汰时找不到最小频率节点的问题
- 缓存节点和频率节点都需要手动管理内存，避免内存泄漏，析构函数中需要遍历释放所有节点
- 如果业务场景需要支持更多类型的键值对，可以将实现改为模板类，适配不同数据类型
总结
基于频率链表和哈希表的C++ LFU缓存实现，所有核心操作都能达到O(1)的时间复杂度，性能表现优异。频率链表的设计避免了每次更新频率时遍历所有节点的开销，通过最小频率变量快速定位淘汰目标，整体逻辑清晰且高效。开发者可以根据自身业务需求调整节点存储的内容，比如添加过期时间、访问时间戳等扩展功能。