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

LFU 缓存算法详解

一、核心原理

基础规则：优先淘汰历史访问频率最低的数据（长期统计维度）。

每个缓存条目维护两个核心属性：键值对数据 + 访问频率计数器。当缓存容量达到上限时，系统会选择当前所有数据中访问频率最低的条目进行淘汰；若多个数据的频率相同，则进一步淘汰其中最久未被访问的（类似 LRU 的兜底逻辑）。

操作流程：

访问数据时：命中缓存后，该数据的访问频率 +1，并调整其在频率排序中的位置（确保高频数据优先保留，也就是在双向链表头部）。
写入新数据时：若缓存未满，直接插入（初始频率通常为 1 或 0+1）；若缓存已满，先淘汰频率最低的数据，再写入新条目（新数据频率初始化为 1）；如果对应 key 值存在，那就更新对应 value，最后再调整对应频率。

二、关键特性与实现机制

1. 数据结构设计（高效实现的核心）

LFU 通常通过双哈希表 + 频率双向链表的组合实现 O(1) 时间复杂度的操作：

存储哈希表（Key-Node）：存储键到缓存条目数据集的映射（快速定位数据，方便及时更新频率操作）。
频率哈希表：以频率值为键，而 key 类型的双向链表为值，维护该频率下的所有数据节点（通常用双向链表存储，支持快速插入/删除）。
最小频率计数器：记录当前缓存中最低的频率值，淘汰时直接定位到该频率链表。

例如：当数据 A 被访问时，其频率从 1→2，需从原频率 1 的链表移除，并插入到频率 2 的链表头部；若新数据 B 写入，初始频率为 1，插入频率 1 链表。

2. 频率动态更新

每次访问（读/写）缓存数据时，触发频率 +1 的更新操作：

从原频率对应的链表中移除该数据节点；
将频率值 +1，并插入到新频率对应的链表头部（保证最近访问的数据在链表前端）；
更新全局最小频率（若原最小频率链表为空，则最小频率 +1）。

3. 实现思想及代码测试

我们下面要设计的这个 LFU 算法逻辑和上面的演示图是差不多，只不过我们存储的不是自定义节点的地址，而是这个 Node 对象，当然地址也行，其他都差不多。

对应的节点结构如下：

// 定义对应的节点结构：template<class K, class V>
struct Node {
    Node() {}
    // 表明对应的默认对象必须存在，hash[key] = Node()！！
    Node(const K& key, const V& value, int access_count)
        : key(key), value(value), access_count(access_count) {}
    
    K key;
    V value; // 存储对应 key 的访问次数
    int access_count;
    // 对应节点的 key 值所在的 list 处的迭代器
    typename std::list<K>::iterator it;
};

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

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<int>& 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.(key);
    
    _hash_map[key].it = new_list.();
    _min_access_count = ;
     ;
}

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

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

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

因此需要：

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

设计策略：

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

效果：

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

三、典型优势与劣势

优势场景

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

劣势与挑战

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

四、典型问题与优化策略

1. 新数据冷启动优化

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

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

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

五、适用场景与典型用例

场景类型	具体例子	为什么适合 LFU？
长期稳定热点	CDN 热门视频缓存、经典文档/教程页	这些内容长期被高频访问，频率持续累积，LFU 能确保其长期驻留缓存。
爆款商品/内容	电商平台的限时爆款、社交媒体的热帖	爆款期间访问频率极高，LFU 会优先保留，支撑高并发请求。
低更新频率服务	在线词典的热门词条、百科经典词条	词条热度长期稳定，高频词条（如'人工智能'）会被持续缓存。

六、LFU vs LRU 对比

维度	LFU（最不经常使用）	LRU（最近最少使用）
判断依据	历史访问频率（总次数）	最近一次访问时间（时间戳）
核心优势	保护长期高频热点数据，命中率高	快速响应新流量，适应突发热点
主要劣势	新数据易被淘汰，旧高频数据可能霸占	旧高频数据可能被误淘汰，不保护长期热点
实现复杂度	较高（需维护频率结构）	较低（只需维护访问时间顺序）
典型场景	经典内容、爆款商品、CDN 稳定热点	浏览器缓存、数据库 Buffer Pool、新热点
变种优化	LFU-LRU 混合、频率衰减、初始频率加成	LRU-K（考虑最近 K 次访问）、ARC（自适应）

总结

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

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