C语言缓存数据结构（从零开始构建高效内存缓存系统）

为什么需要缓存数据结构？

在 C 语言中，没有内置的缓存类型。因此，开发者需要自行设计 内存缓存实现。一个好的缓存应具备以下特性：

• 快速查找（通常使用哈希表）
• 自动淘汰旧数据（如 LRU 策略）
• 线程安全（高级需求）
• 内存可控（防止内存泄漏）

实现一个简易 LRU 缓存

我们以 C语言LRU缓存 为例，LRU（Least Recently Used）是最常用的缓存淘汰策略：当缓存满时，移除最近最少使用的数据。

我们将结合 哈希表（快速查找）和 双向链表（维护使用顺序）来实现。

1. 定义数据结构

#include <stdio.h>#include <stdlib.h>#include <string.h>// 缓存节点typedef struct CacheNode {    int key;    int value;    struct CacheNode* prev;    struct CacheNode* next;} CacheNode;// 缓存结构体typedef struct {    int capacity;    int size;    CacheNode* head; // 最近使用    CacheNode* tail; // 最久未使用    CacheNode** hash_table; // 简易哈希表（数组模拟）    int table_size;} LRUCache;  

2. 初始化缓存

LRUCache* lru_cache_create(int capacity) {    LRUCache* cache = (LRUCache*)malloc(sizeof(LRUCache));    cache->capacity = capacity;    cache->size = 0;    cache->table_size = capacity * 2; // 哈希表大小设为容量两倍减少冲突        cache->hash_table = (CacheNode**)calloc(cache->table_size, sizeof(CacheNode*));        // 创建虚拟头尾节点，简化链表操作    cache->head = (CacheNode*)malloc(sizeof(CacheNode));    cache->tail = (CacheNode*)malloc(sizeof(CacheNode));    cache->head->next = cache->tail;    cache->tail->prev = cache->head;        return cache;}  

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

// 哈希函数（简单取模）static int hash(int key, int table_size) {    return (key % table_size + table_size) % table_size;}// 将节点移到头部（表示最近使用）static void move_to_head(LRUCache* cache, CacheNode* 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 lru_get(LRUCache* cache, int key) {    int idx = hash(key, cache->table_size);    CacheNode* node = cache->hash_table[idx];        while (node != NULL) {        if (node->key == key) {            move_to_head(cache, node);            return node->value;        }        node = node->next;    }    return -1; // 未找到}void lru_put(LRUCache* cache, int key, int value) {    int idx = hash(key, cache->table_size);    CacheNode* node = cache->hash_table[idx];        // 检查是否已存在    while (node != NULL) {        if (node->key == key) {            node->value = value;            move_to_head(cache, node);            return;        }        node = node->next;    }        // 新增节点    if (cache->size >= cache->capacity) {        // 淘汰 tail 前的节点（最久未使用）        CacheNode* last = cache->tail->prev;        int del_idx = hash(last->key, cache->table_size);        CacheNode** p = &cache->hash_table[del_idx];        while (*p != last) p = &(*p)->next;        *p = last->next;                last->prev->next = cache->tail;        cache->tail->prev = last->prev;        free(last);        cache->size--;    }        CacheNode* new_node = (CacheNode*)malloc(sizeof(CacheNode));    new_node->key = key;    new_node->value = value;        // 插入到头部    new_node->next = cache->head->next;    new_node->prev = cache->head;    cache->head->next->prev = new_node;    cache->head->next = new_node;        // 加入哈希表    new_node->next = cache->hash_table[idx];    cache->hash_table[idx] = new_node;        cache->size++;}  

使用示例

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

总结

通过本教程，你已经掌握了如何用 C 语言构建一个基础但实用的 高效缓存设计。虽然这个实现较为简化（例如哈希表使用链地址法但未处理所有冲突），但它清晰展示了缓存的核心思想。

在实际项目中，你可以进一步优化：使用更高效的哈希算法、支持泛型、添加线程锁等。掌握 C语言缓存数据结构 不仅能提升程序性能，也是深入理解系统编程的重要一步。

提示：完整代码可在本地编译测试，记得释放内存以避免泄漏！