LFU缓存详解（C++语言实现LFU缓存淘汰算法完整教程）

LFU缓存的核心挑战

实现LFU缓存的关键难点在于：如何高效地维护每个键的访问频率，并在O(1)时间内完成插入、获取和淘汰操作。为了达到这个目标，我们需要巧妙地结合哈希表和双向链表。

C++实现LFU缓存

下面我们将使用C++标准库中的 unordered_map 和自定义双向链表来实现LFU缓存。我们的目标是支持以下操作：

• get(key)：获取缓存中的值，若存在则返回值并增加访问频率；否则返回 -1
• put(key, value)：插入或更新键值对，若缓存已满则淘汰频率最低且最久未使用的键

数据结构设计

我们需要两个主要的数据结构：

1. keyMap：哈希表，存储 key → (value, frequency, 节点指针)
2. freqMap：哈希表，存储 frequency → 双向链表（按访问时间排序）

完整C++代码实现

#include <unordered_map>#include <list>#include <algorithm>using namespace std;class LFUCache {private:    struct Node {        int key, value, freq;        Node(int k, int v, int f) : key(k), value(v), freq(f) {}    };    int capacity;    int minFreq;    unordered_map<int, list<Node>::iterator> keyMap;    unordered_map<int, list<Node>> freqMap;public:    LFUCache(int capacity) : capacity(capacity), minFreq(0) {}    int get(int key) {        if (keyMap.find(key) == keyMap.end()) {            return -1;        }        auto nodeIt = keyMap[key];        int val = nodeIt->value;        int freq = nodeIt->freq;        // 从当前频率列表中移除        freqMap[freq].erase(nodeIt);        // 如果当前频率列表为空且是最小频率，则更新minFreq        if (freqMap[freq].empty() && minFreq == freq) {            minFreq++;        }        // 插入到 freq+1 的列表中        freqMap[freq + 1].emplace_front(key, val, freq + 1);        keyMap[key] = freqMap[freq + 1].begin();        return val;    }    void put(int key, int value) {        if (capacity == 0) return;        if (keyMap.find(key) != keyMap.end()) {            // 更新现有键            auto nodeIt = keyMap[key];            int freq = nodeIt->freq;            freqMap[freq].erase(nodeIt);            if (freqMap[freq].empty() && minFreq == freq) {                minFreq++;            }            freqMap[freq + 1].emplace_front(key, value, freq + 1);            keyMap[key] = freqMap[freq + 1].begin();        } else {            // 插入新键            if (keyMap.size() >= capacity) {                // 淘汰最小频率中最久未使用的节点                auto lastNode = freqMap[minFreq].back();                keyMap.erase(lastNode.key);                freqMap[minFreq].pop_back();            }            minFreq = 1;            freqMap[1].emplace_front(key, value, 1);            keyMap[key] = freqMap[1].begin();        }    }};

代码解析

让我们逐段分析这段C++实现的关键部分：

• Node 结构体：包含 key、value 和 freq（访问频率）
• keyMap：快速定位某个 key 对应的节点在哪个 freq 列表中
• freqMap：每个频率对应一个双向链表，链表头部是最新访问的，尾部是最久未访问的
• minFreq：记录当前所有 key 中的最小频率，用于快速淘汰

通过这种设计，get 和 put 操作的时间复杂度均为 O(1)，满足高性能要求。

使用示例

int main() {    LFUCache cache(2);        cache.put(1, 1);    cache.put(2, 2);    cout << cache.get(1) << endl;   // 输出 1    cache.put(3, 3);                // 淘汰 key=2    cout << cache.get(2) << endl;   // 输出 -1    cout << cache.get(3) << endl;   // 输出 3    cache.put(4, 4);                // 淘汰 key=1    cout << cache.get(1) << endl;   // 输出 -1    cout << cache.get(3) << endl;   // 输出 3    cout << cache.get(4) << endl;   // 输出 4        return 0;}

总结

通过本教程，你已经掌握了如何用C++语言实现一个高效的LFU缓存系统。LFU作为经典的缓存淘汰算法，在数据库、操作系统和Web服务中广泛应用。理解其原理和实现方式，不仅能提升你的算法能力，还能在实际项目中优化系统性能。

记住，Least Frequently Used 的核心思想是“频率优先”，而高效实现的关键在于数据结构的巧妙组合。希望这篇教程对你有所帮助！