C语言缓存实现方法（从零开始构建高效内存缓存系统）

什么是缓存？

缓存（Cache）是一种临时存储机制，用于保存频繁访问的数据副本，以便下次快速获取。在 C 语言中，我们通常使用数组、链表或哈希表等数据结构来实现缓存。

常见的缓存淘汰策略包括：

• FIFO（先进先出）
• LRU（最近最少使用）
• LFU（最不经常使用）

本文将以 LRU 缓存 为例，展示如何用 C 语言实现一个基础但高效的 内存缓存设计。

LRU 缓存的基本原理

LRU（Least Recently Used）策略认为：最近被访问过的数据更可能再次被访问，而长时间未使用的数据可以被淘汰。

为了高效实现 LRU，我们通常结合 哈希表（用于 O(1) 查找）和 双向链表（用于 O(1) 插入/删除）。

C语言实现步骤

1. 定义数据结构

首先，我们需要定义缓存节点和缓存结构体：

#include <stdio.h>#include <stdlib.h>#include <string.h>// 缓存节点typedef struct Node {    int key;    int value;    struct Node* prev;    struct Node* next;} Node;// LRU 缓存结构typedef struct {    int capacity;    int size;    Node* head;    Node* tail;    Node** cache; // 哈希表（简化版，用数组模拟）} LRUCache;

2. 初始化缓存

LRUCache* lruCreate(int capacity) {    LRUCache* cache = (LRUCache*)malloc(sizeof(LRUCache));    cache->capacity = capacity;    cache->size = 0;        // 创建虚拟头尾节点，简化边界处理    cache->head = (Node*)malloc(sizeof(Node));    cache->tail = (Node*)malloc(sizeof(Node));    cache->head->next = cache->tail;    cache->tail->prev = cache->head;        // 简化哈希表：假设 key 范围为 0~999    cache->cache = (Node**)calloc(1000, sizeof(Node*));        return cache;}

3. 实现核心操作

主要包括 get 和 put 操作：

// 将节点移到头部（表示最近使用）void moveToHead(LRUCache* cache, Node* node) {    // 先断开    node->prev->next = node->next;    node->next->prev = node->prev;        // 插入到 head 后    node->next = cache->head->next;    node->prev = cache->head;    cache->head->next->prev = node;    cache->head->next = node;}int lruGet(LRUCache* cache, int key) {    if (cache->cache[key] == NULL) {        return -1; // 未命中    }        Node* node = cache->cache[key];    moveToHead(cache, node);    return node->value;}void lruPut(LRUCache* cache, int key, int value) {    if (cache->cache[key] != NULL) {        // 更新值并移到头部        cache->cache[key]->value = value;        moveToHead(cache, cache->cache[key]);    } else {        // 新增节点        if (cache->size >= cache->capacity) {            // 淘汰尾部节点（最久未用）            Node* last = cache->tail->prev;            cache->cache[last->key] = NULL;            last->prev->next = cache->tail;            cache->tail->prev = last->prev;            free(last);            cache->size--;        }                Node* newNode = (Node*)malloc(sizeof(Node));        newNode->key = key;        newNode->value = value;                // 插入头部        newNode->next = cache->head->next;        newNode->prev = cache->head;        cache->head->next->prev = newNode;        cache->head->next = newNode;                cache->cache[key] = newNode;        cache->size++;    }}

测试你的缓存

int main() {    LRUCache* cache = lruCreate(2);        lruPut(cache, 1, 1);    lruPut(cache, 2, 2);    printf("%d\n", lruGet(cache, 1));   // 输出 1    lruPut(cache, 3, 3);                // 淘汰 key=2    printf("%d\n", lruGet(cache, 2));   // 输出 -1（未找到）    lruPut(cache, 4, 4);                // 淘汰 key=1    printf("%d\n", lruGet(cache, 1));   // 输出 -1    printf("%d\n", lruGet(cache, 3));   // 输出 3    printf("%d\n", lruGet(cache, 4));   // 输出 4        return 0;}

总结

通过本教程，你已经掌握了如何用 C 语言实现一个基本的 LRU 缓存系统。这种 高效缓存机制 在实际项目中非常有用，例如 Web 服务器缓存、数据库查询缓存等。

虽然我们的实现使用了简化版的哈希表（固定大小数组），但在真实场景中，你可以替换为更复杂的哈希函数或使用开源哈希库（如 uthash）来支持任意 key 类型。

掌握 C语言LRU缓存 的实现，不仅能加深你对数据结构的理解，还能显著提升程序性能。快动手试试吧！