前言

LFU（least frequently used，最不经常使用）是一种缓存淘汰策略：缓存满时，优先淘汰访问次数最少的元素；次数相同时，淘汰最久未使用的那个。它和 LRU（least recently used）的区别在于，LRU 只看"最近一次访问时间"，LFU 还看"累计访问频率"。

常见误解是"LFU 用一个计数器排序就行"。每次访问都对所有元素排序，复杂度是 O(n log n)，缓存大了根本不可行。正确的实现要维护"频率 → 该频率下的元素链表"这样的桶结构，让 get 和 put 都达到平均 O(1)。

另一个难点是"最少频率"的维护。删除元素后，最小频率可能变化；新插入的元素频率为 1，最小频率又要重置。这些边界处理不好，就会出现淘汰了不该淘汰的元素、或者访问已删除元素的问题。

本文用 C++17 模板实现一个泛型的 LFU 缓存，键和值都可以是任意可哈希、可拷贝的类型，并用std::list保证迭代器稳定。

一、数据结构设计

核心是三层结构：

每个Entry保存两个东西：当前频率，以及该元素在对应频率链表中的迭代器。std::list的插入、删除不会让其他元素的迭代器失效，这让"从旧频率桶搬到新频率桶"成为 O(1) 操作。

同一频率内，链表头部放最近访问的元素，尾部放最久未访问的。淘汰时取尾部，就同时满足了"频率最低"和"同频率最久未用"。

// 适用于 C++17
#include <cstddef>
#include <functional>
#include <list>
#include <stdexcept>
#include <unordered_map>
#include <utility>

template <typename Key, typename Value,
typename Hash = std::hash<Key>,
typename Equal = std::equal_to<Key>>
class 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::list<std::pair<Key, 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_map<Key, Entry, Hash, Equal> m_index;
std::unordered_map<std::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 里移除。

四、使用示例

// 适用于 C++17
#include <iostream>
#include <string>

int main()
{
LFUCache<int, 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"); // 淘汰 2

std::cout << std::boolalpha;
std::cout << cache.get(2, out) << "\n"; // false
std::cout << cache.get(1, out) << " " << out << "\n"; // true one
std::cout << cache.get(3, out) << " " << out << "\n"; // true three
return 0;
}

按语义推演：插入 1、2 后两者频率都是 1；访问 1 后它的频率变为 2，最小频率仍是 1，桶里只剩 2；插入 3 时缓存已满，淘汰频率 1 的 2。之后查询 2 失败，查询 1 和 3 都能命中。

五、泛型约束与复杂度

模板参数Key需要满足：

• 
  
• 可用std::hash<Key>计算哈希（或通过Hash参数传入自定义哈希）；
• 
  
• 可用std::equal_to<Key>比较相等（或通过Equal传入）。
• 
  

Value需要可拷贝，因为get要把值写到输出参数，touch搬桶时也要复制一次。如果值很大，可以考虑让get返回指针或std::reference_wrapper，但要小心元素被淘汰后指针悬垂。

哈希表的 O(1) 是平均情况，最坏情况取决于哈希质量和冲突处理，标准不作常数保证。

六、与 LRU 的比较

LFU 的问题是"历史包袱"：一个曾经很热、后来不再使用的元素，频率很高，很难被淘汰。实际系统里常用带衰减的 LFU，或者 LRU 与 LFU 的混合策略。

常见坑点

1. 
   
2. ❌ 每次访问都对所有元素按频率排序。
3. 
   

✅ 用频率桶，get/put 平均 O(1)。

1. 
   
2. ❌ 搬桶时先删除旧结点，再读它的值。
3. 
   

✅ 先把值拷贝出来，再erase。

1. 
   
2. ❌ 桶空了不更新m_minFreq，淘汰时找不到桶。
3. 
   

✅ 旧桶为空且等于最小频率时，++m_minFreq。

1. 
   
2. ❌ 插入新元素后忘记把m_minFreq重置为 1。
3. 
   

✅ 新元素频率总是 1，最小频率必然是 1。

1. 
   
2. ❌ 用std::vector存同频率元素，删除导致迭代器失效。
3. 
   

✅ 用std::list，删除只影响被删结点。

1. 
   
2. ❌capacity为 0 时仍执行插入。
3. 
   

✅ 开头判断，直接返回。

1. 
   
2. ❌ 淘汰时只从频率桶删除，忘记同步删除索引。
3. 
   

✅ 两处都要删，否则索引指向已释放结点。

1. 
   
2. ❌ 认为哈希表查找一定是常数时间。
3. 
   

✅ 那是平均复杂度；冲突严重时会退化。

总结

LFU 的代码量比 LRU 大，但结构清晰：索引负责"找到"，频率桶负责"排序"，最小频率负责"淘汰"。把搬桶时的值拷贝、空桶时的最小频率更新、淘汰时的两处删除这三件事做对，O(1) 的 LFU 就成立了。