LFU 缓存算法详解：双哈希与双向链表的 O(1) 实现

然后我们只要的就是维护两个哈希，以及容量和对应最小频率计数器即可：

std::unordered_map<K, Node<K, V>> _hash_map;      // 储存对应 key 值与对应的上述节点的 hash
std::unordered_map<int, std::list<K>> _access_map; // 储存对应的访问次数的存放 key 的那个 list
size_t _capacity;                                  // 缓存最大容量，根据它进行决定进行对应的 LFU 策略更新
int _min_access_count;                             // 储存最少的访问次数，方便进行删除

然而 LFU，最大的特色就在于它的访问频率更新策略，通过它来保证整个算法的优越性，下面我们解释下这个策略：

• 首先比如我们 put 或者 get 一个数据的时候，此时对应的访问频次就要增加（这里我们设置的是默认增加 1），此时就要调整对应的维护频率次数的那个 hash 了，及时进行对应 list 节点删除以及挂载即可。

需要注意的是：

• 操作过程要时刻维护着这个 min_access_count，这是关键。
• 其次就是这两个 hash 是互相关联的，也就是移除了对应 list 的节点，此时对应第一个 hash 的映射就要及时删除。
• 其次就是如果对应 list 删除对应节点后为空了，此时就要移除第二个 hash 对应的槽位。

// 对于 put 或者 get 后进行对应的数据的访问次数等操作进行统一处理（比如进行 LFU 策略删除等）
void accessCountAdd(const K& key) {
    // 获取对应节点
    Node<K, V>& node = _hash_map[key];
    int old_access_cnt = node.access_count;
    std::list<K>& cur_list = _access_map[old_access_cnt];
    cur_list.erase(node.it); // 删除后进行判断，如果访问的 hash 对应 list 空了，直接删除这个 hash 槽即可
    if (cur_list.empty()) {
        _access_map.erase(old_access_cnt);
        // 如果恰好是最少的，更新下最小的即可
        if (old_access_cnt == _min_access_count)
            // 如果删除完对应的之前的 key 所在的 list 后，为空了而且此时对应的 min_cnt 也是当前 key 的 cnt，此时说明 min_cnt 必须要 +1 完成更新了
            _min_access_count++;
    }
    // 此时除了有可能它俩相同，就是 cur_list 不为空的情况，或者不等：
    // 进行更新访问次数
    int new_access_cnt = old_access_cnt + 1;
    node.access_count = new_access_cnt;
    // 再次更新下，这里保险起见
    _min_access_count = std::min(_min_access_count, new_access_cnt);
    // 把对应的 key 加入到新的 list 中
    auto& new_list = _access_map[new_access_cnt];
    // 这里需要引用，因为后续会进行修改
    new_list.push_front(node.key);
    // 务必要更新对应迭代器
    node.it = new_list.begin();
}

然后我们主要提供对应的 get 与 put 接口：

1. get：

这里其实就是通过快查 hash，完成对应的获取，如果不存在返回默认构造（这里可能有点不合适，因为是模版暂时这样），如果存在就返回对应 node 的 value，然后进行频率更新策略。

如下：

V get(const K& key) {
    // 先判断是否存在这个 key
    if (_hash_map.find(key) == _hash_map.end())
        return V(); // 有点瑕疵，一般都是 int int，直接返回 -1
    // 存在这个 key，进行访问次数 +1
    accessCountAdd(key);
    return _hash_map[key].value;
}

2. put：

首先先去第一个 hash 找对应 key 的节点是否存在，分为两种情况：

• 存在，此时直接更新对应 value，再执行对应的频率策略即可。
• 不存在，此时我们就要新插入了，但是插入之前，先判断是否容量已经满了，如果满了就要根据_min_access_count 进行删除了，此时才能继续插入。

如下：

bool put(const K& key, const V& val) {
    // 1. 判断容量是否为 0
    if (_capacity <= 0) return false;
    // 进行查找
    auto it = _hash_map.find(key);
    if (it != _hash_map.end()) {
        // 存在这个 key，直接更新对应的值并根据对应 LFU 策略进行对应处理
        _hash_map[key].value = val;
        // 2. 更新访问次数
        accessCountAdd(key);
        return true;
    }
    // 不存在，检查容量（根据 LFU 策略更新),插入新的
    // it==_hash_map.end()
    if (_capacity <= _hash_map.size()) {
        // 容量已满，执行 LFU 策略
        // 找到访问次数最少的 list，也就是是最不经常使用的那一批数据
        auto& min_list = _access_map[_min_access_count];
        // 根据 LRU 策略删除最近最少使用的 key
        auto evict_key = min_list.back();
        min_list.pop_back();
        // 判断是否这个 list 为空了，进行删除
        if (min_list.empty()) _access_map.erase(_min_access_count);
        _hash_map.erase(evict_key);
    }
    // 不存在直接构造插入
    // 3. 插入新节点
    auto& new_list = _access_map[1];
    // 这里是 1，因为是新插入的节点，访问次数为 1
    _hash_map[key] = Node<K, V>(key, val, 1);
    // 这里也需要告诉编译器是个类型不是变量！！
    // 4. 更新访问次数 hash
    new_list.push_front(key);
    // 更新对应的 key 的 node 的迭代器
    _hash_map[key].it = new_list.begin();
    _min_access_count = 1;
    return true;
}

注：

