前言LFUleast frequently used最不经常使用是一种缓存淘汰策略缓存满时优先淘汰访问次数最少的元素次数相同时淘汰最久未使用的那个。它和 LRUleast recently used的区别在于LRU 只看最近一次访问时间LFU 还看累计访问频率。常见误解是LFU 用一个计数器排序就行。每次访问都对所有元素排序复杂度是 O(n log n)缓存大了根本不可行。正确的实现要维护频率 → 该频率下的元素链表这样的桶结构让 get 和 put 都达到平均 O(1)。另一个难点是最少频率的维护。删除元素后最小频率可能变化新插入的元素频率为 1最小频率又要重置。这些边界处理不好就会出现淘汰了不该淘汰的元素、或者访问已删除元素的问题。本文用 C17 模板实现一个泛型的 LFU 缓存键和值都可以是任意可哈希、可拷贝的类型并用std::list保证迭代器稳定。一、数据结构设计核心是三层结构结构类型作用索引unordered_mapKey, Entry按 key 找到元素位置与频率频率桶unordered_mapsize_t, listpairKey, Value每个频率一条链表最小频率size_t m_minFreq淘汰时直接定位到最低频桶每个Entry保存两个东西当前频率以及该元素在对应频率链表中的迭代器。std::list的插入、删除不会让其他元素的迭代器失效这让从旧频率桶搬到新频率桶成为 O(1) 操作。同一频率内链表头部放最近访问的元素尾部放最久未访问的。淘汰时取尾部就同时满足了频率最低和同频率最久未用。// 适用于 C17#include cstddef#include functional#include list#include stdexcept#include unordered_map#include utilitytemplate typename Key, typename Value,typename Hash std::hashKey,typename Equal std::equal_toKeyclass LFUCache {public:explicit LFUCache(std::size_t capacity): m_capacity(capacity){}bool get(const Key key, Value out){const auto it m_index.find(key);if (it m_index.end()) {return false;}out it-second.pos-second; // 先拷贝值再搬桶touch(it-second, it-first);return true;}void put(const Key key, const Value value){if (m_capacity 0) {return;}const auto it m_index.find(key);if (it ! m_index.end()) {it-second.pos-second value;touch(it-second, it-first);return;}if (m_index.size() m_capacity) {evict();}Bucket bucket m_freq[1];bucket.push_front(std::make_pair(key, value));m_index.emplace(key, Entry{1, bucket.begin()});m_minFreq 1;}std::size_t size() const { return m_index.size(); }private:using Bucket std::liststd::pairKey, Value;struct Entry {std::size_t freq;typename Bucket::iterator pos;};void touch(Entry entry, const Key key){const std::size_t oldFreq entry.freq;const Value value entry.pos-second; // 搬桶前保存值auto oldIt m_freq.find(oldFreq);oldIt-second.erase(entry.pos);if (oldIt-second.empty()) {m_freq.erase(oldIt);if (m_minFreq oldFreq) {m_minFreq; // 最低频桶空了整体上移}}const std::size_t newFreq oldFreq 1;Bucket bucket m_freq[newFreq];bucket.push_front(std::make_pair(key, value));entry.freq newFreq;entry.pos bucket.begin();}void evict(){auto it m_freq.find(m_minFreq);if (it m_freq.end() || it-second.empty()) {return;}Bucket bucket it-second;const Key victimKey bucket.back().first;m_index.erase(victimKey);bucket.pop_back();if (bucket.empty()) {m_freq.erase(it);}}std::size_t m_capacity;std::size_t m_minFreq 0;std::unordered_mapKey, Entry, Hash, Equal m_index;std::unordered_mapstd::size_t, Bucket m_freq;};二、get 与 put 的流程get分三步查找索引把值拷贝到输出参数把该元素从旧频率桶搬到freq 1的桶头。值必须在搬桶前拷贝因为搬桶会先删除旧的链表结点。put分两种情况key 已存在更新值然后同样提升频率key 不存在缓存满则先淘汰再以频率 1 插入新桶并把m_minFreq重置为 1。m_minFreq的重置很关键。即使之前的最小频率是 5新元素的频率是 1之后淘汰必须从 1 开始找。三、touch 的边界touch里的if (m_minFreq oldFreq) m_minFreq;只在该频率桶变空时执行。为什么可以直接加一因为刚被访问的元素从oldFreq搬到了oldFreq 1如果oldFreq是最小频率且桶已空那么新的最小频率至少是oldFreq 1而这个元素正好在oldFreq 1桶里所以最小值就是它。如果oldFreq不是最小频率桶空了也不影响m_minFreq因为还有更低的频率存在。evict取bucket.back()即同频率里最久未访问的元素。删除索引项、弹出链表尾如果桶空了就把整个频率项从 map 里移除。四、使用示例// 适用于 C17#include iostream#include stringint main(){LFUCacheint, std::string cache(2);cache.put(1, one);cache.put(2, two);std::string out;if (cache.get(1, out)) {std::cout get 1: out \n; // one}cache.put(3, three); // 淘汰 2std::cout std::boolalpha;std::cout cache.get(2, out) \n; // falsestd::cout cache.get(1, out) out \n; // true onestd::cout cache.get(3, out) out \n; // true threereturn 0;}按语义推演插入 1、2 后两者频率都是 1访问 1 后它的频率变为 2最小频率仍是 1桶里只剩 2插入 3 时缓存已满淘汰频率 1 的 2。之后查询 2 失败查询 1 和 3 都能命中。五、泛型约束与复杂度模板参数Key需要满足可用std::hashKey计算哈希或通过Hash参数传入自定义哈希可用std::equal_toKey比较相等或通过Equal传入。Value需要可拷贝因为get要把值写到输出参数touch搬桶时也要复制一次。如果值很大可以考虑让get返回指针或std::reference_wrapper但要小心元素被淘汰后指针悬垂。操作平均复杂度说明getO(1)哈希查找 链表搬移put已存在O(1)更新 搬移put新键O(1)可能触发一次淘汰空间O(capacity)索引与频率桶各一份哈希表的 O(1) 是平均情况最坏情况取决于哈希质量和冲突处理标准不作常数保证。六、与 LRU 的比较维度LRULFU淘汰依据最久未访问访问次数最少额外结构一条双向链表频率桶 最小频率对新元素立即变为最新从频率 1 开始可能很快被淘汰适用场景访问模式随时间变化热点长期稳定LFU 的问题是历史包袱一个曾经很热、后来不再使用的元素频率很高很难被淘汰。实际系统里常用带衰减的 LFU或者 LRU 与 LFU 的混合策略。常见坑点❌ 每次访问都对所有元素按频率排序。✅ 用频率桶get/put 平均 O(1)。❌ 搬桶时先删除旧结点再读它的值。✅ 先把值拷贝出来再erase。❌ 桶空了不更新m_minFreq淘汰时找不到桶。✅ 旧桶为空且等于最小频率时m_minFreq。❌ 插入新元素后忘记把m_minFreq重置为 1。✅ 新元素频率总是 1最小频率必然是 1。❌ 用std::vector存同频率元素删除导致迭代器失效。✅ 用std::list删除只影响被删结点。❌capacity为 0 时仍执行插入。✅ 开头判断直接返回。❌ 淘汰时只从频率桶删除忘记同步删除索引。✅ 两处都要删否则索引指向已释放结点。❌ 认为哈希表查找一定是常数时间。✅ 那是平均复杂度冲突严重时会退化。总结组件作用关键操作m_indexkey → 频率与链表位置查找、删除m_freq频率 → 元素链表搬入、搬出、取尾部m_minFreq定位淘汰桶桶空时上移新插入时重置Entry::pos指向链表结点使搬桶为 O(1)LFU 的代码量比 LRU 大但结构清晰索引负责找到频率桶负责排序最小频率负责淘汰。把搬桶时的值拷贝、空桶时的最小频率更新、淘汰时的两处删除这三件事做对O(1) 的 LFU 就成立了。
前言LFUleast frequently used最不经常使用是一种缓存淘汰策略缓存满时优先淘汰访问次数最少的元素次数相同时淘汰最久未使用的那个。它和 LRUleast recently used的区别在于LRU 只看最近一次访问时间LFU 还看累计访问频率。常见误解是LFU 用一个计数器排序就行。每次访问都对所有元素排序复杂度是 O(n log n)缓存大了根本不可行。正确的实现要维护频率 → 该频率下的元素链表这样的桶结构让 get 和 put 都达到平均 O(1)。另一个难点是最少频率的维护。删除元素后最小频率可能变化新插入的元素频率为 1最小频率又要重置。这些边界处理不好就会出现淘汰了不该淘汰的元素、或者访问已删除元素的问题。本文用 C17 模板实现一个泛型的 LFU 缓存键和值都可以是任意可哈希、可拷贝的类型并用std::list保证迭代器稳定。一、数据结构设计核心是三层结构结构类型作用索引unordered_mapKey, Entry按 key 找到元素位置与频率频率桶unordered_mapsize_t, listpairKey, Value每个频率一条链表最小频率size_t m_minFreq淘汰时直接定位到最低频桶每个Entry保存两个东西当前频率以及该元素在对应频率链表中的迭代器。std::list的插入、删除不会让其他元素的迭代器失效这让从旧频率桶搬到新频率桶成为 O(1) 操作。同一频率内链表头部放最近访问的元素尾部放最久未访问的。淘汰时取尾部就同时满足了频率最低和同频率最久未用。// 适用于 C17#include cstddef#include functional#include list#include stdexcept#include unordered_map#include utilitytemplate typename Key, typename Value,typename Hash std::hashKey,typename Equal std::equal_toKeyclass LFUCache {public:explicit LFUCache(std::size_t capacity): m_capacity(capacity){}bool get(const Key key, Value out){const auto it m_index.find(key);if (it m_index.end()) {return false;}out it-second.pos-second; // 先拷贝值再搬桶touch(it-second, it-first);return true;}void put(const Key key, const Value value){if (m_capacity 0) {return;}const auto it m_index.find(key);if (it ! m_index.end()) {it-second.pos-second value;touch(it-second, it-first);return;}if (m_index.size() m_capacity) {evict();}Bucket bucket m_freq[1];bucket.push_front(std::make_pair(key, value));m_index.emplace(key, Entry{1, bucket.begin()});m_minFreq 1;}std::size_t size() const { return m_index.size(); }private:using Bucket std::liststd::pairKey, Value;struct Entry {std::size_t freq;typename Bucket::iterator pos;};void touch(Entry entry, const Key key){const std::size_t oldFreq entry.freq;const Value value entry.pos-second; // 搬桶前保存值auto oldIt m_freq.find(oldFreq);oldIt-second.erase(entry.pos);if (oldIt-second.empty()) {m_freq.erase(oldIt);if (m_minFreq oldFreq) {m_minFreq; // 最低频桶空了整体上移}}const std::size_t newFreq oldFreq 1;Bucket bucket m_freq[newFreq];bucket.push_front(std::make_pair(key, value));entry.freq newFreq;entry.pos bucket.begin();}void evict(){auto it m_freq.find(m_minFreq);if (it m_freq.end() || it-second.empty()) {return;}Bucket bucket it-second;const Key victimKey bucket.back().first;m_index.erase(victimKey);bucket.pop_back();if (bucket.empty()) {m_freq.erase(it);}}std::size_t m_capacity;std::size_t m_minFreq 0;std::unordered_mapKey, Entry, Hash, Equal m_index;std::unordered_mapstd::size_t, Bucket m_freq;};二、get 与 put 的流程get分三步查找索引把值拷贝到输出参数把该元素从旧频率桶搬到freq 1的桶头。值必须在搬桶前拷贝因为搬桶会先删除旧的链表结点。put分两种情况key 已存在更新值然后同样提升频率key 不存在缓存满则先淘汰再以频率 1 插入新桶并把m_minFreq重置为 1。m_minFreq的重置很关键。即使之前的最小频率是 5新元素的频率是 1之后淘汰必须从 1 开始找。三、touch 的边界touch里的if (m_minFreq oldFreq) m_minFreq;只在该频率桶变空时执行。为什么可以直接加一因为刚被访问的元素从oldFreq搬到了oldFreq 1如果oldFreq是最小频率且桶已空那么新的最小频率至少是oldFreq 1而这个元素正好在oldFreq 1桶里所以最小值就是它。如果oldFreq不是最小频率桶空了也不影响m_minFreq因为还有更低的频率存在。evict取bucket.back()即同频率里最久未访问的元素。删除索引项、弹出链表尾如果桶空了就把整个频率项从 map 里移除。四、使用示例// 适用于 C17#include iostream#include stringint main(){LFUCacheint, std::string cache(2);cache.put(1, one);cache.put(2, two);std::string out;if (cache.get(1, out)) {std::cout get 1: out \n; // one}cache.put(3, three); // 淘汰 2std::cout std::boolalpha;std::cout cache.get(2, out) \n; // falsestd::cout cache.get(1, out) out \n; // true onestd::cout cache.get(3, out) out \n; // true threereturn 0;}按语义推演插入 1、2 后两者频率都是 1访问 1 后它的频率变为 2最小频率仍是 1桶里只剩 2插入 3 时缓存已满淘汰频率 1 的 2。之后查询 2 失败查询 1 和 3 都能命中。五、泛型约束与复杂度模板参数Key需要满足可用std::hashKey计算哈希或通过Hash参数传入自定义哈希可用std::equal_toKey比较相等或通过Equal传入。Value需要可拷贝因为get要把值写到输出参数touch搬桶时也要复制一次。如果值很大可以考虑让get返回指针或std::reference_wrapper但要小心元素被淘汰后指针悬垂。操作平均复杂度说明getO(1)哈希查找 链表搬移put已存在O(1)更新 搬移put新键O(1)可能触发一次淘汰空间O(capacity)索引与频率桶各一份哈希表的 O(1) 是平均情况最坏情况取决于哈希质量和冲突处理标准不作常数保证。六、与 LRU 的比较维度LRULFU淘汰依据最久未访问访问次数最少额外结构一条双向链表频率桶 最小频率对新元素立即变为最新从频率 1 开始可能很快被淘汰适用场景访问模式随时间变化热点长期稳定LFU 的问题是历史包袱一个曾经很热、后来不再使用的元素频率很高很难被淘汰。实际系统里常用带衰减的 LFU或者 LRU 与 LFU 的混合策略。常见坑点❌ 每次访问都对所有元素按频率排序。✅ 用频率桶get/put 平均 O(1)。❌ 搬桶时先删除旧结点再读它的值。✅ 先把值拷贝出来再erase。❌ 桶空了不更新m_minFreq淘汰时找不到桶。✅ 旧桶为空且等于最小频率时m_minFreq。❌ 插入新元素后忘记把m_minFreq重置为 1。✅ 新元素频率总是 1最小频率必然是 1。❌ 用std::vector存同频率元素删除导致迭代器失效。✅ 用std::list删除只影响被删结点。❌capacity为 0 时仍执行插入。✅ 开头判断直接返回。❌ 淘汰时只从频率桶删除忘记同步删除索引。✅ 两处都要删否则索引指向已释放结点。❌ 认为哈希表查找一定是常数时间。✅ 那是平均复杂度冲突严重时会退化。总结组件作用关键操作m_indexkey → 频率与链表位置查找、删除m_freq频率 → 元素链表搬入、搬出、取尾部m_minFreq定位淘汰桶桶空时上移新插入时重置Entry::pos指向链表结点使搬桶为 O(1)LFU 的代码量比 LRU 大但结构清晰索引负责找到频率桶负责排序最小频率负责淘汰。把搬桶时的值拷贝、空桶时的最小频率更新、淘汰时的两处删除这三件事做对O(1) 的 LFU 就成立了。
