C语言LRU缓存实现（手把手教你用C语言构建高效LRU缓存机制）

什么是LRU缓存？

LRU缓存的核心思想是：当缓存空间已满，需要腾出位置时，优先淘汰最久未被访问的数据。这种策略基于“局部性原理”——最近被访问的数据很可能再次被访问。

例如，一个容量为3的LRU缓存：

• 插入 A → [A]
• 插入 B → [B, A]
• 插入 C → [C, B, A]
• 访问 B → [B, C, A]（B移到最前）
• 插入 D → [D, B, C]（A被淘汰）

实现思路

为了高效实现LRU，我们需要支持以下操作：

• get(key)：获取值，若存在则将其移到“最近使用”位置
• put(key, value)：插入或更新键值对，若缓存满则淘汰最久未用项

关键点在于：快速查找（哈希表） + 快速移动/删除（双向链表）。这就是经典的“哈希链表”结构。

C语言实现步骤

1. 定义数据结构

首先定义双向链表节点和LRU缓存结构：

// 双向链表节点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** map;   // 简易哈希表（数组模拟，实际项目建议用哈希库）} LRUCache;

2. 辅助函数：添加到头部 & 删除节点

// 将节点添加到链表头部（head之后）void addToHead(LRUCache* cache, Node* node) {    node->prev = cache->head;    node->next = cache->head->next;    cache->head->next->prev = node;    cache->head->next = node;}// 删除指定节点void removeNode(Node* node) {    node->prev->next = node->next;    node->next->prev = node->prev;}// 移动节点到头部void moveToHead(LRUCache* cache, Node* node) {    removeNode(node);    addToHead(cache, node);}

3. 初始化缓存

LRUCache* lRUCacheCreate(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~9999）    cache->map = (Node**)calloc(10000, sizeof(Node*));        return cache;}

4. 实现 get 和 put

int lRUCacheGet(LRUCache* obj, int key) {    if (obj->map[key] == NULL) {        return -1; // 未找到    }    // 找到后移到头部    Node* node = obj->map[key];    moveToHead(obj, node);    return node->value;}void lRUCachePut(LRUCache* obj, int key, int value) {    if (obj->map[key] != NULL) {        // 更新现有节点        Node* node = obj->map[key];        node->value = value;        moveToHead(obj, node);    } else {        // 插入新节点        if (obj->size >= obj->capacity) {            // 缓存满，删除尾部节点（最久未用）            Node* tail = obj->tail->prev;            removeNode(tail);            obj->map[tail->key] = NULL;            free(tail);            obj->size--;        }                Node* newNode = (Node*)malloc(sizeof(Node));        newNode->key = key;        newNode->value = value;        obj->map[key] = newNode;        addToHead(obj, newNode);        obj->size++;    }}

完整使用示例

#include <stdio.h>#include <stdlib.h>// ... 上面所有函数定义 ...int main() {    LRUCache* cache = lRUCacheCreate(2);        lRUCachePut(cache, 1, 1);    lRUCachePut(cache, 2, 2);    printf("%d\n", lRUCacheGet(cache, 1)); // 输出 1    lRUCachePut(cache, 3, 3); // 淘汰 key=2    printf("%d\n", lRUCacheGet(cache, 2)); // 输出 -1    lRUCachePut(cache, 4, 4); // 淘汰 key=1    printf("%d\n", lRUCacheGet(cache, 1)); // 输出 -1    printf("%d\n", lRUCacheGet(cache, 3)); // 输出 3    printf("%d\n", lRUCacheGet(cache, 4)); // 输出 4        return 0;}

性能与优化建议

本实现的时间复杂度为：

• get：O(1)
• put：O(1)

但注意：我们使用了固定大小数组模拟哈希表（仅适用于key范围小的情况）。在真实项目中，建议使用成熟的哈希库（如 uthash）来替代，以支持任意key类型并避免哈希冲突问题。

总结

通过本文，你已经掌握了如何用 C语言实现LRU缓存。这项技能不仅加深了你对 LRU算法 的理解，也提升了你在 C语言缓存机制 和 内存管理 方面的实战能力。LRU广泛应用于数据库、操作系统、Web服务器等领域，是面试高频考点，也是系统设计的基础组件。

动手试试吧！你可以尝试扩展它：支持字符串key、自动扩容、线程安全等。编程的世界，实践出真知！