这里有个坑点：就是必须先从对应 hash 中查找对应的 node，如果不存在的话，再去判断是否满了，进行删除以及后面的插入操作，不能上来就进行判满逻辑；否则比如满了，删了一个数据 1–2，但是插入的数据 key 存在，直接更新就好，因此这个 1–2 就相当于被误删了！

联合测试：

测试数据：按照规则，这里我们先淘汰的是 key 为 2 的数据，接着就是 key 为 4 的数据：

LFUCache<int, int> cache(3);
cache.put(1, 10);
cache.put(2, 20);
cache.put(3, 30);
cache.printCache();
cout << endl;
// 访问键 1，增加其访问次数
cout << "Get key 1: " << cache.get(1) << endl;
cache.printCache();
cout << endl;
// 添加新键 4，应淘汰访问次数最低的键 2
cache.put(4, 40);
cache.printCache();
cout << endl;
// 再次访问键 3，增加其访问次数
cout << "Get key 3: " << cache.get(3) << endl;
cache.printCache();
cout << endl;
// 添加新键 5，应淘汰访问次数最低的键 4
cache.put(5, 50);
cache.printCache();

效果：

[图：插入 key 为 1 2 3 结果] [图：查询 key 为 1 的结果] [图：插入 key 为 4 淘汰 key 为 2 的结果] [图：访问 key 为 3 插入 key 为 5 淘汰 key 为 4 的结果]

由此可以看出，全部符合预期，也就是这个简易版本的 LFU 缓存算法还算可以。

4. 为什么 LFU 用 双哈希表 + 双向链表？

首先我们要知道：

LFU 的核心需求是：缓存满时快速淘汰「访问频率最低」的数据，且每次访问数据时要快速更新其频率。如果用普通数组或单链表，找最低频率或移动节点都得遍历，效率太低（O(n)）。

因此需要：

1. 快速定位最低频率的数据（淘汰时用）；
2. 快速更新数据的访问频率（访问时用）；
3. 保证所有操作（查、增、删、频率更新）都是 O(1) 时间复杂度（高并发场景必备）。

设计策略：

• 哈希表 1（键 - 值映射）：存 key → 节点，快速根据 key 找到数据（O(1)）。
• 哈希表 2（频率 - 链表映射）：存频率 → 双向链表，把相同频率的数据串成链表，方便直接操作整组数据（O(1)）。
• 双向链表：每个频率对应的链表里，数据按访问时间排序（头部最新，尾部最久未访问），方便快速找到同频率中最该淘汰的节点（O(1)），其实就是每个 list 相当于按照 lru 机制进行添加/淘汰。
• 最小频率计数器：直接记录当前最低频率，淘汰时不用遍历所有频率（O(1)）。

效果：

• 淘汰时：通过最小频率指针找到最低频率的链表，直接取尾部节点（最久未访问的同频率数据）删除（O(1)）；
• 访问时：通过哈希表定位数据，更新频率后从原频率链表删掉，插入新频率链表头部（O(1)）。

三、典型优势与劣势

优势场景

[图：优势场景示意图]

1. 长期热点稳定：适合访问频率长期集中的数据（如经典文章、爆款商品、CDN 热门视频）。高频数据因频率持续累积，会被优先保留，减少重复计算/加载的开销。
2. 理论最优性：在'访问频率完全可预测且稳定'的场景下，LFU 能最大化缓存命中率（长期高频数据几乎不被淘汰）。

劣势与挑战

[图：劣势与挑战示意图]

1. 冷启动问题（新数据劣势）：新加入的数据初始频率为 0 或 1，即使近期被频繁访问，也可能因频率低于历史高频数据而被优先淘汰（例如：突然爆火的新商品挤不进缓存）。
2. 旧高频霸占问题：历史高频但当前不再使用的数据（如过季商品、旧闻）可能因早期积累的高频率长期占位，阻碍新热点数据的缓存（例如：经典老歌长期占缓存，新歌难进入）。
3. 实现复杂度高：需维护频率链表、最小频率计数器等结构，代码实现比 LRU 更复杂（但可通过哈希表 + 双向链表优化到 O(1) 操作）。

四、典型问题与优化策略

1. 新数据冷启动优化

[图：冷启动优化示意图]

• 初始频率加成：新数据的初始频率设为 1（或更高，如 2），避免因初始 0 被直接淘汰。
• 预热机制：对已知的高频新数据（如运营推荐的新品），手动初始化较高频率。
• 混合策略：结合 LRU 思想，对新数据给予短期'保护期'（例如：新数据前 N 次访问不参与频率竞争）。

2. 频率衰减（避免历史权重过高）

[图：频率衰减示意图]

• 定期衰减：每隔固定时间，所有数据的频率值减半（或减去固定值），降低历史高频数据的绝对优势（例如：每月将所有数据频率÷2，让近期活跃数据更容易反超）。
• 动态权重：引入时间衰减因子，近期访问的频率权重更高（例如：最近 1 天的访问次数×2，1 周前的访问次数×0.5）。

五、适用场景与典型用例

六、LFU vs LRU 对比

七、总结

LFU 是缓存中的'时间的朋友'——谁被访问的次数越多，谁就越容易被保留；但它需要解决'新数据入场难'和'旧热点占位'的问题，实际常通过优化策略（如频率衰减、初始加成）或与 LRU 结合（如 Redis 的近似 LFU）来平衡长期与短期热点需求。

八、小结

LFU 算法通过双哈希表和双向链表实现了高效的缓存淘汰机制，适合长期热点稳定的业务场景。开发者在实际应用中需注意冷启动和旧数据霸占问题，并结合具体业务进行优化。