如何用C++设计高性能LFU缓存淘汰机制的核心算法？

在构建高并发服务时，缓存层常需要按访问频率淘汰数据，LFU（Least Frequently Used）策略比LRU更能保留热点内容。本文用C++设计一个核心算法，使get与put操作均达到O(1)时间复杂度，关键在于频率链表与哈希表的配合。

LFU核心结构设计

我们维护一个哈希表key_to_node，将键映射到链表节点；另一个哈希表freq_to_list，将频率值映射到该频率下的双向链表。每个节点保存键、值、当前频率。这样命中时只需把节点从旧频率链表移到新频率链表头部。

节点与链表定义

#include <unordered_map>
#include <list>

struct Node {
    int key;
    int value;
    int freq;
    Node(int k, int v) : key(k), value(v), freq(1) {}
};

// 频率链表：每个频率对应一个list<Node*>
std::unordered_map<int, std::list<Node*>> freq_to_list;
std::unordered_map<int, Node*> key_to_node;
int min_freq = 0; // 当前最小频率，用于淘汰
int capacity = 0;

核心操作实现

get操作

若键存在，提升其频率：从原链表删除，频率加一后插入新链表头部，并更新min_freq。

int get(int key) {
    if (key_to_node.find(key) == key_to_node.end()) return -1;
    Node* node = key_to_node[key];
    // 从旧频率链表移除
    freq_to_list[node->freq].remove(node);
    if (freq_to_list[node->freq].empty()) {
        freq_to_list.erase(node->freq);
        if (min_freq == node->freq) min_freq++;
    }
    node->freq++;
    freq_to_list[node->freq].push_front(node);
    return node->value;
}

put操作

若容量满，从min_freq对应链表尾部淘汰节点；再插入新节点到频率1的链表。

void put(int key, int value) {
    if (capacity <= 0) return;
    if (key_to_node.find(key) != key_to_node.end()) {
        key_to_node[key]->value = value;
        get(key); // 触发频率提升
        return;
    }
    if (key_to_node.size() >= capacity) {
        auto& lst = freq_to_list[min_freq];
        Node* dead = lst.back();
        lst.pop_back();
        key_to_node.erase(dead->key);
        delete dead;
        if (lst.empty()) freq_to_list.erase(min_freq);
    }
    Node* node = new Node(key, value);
    key_to_node[key] = node;
    freq_to_list[1].push_front(node);
    min_freq = 1;
}

时间复杂度分析

上述设计中，哈希表定位为O(1)，链表删除与插入头部或尾部均为O(1)，因此get与put均满足常数时间。频率链表避免了每次全局排序，仅维护非空频率桶。

小结

使用C++实现LFU时，双哈希表加频率链表是兼顾性能与清晰度的方案。注意在节点删除时同步清理空链表与min_freq，可防止边界错误。

LFU_cacheC++_frequency_listtime_complexity修改时间：2026-07-30 16:54:24