时间复杂度LFU缓存淘汰算法详解)
1. 项目概述与LFU核心思想最近在整理一个C缓存系统的学习项目前面几篇聊了缓存的基本概念和LRU的实现这次咱们来啃一块硬骨头——LFULeast Frequently Used最不经常使用淘汰算法的代码实现。如果你做过LeetCode上那道著名的 460. LFU 缓存 就知道这玩意儿比LRU要复杂不少但它的思想在实际系统中非常有用比如数据库的查询缓存、操作系统的页面置换甚至是一些内容分发网络CDN的边缘节点都会用到LFU或其变种来提升热点数据的命中率。LFU的核心逻辑很简单当缓存空间不足时淘汰掉那个被访问频率最低的数据。听起来比LRU的“淘汰最久未使用”更合理对吧毕竟一个被频繁访问的“热数据”理应比一个偶尔被访问一次的“冷数据”更有资格留在缓存里。但实现起来麻烦就出在这个“频率”上。它不是一个静态值而是一个动态变化的计数器。每次访问一个键它的频率就要加一。当需要淘汰时我们得从所有最低频率的键中再按照LRU或者FIFO的规则挑一个出来扔掉通常选择最久未访问的以解决“历史频率高但近期冷”的问题。这就意味着我们需要一种数据结构能同时高效地支持以下操作根据键key快速获取值value和其当前访问频率。根据频率freq快速找到所有处于该频率的键并且能从中移除一个通常是最早加入的。当某个键被访问频率增加时能将它从一个频率链表移动到更高一级的频率链表中。这比LRU只需要维护一个按访问时间排序的双向链表要复杂得多。网上很多简单的LFU实现在get和put操作时时间复杂度是O(N)的这在数据量大的时候根本不可用。我们这次的目标是实现一个get和put操作时间复杂度都在O(1)的LFU缓存。这需要精心设计数据结构的组合。2. 数据结构设计O(1)复杂度的关键要实现O(1)的操作我们必须摒弃遍历。核心思路是使用三个哈希表unordered_map和一组双向链表list进行组合。下面我们来拆解每个部分的作用。2.1 核心数据结构拆解key_table(键到节点的映射)类型unordered_mapint, Node键用户传入的键key。值一个Node结构体里面至少包含key,value,freq当前访问频率。作用这是最基础的映射。通过key我们可以在O(1)时间内找到对应的值value和其当前的频率freq。没有它get操作就无法快速完成。freq_table(频率到链表的映射)类型unordered_mapint, listNode键访问频率freq。值一个双向链表std::list里面存放所有处于该频率的Node。这个链表的顺序就是访问时间顺序链表头部是最新访问的尾部是最久未访问的。作用这是实现LFU淘汰的关键。它把相同频率的节点组织在一起。当我们需要淘汰时直接找到min_freq对应的链表移除其尾部的节点最久未访问就是O(1)操作。当某个节点频率增加时我们也需要把它从旧频率链表移动到新频率链表。min_freq(当前最小频率)类型int作用一个整型变量记录当前缓存中所有键的最低访问频率。淘汰操作依赖它。维护这个变量是保证O(1)淘汰的关键否则我们可能需要遍历freq_table来寻找最小频率。capacity(缓存容量)类型size_t作用缓存的最大容量在构造函数中传入。2.2 Node结构体与迭代器存储这里有一个非常重要的细节。当我们把一个Node放入std::list后如果后续要移动或删除它我们需要知道它在链表中的确切位置迭代器。但list的迭代器在元素被插入后才会确定并且如果我们将Node对象直接存入list再通过key_table找到这个Node我们无法直接获取到它在freq_table对应链表里的迭代器。因此常见的优化做法是key_table不直接存储Node对象而是存储一个包含value,freq以及迭代器的结构。这个迭代器指向该节点在freq_table[freq]这个链表中的位置。我们定义两个核心结构// 链表节点存储键值对和频率 struct Node { int key; int value; int freq; // 访问频率 // 构造函数方便初始化 Node(int k, int v, int f) : key(k), value(v), freq(f) {} }; // 在键表中存储的条目包含值和指向频率链表中位置的迭代器 struct KeyEntry { int value; int freq; std::listNode::iterator it; // 指向对应频率链表中的节点 };这样key_table的类型就变成了unordered_mapint, KeyEntry。通过key找到KeyEntry后我们立刻能拿到value、freq以及它在链表中的位置it。这个设计是连接key_table和freq_table的桥梁是实现O(1)移动和删除的核心。3. 核心操作流程与代码实现有了上面的设计图我们来看get和put这两个核心方法如何实现。我们先给出LFUCache类的整体框架。#include unordered_map #include list #include iostream class LFUCache { private: int capacity; // 缓存容量 int minFreq; // 当前最小频率 std::unordered_mapint, KeyEntry keyTable; // 键到条目的映射 std::unordered_mapint, std::listNode freqTable; // 频率到节点链表的映射 // 辅助函数增加某个键的频率 void increaseFreq(int key) { // 具体实现见下文 } public: LFUCache(int capacity) : capacity(capacity), minFreq(0) { // 构造函数 } int get(int key) { // 具体实现见下文 } void put(int key, int value) { // 具体实现见下文 } };3.1get操作查询并更新频率get操作的逻辑是如果key不存在于keyTable中直接返回-1。如果存在 a. 通过keyTable[key]找到对应的KeyEntry拿到value和freq。 b.调用increaseFreq(key)函数更新该键的频率。这是LFU的核心。 c. 返回value。int get(int key) { if (capacity 0) return -1; // 边界情况处理 auto it keyTable.find(key); if (it keyTable.end()) { return -1; // 键不存在 } // 找到条目 KeyEntry entry it-second; int value entry.value; // 提升该键的频率 increaseFreq(key); return value; }3.2put操作插入或更新put操作的逻辑更复杂一些需要处理插入新键和更新旧键两种情况以及缓存满时的淘汰。如果key已存在更新其value并调用increaseFreq(key)提升其频率。这相当于一次访问。如果key不存在 a.如果缓存已满keyTable.size() capacity则需要进行淘汰。 i. 找到minFreq对应的链表freqTable[minFreq]。 ii. 该链表的尾部节点就是最不经常使用且最久未访问的节点将其移除。 iii. 同时从keyTable中也删除这个键。 iv.注意移除节点后如果freqTable[minFreq]链表变空理论上可以删除这个空链表并且minFreq需要更新。但在本次插入后新键的频率为1minFreq必然会被设置为1。所以我们可以选择不立即更新minFreq而是在increaseFreq或下次淘汰时处理。一种更清晰的写法是在淘汰后如果链表为空就删除freqTable[minFreq]这个键但minFreq可以暂时不变因为紧接着要插入频率为1的新节点。 b.创建新节点频率freq初始化为1。 c. 将新节点插入到freqTable[1]链表的头部表示最新访问。 d. 在keyTable中记录这个新键其KeyEntry包含value、freq1以及上一步插入节点后返回的迭代器。 e.将minFreq重置为1。因为新加入的键频率最低就是1。void put(int key, int value) { if (capacity 0) return; // 边界情况处理 auto it keyTable.find(key); if (it ! keyTable.end()) { // 键已存在更新值并提升频率 KeyEntry entry it-second; entry.value value; // 更新值 increaseFreq(key); // 提升频率 return; } // 键不存在需要插入 // 检查容量是否已满 if (keyTable.size() capacity) { // 缓存已满需要淘汰 // 找到最小频率对应的链表 auto minFreqList freqTable[minFreq]; // 链表尾部的节点是最久未访问的 Node nodeToRemove minFreqList.back(); minFreqList.pop_back(); // 从链表中移除 keyTable.erase(nodeToRemove.key); // 从键表中移除 // 如果移除后链表变空可以清理这个频率桶可选 if (minFreqList.empty()) { freqTable.erase(minFreq); // 注意此时minFreq可能失效但接下来我们会插入freq1的节点所以直接设为1即可 } } // 插入新节点频率为1 int newFreq 1; // 将新节点插入频率1的链表头部 freqTable[newFreq].push_front(Node(key, value, newFreq)); // 获取刚插入节点的迭代器 auto newIt freqTable[newFreq].begin(); // 在键表中记录 keyTable[key] {value, newFreq, newIt}; // 新插入节点频率为1更新最小频率 minFreq 1; }3.3increaseFreq辅助函数频率提升的核心这是整个LFU实现中最精妙的部分它负责将一个键从一个频率链表移动到更高一级的频率链表。步骤通过keyTable[key]找到对应的KeyEntry获取当前的freq和链表迭代器it。从freqTable[freq]链表中通过迭代器it删除该节点。重要检查如果删除节点后freqTable[freq]链表变空了并且当前的freq恰好等于minFreq那么说明这个频率层级已经没有节点了最小频率minFreq需要增加minFreq。因为接下来这个节点的频率会变成freq1而freq这个频率已经不存在任何节点了。将节点的频率freq加一。将更新后的节点插入到freqTable[freq1]链表的头部。更新keyTable[key]中的freq和迭代器it。void increaseFreq(int key) { KeyEntry entry keyTable[key]; int oldFreq entry.freq; auto oldIt entry.it; // 1. 从旧频率链表中移除节点 freqTable[oldFreq].erase(oldIt); // 2. 检查旧频率链表是否变空并且是否是最小频率 if (freqTable[oldFreq].empty()) { freqTable.erase(oldFreq); // 清理空链表 if (oldFreq minFreq) { minFreq; // 最小频率需要提升 } } // 3. 提升频率 int newFreq oldFreq 1; // 4. 将节点插入新频率链表的头部 // 注意我们需要更新节点的freq但Node是存储在list里的我们需要修改它 // 更优的做法是在list中删除旧节点插入一个全新的Node。 // 但为了清晰我们修改原Node的freq然后重新插入。 // 实际上在erase后旧的Node对象已经被销毁。我们需要基于key和value新建一个。 // 因此我们需要从entry中取出value。 int value entry.value; freqTable[newFreq].push_front(Node(key, value, newFreq)); auto newIt freqTable[newFreq].begin(); // 5. 更新键表中的记录 entry.freq newFreq; entry.it newIt; }4. 完整代码与测试案例将上述所有部分组合起来就得到了一个完整的、O(1)时间复杂度的LFU缓存实现。#include unordered_map #include list 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) {} }; struct KeyEntry { int value, freq; listNode::iterator it; }; int cap; int minFreq; unordered_mapint, KeyEntry keyTable; // key - {value, freq, iterator} unordered_mapint, listNode freqTable; // freq - list of Nodes void increaseFreq(int key) { KeyEntry entry keyTable[key]; int oldFreq entry.freq; auto oldIt entry.it; // 从旧链表删除 freqTable[oldFreq].erase(oldIt); // 如果旧链表变空清理并更新minFreq if (freqTable[oldFreq].empty()) { freqTable.erase(oldFreq); if (oldFreq minFreq) { minFreq; } } // 频率增加 int newFreq oldFreq 1; // 插入新链表头部 freqTable[newFreq].push_front(Node(key, entry.value, newFreq)); auto newIt freqTable[newFreq].begin(); // 更新键表记录 entry.freq newFreq; entry.it newIt; } public: LFUCache(int capacity) : cap(capacity), minFreq(0) {} int get(int key) { if (cap 0) return -1; auto it keyTable.find(key); if (it keyTable.end()) return -1; increaseFreq(key); return it-second.value; } void put(int key, int value) { if (cap 0) return; auto it keyTable.find(key); if (it ! keyTable.end()) { // 键存在更新值并提升频率 it-second.value value; increaseFreq(key); return; } // 键不存在插入新节点 if (keyTable.size() cap) { // 缓存满淘汰 auto minList freqTable[minFreq]; Node nodeToDel minList.back(); minList.pop_back(); keyTable.erase(nodeToDel.key); if (minList.empty()) { freqTable.erase(minFreq); // 注意这里minFreq可能失效但下面会置为1 } } // 插入新节点频率为1 int newFreq 1; freqTable[newFreq].push_front(Node(key, value, newFreq)); auto newIt freqTable[newFreq].begin(); keyTable[key] {value, newFreq, newIt}; minFreq 1; // 新插入节点最小频率必为1 } };我们来跑一个简单的测试模拟LeetCode的用例int main() { LFUCache lfu(2); lfu.put(1, 1); lfu.put(2, 2); cout lfu.get(1) endl; // 返回 1 key1 freq2 lfu.put(3, 3); // 容量已满移除key2 (freq1), 插入key3 cout lfu.get(2) endl; // 返回 -1 (未找到) cout lfu.get(3) endl; // 返回 3 key3 freq2 lfu.put(4, 4); // 容量已满此时key1 freq2, key3 freq2 // 两者频率相同移除最久未使用的即key1 cout lfu.get(1) endl; // 返回 -1 (未找到) cout lfu.get(3) endl; // 返回 3 key3 freq3 cout lfu.get(4) endl; // 返回 4 key4 freq2 return 0; }输出应该为1 -1 3 -1 3 45. 实现细节剖析与避坑指南在实现过程中有几个细节容易出错也是面试官喜欢追问的地方。5.1 迭代器失效问题这是使用STL容器特别是结合list和unordered_map时最需要小心的问题。在我们的设计里keyTable中存储了指向list的迭代器。当我们在increaseFreq中调用freqTable[oldFreq].erase(oldIt);后oldIt这个迭代器就立即失效了。之后我们绝不能再次使用它。这就是为什么我们需要在删除前就从KeyEntry里把需要的value信息取出来int value entry.value;因为删除后原来的Node对象就不复存在了。后续我们创建新的Node插入到新的链表中。5.2minFreq的更新时机minFreq的维护是保证淘汰O(1)的关键逻辑必须清晰何时增加只在increaseFreq函数中当某个键从当前minFreq对应的链表中被移走并且移走后该链表变空了此时才需要将minFreq。因为剩下的所有键的频率都至少是minFreq1。何时重置为1在put一个新键时。因为新键的频率永远是1所以此时整个缓存中的最小频率必然是1。淘汰时在淘汰一个键之后如果其所在的链表即freqTable[minFreq]变空我们可以选择删除这个空链表条目。但此时minFreq变量暂时处于一个“无效”状态因为该频率已无节点。不过紧接着如果是插入新键我们会把minFreq设为1如果是更新已有键minFreq可能会在后续的increaseFreq中被修正。一种更严谨的做法是在淘汰后如果链表空就freqTable.erase(minFreq);但先不更新minFreq等待下次get或put触发increaseFreq时由其中的判断逻辑来更新。我们的代码采用了在插入新键时直接重置的策略逻辑上是正确的。5.3 链表顺序与淘汰策略我们约定在每一个频率对应的双向链表中头部是最近访问的尾部是最久未访问的。这个“访问”指的是get或put更新该键。这样当需要从同一频率的多个键中淘汰一个时我们淘汰链表尾部的节点这就实现了LFU LRU的复合策略先淘汰频率最低的如果频率最低的有多个则淘汰其中最久未使用的。这是一种更公平、更实用的策略能防止一个历史上频繁访问但近期不再使用的“老热点”数据长期霸占缓存。5.4 容量为0的边界情况这是一个简单的边界条件但很重要。如果缓存容量为0那么get永远返回-1put操作什么都不做。在构造函数和两个主函数开头进行判断即可。6. 性能分析与应用场景思考6.1 时间复杂度get(int key): O(1)。哈希表查找O(1)increaseFreq中的链表删除、插入也都是O(1)。put(int key, int value): O(1)。哈希表查找、插入O(1)淘汰时链表尾部删除O(1)新节点链表头部插入O(1)。空间复杂度: O(capacity)。用于存储keyTable和freqTable。6.2 与LRU的对比优势LFU能更好地抓住“热点”数据。对于访问模式相对稳定、热点集中的场景如新闻热点排行、某款商品详情LFU的命中率通常高于LRU。因为它保护了频繁访问的数据即使它们有一段时间没被访问。劣势实现复杂需要维护频率信息数据结构比LRU复杂。对突发流量不友好如果一个新数据突然被大量访问突发热点LRU会立刻将其放到头部保护起来。而LFU中新数据初始频率低在缓存满时很容易被淘汰掉即使它正在被疯狂访问。这就是“缓存污染”问题。历史频率负担一个数据过去被访问很多次但未来不再需要。LFU会因为其历史高频率而长期保留它占用空间。6.3 实际应用与变种纯粹的LFU在实际大型系统中较少直接使用正是因为上述缺点。但它的思想被广泛应用并衍生出许多改进算法LFU-Aging给每个频率记录引入一个“年龄”或衰减机制定期降低所有数据的频率让旧的热点数据能逐渐被淘汰。Window-LFU只统计最近一段时间窗口内的访问频率结合了LRU和LFU的思想。TinyLFU一种非常著名的现代近似LFU算法用Count-Min Sketch等概率数据结构以极小的空间估算频率并结合一个准入过滤器通常是一个LRU队列来决定新数据是否值得放入缓存。Caffeine缓存库就使用了TinyLFU。对于我们的学习项目而言实现这个标准的、O(1)的LFU已经足够深入理解其精髓。下次可以尝试在此基础上实现一个简单的LFU-Aging或者对比测试一下LFU和LRU在不同访问模式下的命中率那会更有意思。
1. 项目概述与LFU核心思想最近在整理一个C缓存系统的学习项目前面几篇聊了缓存的基本概念和LRU的实现这次咱们来啃一块硬骨头——LFULeast Frequently Used最不经常使用淘汰算法的代码实现。如果你做过LeetCode上那道著名的 460. LFU 缓存 就知道这玩意儿比LRU要复杂不少但它的思想在实际系统中非常有用比如数据库的查询缓存、操作系统的页面置换甚至是一些内容分发网络CDN的边缘节点都会用到LFU或其变种来提升热点数据的命中率。LFU的核心逻辑很简单当缓存空间不足时淘汰掉那个被访问频率最低的数据。听起来比LRU的“淘汰最久未使用”更合理对吧毕竟一个被频繁访问的“热数据”理应比一个偶尔被访问一次的“冷数据”更有资格留在缓存里。但实现起来麻烦就出在这个“频率”上。它不是一个静态值而是一个动态变化的计数器。每次访问一个键它的频率就要加一。当需要淘汰时我们得从所有最低频率的键中再按照LRU或者FIFO的规则挑一个出来扔掉通常选择最久未访问的以解决“历史频率高但近期冷”的问题。这就意味着我们需要一种数据结构能同时高效地支持以下操作根据键key快速获取值value和其当前访问频率。根据频率freq快速找到所有处于该频率的键并且能从中移除一个通常是最早加入的。当某个键被访问频率增加时能将它从一个频率链表移动到更高一级的频率链表中。这比LRU只需要维护一个按访问时间排序的双向链表要复杂得多。网上很多简单的LFU实现在get和put操作时时间复杂度是O(N)的这在数据量大的时候根本不可用。我们这次的目标是实现一个get和put操作时间复杂度都在O(1)的LFU缓存。这需要精心设计数据结构的组合。2. 数据结构设计O(1)复杂度的关键要实现O(1)的操作我们必须摒弃遍历。核心思路是使用三个哈希表unordered_map和一组双向链表list进行组合。下面我们来拆解每个部分的作用。2.1 核心数据结构拆解key_table(键到节点的映射)类型unordered_mapint, Node键用户传入的键key。值一个Node结构体里面至少包含key,value,freq当前访问频率。作用这是最基础的映射。通过key我们可以在O(1)时间内找到对应的值value和其当前的频率freq。没有它get操作就无法快速完成。freq_table(频率到链表的映射)类型unordered_mapint, listNode键访问频率freq。值一个双向链表std::list里面存放所有处于该频率的Node。这个链表的顺序就是访问时间顺序链表头部是最新访问的尾部是最久未访问的。作用这是实现LFU淘汰的关键。它把相同频率的节点组织在一起。当我们需要淘汰时直接找到min_freq对应的链表移除其尾部的节点最久未访问就是O(1)操作。当某个节点频率增加时我们也需要把它从旧频率链表移动到新频率链表。min_freq(当前最小频率)类型int作用一个整型变量记录当前缓存中所有键的最低访问频率。淘汰操作依赖它。维护这个变量是保证O(1)淘汰的关键否则我们可能需要遍历freq_table来寻找最小频率。capacity(缓存容量)类型size_t作用缓存的最大容量在构造函数中传入。2.2 Node结构体与迭代器存储这里有一个非常重要的细节。当我们把一个Node放入std::list后如果后续要移动或删除它我们需要知道它在链表中的确切位置迭代器。但list的迭代器在元素被插入后才会确定并且如果我们将Node对象直接存入list再通过key_table找到这个Node我们无法直接获取到它在freq_table对应链表里的迭代器。因此常见的优化做法是key_table不直接存储Node对象而是存储一个包含value,freq以及迭代器的结构。这个迭代器指向该节点在freq_table[freq]这个链表中的位置。我们定义两个核心结构// 链表节点存储键值对和频率 struct Node { int key; int value; int freq; // 访问频率 // 构造函数方便初始化 Node(int k, int v, int f) : key(k), value(v), freq(f) {} }; // 在键表中存储的条目包含值和指向频率链表中位置的迭代器 struct KeyEntry { int value; int freq; std::listNode::iterator it; // 指向对应频率链表中的节点 };这样key_table的类型就变成了unordered_mapint, KeyEntry。通过key找到KeyEntry后我们立刻能拿到value、freq以及它在链表中的位置it。这个设计是连接key_table和freq_table的桥梁是实现O(1)移动和删除的核心。3. 核心操作流程与代码实现有了上面的设计图我们来看get和put这两个核心方法如何实现。我们先给出LFUCache类的整体框架。#include unordered_map #include list #include iostream class LFUCache { private: int capacity; // 缓存容量 int minFreq; // 当前最小频率 std::unordered_mapint, KeyEntry keyTable; // 键到条目的映射 std::unordered_mapint, std::listNode freqTable; // 频率到节点链表的映射 // 辅助函数增加某个键的频率 void increaseFreq(int key) { // 具体实现见下文 } public: LFUCache(int capacity) : capacity(capacity), minFreq(0) { // 构造函数 } int get(int key) { // 具体实现见下文 } void put(int key, int value) { // 具体实现见下文 } };3.1get操作查询并更新频率get操作的逻辑是如果key不存在于keyTable中直接返回-1。如果存在 a. 通过keyTable[key]找到对应的KeyEntry拿到value和freq。 b.调用increaseFreq(key)函数更新该键的频率。这是LFU的核心。 c. 返回value。int get(int key) { if (capacity 0) return -1; // 边界情况处理 auto it keyTable.find(key); if (it keyTable.end()) { return -1; // 键不存在 } // 找到条目 KeyEntry entry it-second; int value entry.value; // 提升该键的频率 increaseFreq(key); return value; }3.2put操作插入或更新put操作的逻辑更复杂一些需要处理插入新键和更新旧键两种情况以及缓存满时的淘汰。如果key已存在更新其value并调用increaseFreq(key)提升其频率。这相当于一次访问。如果key不存在 a.如果缓存已满keyTable.size() capacity则需要进行淘汰。 i. 找到minFreq对应的链表freqTable[minFreq]。 ii. 该链表的尾部节点就是最不经常使用且最久未访问的节点将其移除。 iii. 同时从keyTable中也删除这个键。 iv.注意移除节点后如果freqTable[minFreq]链表变空理论上可以删除这个空链表并且minFreq需要更新。但在本次插入后新键的频率为1minFreq必然会被设置为1。所以我们可以选择不立即更新minFreq而是在increaseFreq或下次淘汰时处理。一种更清晰的写法是在淘汰后如果链表为空就删除freqTable[minFreq]这个键但minFreq可以暂时不变因为紧接着要插入频率为1的新节点。 b.创建新节点频率freq初始化为1。 c. 将新节点插入到freqTable[1]链表的头部表示最新访问。 d. 在keyTable中记录这个新键其KeyEntry包含value、freq1以及上一步插入节点后返回的迭代器。 e.将minFreq重置为1。因为新加入的键频率最低就是1。void put(int key, int value) { if (capacity 0) return; // 边界情况处理 auto it keyTable.find(key); if (it ! keyTable.end()) { // 键已存在更新值并提升频率 KeyEntry entry it-second; entry.value value; // 更新值 increaseFreq(key); // 提升频率 return; } // 键不存在需要插入 // 检查容量是否已满 if (keyTable.size() capacity) { // 缓存已满需要淘汰 // 找到最小频率对应的链表 auto minFreqList freqTable[minFreq]; // 链表尾部的节点是最久未访问的 Node nodeToRemove minFreqList.back(); minFreqList.pop_back(); // 从链表中移除 keyTable.erase(nodeToRemove.key); // 从键表中移除 // 如果移除后链表变空可以清理这个频率桶可选 if (minFreqList.empty()) { freqTable.erase(minFreq); // 注意此时minFreq可能失效但接下来我们会插入freq1的节点所以直接设为1即可 } } // 插入新节点频率为1 int newFreq 1; // 将新节点插入频率1的链表头部 freqTable[newFreq].push_front(Node(key, value, newFreq)); // 获取刚插入节点的迭代器 auto newIt freqTable[newFreq].begin(); // 在键表中记录 keyTable[key] {value, newFreq, newIt}; // 新插入节点频率为1更新最小频率 minFreq 1; }3.3increaseFreq辅助函数频率提升的核心这是整个LFU实现中最精妙的部分它负责将一个键从一个频率链表移动到更高一级的频率链表。步骤通过keyTable[key]找到对应的KeyEntry获取当前的freq和链表迭代器it。从freqTable[freq]链表中通过迭代器it删除该节点。重要检查如果删除节点后freqTable[freq]链表变空了并且当前的freq恰好等于minFreq那么说明这个频率层级已经没有节点了最小频率minFreq需要增加minFreq。因为接下来这个节点的频率会变成freq1而freq这个频率已经不存在任何节点了。将节点的频率freq加一。将更新后的节点插入到freqTable[freq1]链表的头部。更新keyTable[key]中的freq和迭代器it。void increaseFreq(int key) { KeyEntry entry keyTable[key]; int oldFreq entry.freq; auto oldIt entry.it; // 1. 从旧频率链表中移除节点 freqTable[oldFreq].erase(oldIt); // 2. 检查旧频率链表是否变空并且是否是最小频率 if (freqTable[oldFreq].empty()) { freqTable.erase(oldFreq); // 清理空链表 if (oldFreq minFreq) { minFreq; // 最小频率需要提升 } } // 3. 提升频率 int newFreq oldFreq 1; // 4. 将节点插入新频率链表的头部 // 注意我们需要更新节点的freq但Node是存储在list里的我们需要修改它 // 更优的做法是在list中删除旧节点插入一个全新的Node。 // 但为了清晰我们修改原Node的freq然后重新插入。 // 实际上在erase后旧的Node对象已经被销毁。我们需要基于key和value新建一个。 // 因此我们需要从entry中取出value。 int value entry.value; freqTable[newFreq].push_front(Node(key, value, newFreq)); auto newIt freqTable[newFreq].begin(); // 5. 更新键表中的记录 entry.freq newFreq; entry.it newIt; }4. 完整代码与测试案例将上述所有部分组合起来就得到了一个完整的、O(1)时间复杂度的LFU缓存实现。#include unordered_map #include list 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) {} }; struct KeyEntry { int value, freq; listNode::iterator it; }; int cap; int minFreq; unordered_mapint, KeyEntry keyTable; // key - {value, freq, iterator} unordered_mapint, listNode freqTable; // freq - list of Nodes void increaseFreq(int key) { KeyEntry entry keyTable[key]; int oldFreq entry.freq; auto oldIt entry.it; // 从旧链表删除 freqTable[oldFreq].erase(oldIt); // 如果旧链表变空清理并更新minFreq if (freqTable[oldFreq].empty()) { freqTable.erase(oldFreq); if (oldFreq minFreq) { minFreq; } } // 频率增加 int newFreq oldFreq 1; // 插入新链表头部 freqTable[newFreq].push_front(Node(key, entry.value, newFreq)); auto newIt freqTable[newFreq].begin(); // 更新键表记录 entry.freq newFreq; entry.it newIt; } public: LFUCache(int capacity) : cap(capacity), minFreq(0) {} int get(int key) { if (cap 0) return -1; auto it keyTable.find(key); if (it keyTable.end()) return -1; increaseFreq(key); return it-second.value; } void put(int key, int value) { if (cap 0) return; auto it keyTable.find(key); if (it ! keyTable.end()) { // 键存在更新值并提升频率 it-second.value value; increaseFreq(key); return; } // 键不存在插入新节点 if (keyTable.size() cap) { // 缓存满淘汰 auto minList freqTable[minFreq]; Node nodeToDel minList.back(); minList.pop_back(); keyTable.erase(nodeToDel.key); if (minList.empty()) { freqTable.erase(minFreq); // 注意这里minFreq可能失效但下面会置为1 } } // 插入新节点频率为1 int newFreq 1; freqTable[newFreq].push_front(Node(key, value, newFreq)); auto newIt freqTable[newFreq].begin(); keyTable[key] {value, newFreq, newIt}; minFreq 1; // 新插入节点最小频率必为1 } };我们来跑一个简单的测试模拟LeetCode的用例int main() { LFUCache lfu(2); lfu.put(1, 1); lfu.put(2, 2); cout lfu.get(1) endl; // 返回 1 key1 freq2 lfu.put(3, 3); // 容量已满移除key2 (freq1), 插入key3 cout lfu.get(2) endl; // 返回 -1 (未找到) cout lfu.get(3) endl; // 返回 3 key3 freq2 lfu.put(4, 4); // 容量已满此时key1 freq2, key3 freq2 // 两者频率相同移除最久未使用的即key1 cout lfu.get(1) endl; // 返回 -1 (未找到) cout lfu.get(3) endl; // 返回 3 key3 freq3 cout lfu.get(4) endl; // 返回 4 key4 freq2 return 0; }输出应该为1 -1 3 -1 3 45. 实现细节剖析与避坑指南在实现过程中有几个细节容易出错也是面试官喜欢追问的地方。5.1 迭代器失效问题这是使用STL容器特别是结合list和unordered_map时最需要小心的问题。在我们的设计里keyTable中存储了指向list的迭代器。当我们在increaseFreq中调用freqTable[oldFreq].erase(oldIt);后oldIt这个迭代器就立即失效了。之后我们绝不能再次使用它。这就是为什么我们需要在删除前就从KeyEntry里把需要的value信息取出来int value entry.value;因为删除后原来的Node对象就不复存在了。后续我们创建新的Node插入到新的链表中。5.2minFreq的更新时机minFreq的维护是保证淘汰O(1)的关键逻辑必须清晰何时增加只在increaseFreq函数中当某个键从当前minFreq对应的链表中被移走并且移走后该链表变空了此时才需要将minFreq。因为剩下的所有键的频率都至少是minFreq1。何时重置为1在put一个新键时。因为新键的频率永远是1所以此时整个缓存中的最小频率必然是1。淘汰时在淘汰一个键之后如果其所在的链表即freqTable[minFreq]变空我们可以选择删除这个空链表条目。但此时minFreq变量暂时处于一个“无效”状态因为该频率已无节点。不过紧接着如果是插入新键我们会把minFreq设为1如果是更新已有键minFreq可能会在后续的increaseFreq中被修正。一种更严谨的做法是在淘汰后如果链表空就freqTable.erase(minFreq);但先不更新minFreq等待下次get或put触发increaseFreq时由其中的判断逻辑来更新。我们的代码采用了在插入新键时直接重置的策略逻辑上是正确的。5.3 链表顺序与淘汰策略我们约定在每一个频率对应的双向链表中头部是最近访问的尾部是最久未访问的。这个“访问”指的是get或put更新该键。这样当需要从同一频率的多个键中淘汰一个时我们淘汰链表尾部的节点这就实现了LFU LRU的复合策略先淘汰频率最低的如果频率最低的有多个则淘汰其中最久未使用的。这是一种更公平、更实用的策略能防止一个历史上频繁访问但近期不再使用的“老热点”数据长期霸占缓存。5.4 容量为0的边界情况这是一个简单的边界条件但很重要。如果缓存容量为0那么get永远返回-1put操作什么都不做。在构造函数和两个主函数开头进行判断即可。6. 性能分析与应用场景思考6.1 时间复杂度get(int key): O(1)。哈希表查找O(1)increaseFreq中的链表删除、插入也都是O(1)。put(int key, int value): O(1)。哈希表查找、插入O(1)淘汰时链表尾部删除O(1)新节点链表头部插入O(1)。空间复杂度: O(capacity)。用于存储keyTable和freqTable。6.2 与LRU的对比优势LFU能更好地抓住“热点”数据。对于访问模式相对稳定、热点集中的场景如新闻热点排行、某款商品详情LFU的命中率通常高于LRU。因为它保护了频繁访问的数据即使它们有一段时间没被访问。劣势实现复杂需要维护频率信息数据结构比LRU复杂。对突发流量不友好如果一个新数据突然被大量访问突发热点LRU会立刻将其放到头部保护起来。而LFU中新数据初始频率低在缓存满时很容易被淘汰掉即使它正在被疯狂访问。这就是“缓存污染”问题。历史频率负担一个数据过去被访问很多次但未来不再需要。LFU会因为其历史高频率而长期保留它占用空间。6.3 实际应用与变种纯粹的LFU在实际大型系统中较少直接使用正是因为上述缺点。但它的思想被广泛应用并衍生出许多改进算法LFU-Aging给每个频率记录引入一个“年龄”或衰减机制定期降低所有数据的频率让旧的热点数据能逐渐被淘汰。Window-LFU只统计最近一段时间窗口内的访问频率结合了LRU和LFU的思想。TinyLFU一种非常著名的现代近似LFU算法用Count-Min Sketch等概率数据结构以极小的空间估算频率并结合一个准入过滤器通常是一个LRU队列来决定新数据是否值得放入缓存。Caffeine缓存库就使用了TinyLFU。对于我们的学习项目而言实现这个标准的、O(1)的LFU已经足够深入理解其精髓。下次可以尝试在此基础上实现一个简单的LFU-Aging或者对比测试一下LFU和LRU在不同访问模式下的命中率那会更有意思。
