【SSP之路-5-重要节点】LFU

LFU（Least Frequently Used，最近最少使用）缓存是一种高级缓存淘汰算法。与 LRU（最近最少使用）不同，LFU 关注的是数据被访问的频率。

如果一个数据在过去被访问的次数越多，那么它在未来被访问的可能性就越大。当缓存满时，LFU 会优先淘汰那些访问次数最少的数据。如果次数相同，则淘汰最久未被访问的数据。

1. 核心挑战：如何做到O(1)O(1)O(1)时间复杂度？

实现 LFU 的难点在于，我们需要在O(1)O(1)O(1)时间内完成：

1. 查询：通过 Key 获取 Value。
2. 更新：增加某个 Key 的访问计数，并将其移到新的频率区间。
3. 淘汰：找到频率最低且最旧的数据并删除。

传统的堆（Heap）结构虽然能找最小值，但更新操作需要O(log⁡n)O(\log n)O(logn)。为了达到O(1)O(1)O(1)，我们通常采用双重哈希表 + 双向链表的结构。

2. 数据结构设计

我们需要三个主要组件：

• Key 到 节点的映射 (key_table)：存储 Key 与其对应的值、频率等信息。
• 频率 到 节点链表的映射 (freq_table)：每一层频率（如访问了 1 次、2 次…）都对应一个双向链表，链表内按访问时间排序。
• 全局最小频率 (min_freq)：记录当前缓存中最小的访问频率，方便淘汰时定位。

3. C++ 实现解析

#include<unordered_map>#include<list>structNode{intkey,val,freq;Node(intk,intv,intf):key(k),val(v),freq(f){}};classLFUCache{intcapacity;intmin_freq;// key -> list迭代器 (方便 O(1) 删除)std::unordered_map<int,std::list<Node>::iterator>key_table;// freq -> 该频率下的 Node 链表std::unordered_map<int,std::list<Node>>freq_table;public:LFUCache(intcapacity):capacity(capacity),min_freq(0){}intget(intkey){if(capacity==0||key_table.find(key)==key_table.end())return-1;autoit=key_table[key];intval=it->val;intfreq=it->freq;// 1. 从旧频率链表中移除freq_table[freq].erase(it);if(freq_table[freq].empty()){freq_table.erase(freq);if(min_freq==freq)min_freq++;}// 2. 插入新频率链表 (freq + 1) 的头部freq_table[freq+1].push_front(Node(key,val,freq+1));key_table[key]=freq_table[freq+1].begin();returnval;}voidput(intkey,intvalue){if(capacity==0)return;if(get(key)!=-1){// 如果 key 已存在，get 内部已处理频率更新key_table[key]->val=value;// 更新值即可return;}// 3. 缓存已满，淘汰最小频率链表的末尾元素if(key_table.size()==capacity){autoit=freq_table[min_freq].back();key_table.erase(it.key);freq_table[min_freq].pop_back();if(freq_table[min_freq].empty())freq_table.erase(min_freq);}// 4. 插入新元素，频率设为 1min_freq=1;freq_table[1].push_front(Node(key,value,1));key_table[key]=freq_table[1].begin();}};

4. 算法流程拆解

当get(key)发生时：

1. 通过key_table找到该节点。
2. 提取值，并将该节点从freq_table[f]中删除。
3. 将该节点加入到freq_table[f+1]的头部。
4. 关键：如果旧频率f正好是min_freq且对应的链表空了，则min_freq需要自增。

当put(key, value)发生时：

1. 如果 Key 已存在，更新 Value 并触发一次“访问更新”（同get）。
2. 如果 Key 不存在：

• 缓存满了吗？满了就去freq_table[min_freq]的末尾（最旧的节点）删掉一个。
• 插入新节点，频率设为 1。
• 重置min_freq = 1。

5. LRU 与 LFU 的对比