C语言LFU缓存实现（手把手教你用C语言构建高效LFU缓存系统）

LFU缓存的关键挑战

实现一个高效的LFU缓存有两个主要难点：

• 如何快速找到使用频率最低的键？
• 如何在O(1)时间内更新某个键的频率？

为了解决这些问题，我们通常结合哈希表和双向链表来设计数据结构。这也是本教程采用的核心思路。

C语言LFU缓存实现步骤

我们将构建以下组件：

1. 节点结构：存储键、值、频率等信息。
2. 频率桶（Frequency Bucket）：每个频率对应一个双向链表，存放该频率下的所有节点。
3. 哈希表：通过键快速定位节点。
4. 全局最小频率记录：用于快速找到待淘汰的节点。

1. 定义数据结构

// 缓存节点typedef struct Node {    int key;    int val;    int freq;    struct Node* prev;    struct Node* next;} Node;// 频率桶：每个频率对应一个双向链表typedef struct FreqList {    int freq;    Node* head;    Node* tail;    struct FreqList* prev;    struct FreqList* next;} FreqList;// LFU缓存主结构typedef struct {    int capacity;    int size;    int minFreq;    Node** nodeMap;        // 哈希表：key -> Node*    FreqList** freqMap;    // 频率映射：freq -> FreqList*} LFUCache;

2. 辅助函数：创建节点和频率桶

Node* createNode(int key, int val) {    Node* node = (Node*)malloc(sizeof(Node));    node->key = key;    node->val = val;    node->freq = 1;    node->prev = node->next = NULL;    return node;}FreqList* createFreqList(int freq) {    FreqList* fl = (FreqList*)malloc(sizeof(FreqList));    fl->freq = freq;    fl->head = (Node*)malloc(sizeof(Node)); // 哨兵节点    fl->tail = (Node*)malloc(sizeof(Node));    fl->head->next = fl->tail;    fl->tail->prev = fl->head;    fl->prev = fl->next = NULL;    return fl;}

3. 核心操作：插入与获取

以下是 get 和 put 函数的简化实现逻辑：

int lfuGet(LFUCache* obj, int key) {    if (obj->capacity == 0) return -1;        Node* node = obj->nodeMap[key];    if (!node) return -1;        // 从旧频率桶中移除    removeNodeFromFreqList(obj, node);        // 更新频率    node->freq++;        // 加入新频率桶    addNodeToFreqList(obj, node);        // 更新 minFreq（若旧频率桶为空且等于minFreq）    if (obj->freqMap[node->freq - 1]->head->next == obj->freqMap[node->freq - 1]->tail &&        obj->minFreq == node->freq - 1) {        obj->minFreq = node->freq;    }        return node->val;}void lfuPut(LFUCache* obj, int key, int value) {    if (obj->capacity == 0) return;        if (obj->nodeMap[key]) {        // 更新已有键        obj->nodeMap[key]->val = value;        lfuGet(obj, key); // 复用 get 的频率更新逻辑        return;    }        if (obj->size >= obj->capacity) {        // 淘汰：从 minFreq 桶中删除尾部前一个节点        Node* victim = obj->freqMap[obj->minFreq]->tail->prev;        removeNodeFromFreqList(obj, victim);        obj->nodeMap[victim->key] = NULL;        free(victim);        obj->size--;    }        // 插入新节点    Node* newNode = createNode(key, value);    obj->nodeMap[key] = newNode;    obj->minFreq = 1;    addNodeToFreqList(obj, newNode);    obj->size++;}

为什么这个实现高效？

通过维护 minFreq 和频率桶，我们可以在 O(1) 时间内完成以下操作：

• 查找节点（哈希表）
• 更新频率（移动节点到新桶）
• 淘汰节点（从 minFreq 桶尾部删除）

这种设计充分体现了高效缓存设计的思想，也是工业级缓存系统常用的优化手段。

总结

通过本教程，你已经掌握了如何用C语言实现一个完整的LFU缓存系统。这不仅加深了你对LFU缓存算法的理解，也提升了你在C语言缓存机制方面的实战能力。建议你动手编写完整代码，并测试边界情况（如容量为0、重复插入等）。

记住，缓存是系统性能优化的关键一环，掌握LFU这样的高级淘汰策略，将为你在系统设计和面试中带来巨大优势！