C语言实现LRU缓存策略详解

[导读]在计算机系统设计中，缓存是提升数据访问性能的核心技术——无论是CPU的高速缓存，还是操作系统的页面置换，亦或是后端服务的热点数据缓存，都离不开高效的缓存淘汰策略。在众多淘汰算法中，LRU(Least Recently Used，最近最少使用)凭借实现简单、性能优异的特点，成为了最常用的策略之一。

在计算机系统设计中，缓存是提升数据访问性能的核心技术——无论是CPU的高速缓存，还是操作系统的页面置换，亦或是后端服务的热点数据缓存，都离不开高效的缓存淘汰策略。在众多淘汰算法中，LRU(Least Recently Used，最近最少使用)凭借实现简单、性能优异的特点，成为了最常用的策略之一。本文将从LRU的核心原理讲起，一步步用C语言实现一个高效、可运行的LRU缓存，带你完全掌握这一经典算法。

一、为什么需要LRU?缓存淘汰的底层逻辑

要理解LRU，我们首先得回到缓存的本质：缓存是用高速但容量有限的存储空间，存储低速存储设备中频繁访问的数据，从而提升整体访问速度。但容量有限是缓存的固有属性——当缓存被占满，有新数据需要加入时，我们必须决定删除哪些旧数据腾出空间，这个决策规则就是缓存淘汰策略。

常见的缓存淘汰策略有三种：先进先出(FIFO)淘汰最早进入缓存的数据，实现简单但无法区分数据的访问频率，可能会把频繁访问的热点数据误淘汰;最少使用(LFU)淘汰访问次数最少的数据，逻辑更合理，但实现复杂，需要记录每个数据的访问次数，且对热点数据的变化反应较慢，无法适应访问模式的变化;而LRU淘汰最近最少使用的数据，核心逻辑基于一个简单的经验假设：最近被访问过的数据，未来被访问的概率更高;很久没有被访问过的数据，未来被访问的概率更低，这一假设在大多数实际场景中都非常符合实际，兼顾了实现复杂度和命中率。

举个生活化的例子帮助理解：你作为图书馆管理员，书架只能放10本书，当新的书还回来但书架满了，你应该把哪本书拿走?最合理的选择就是拿走最久没人借过的那本，而不是最早放上去的或者被借次数最少的——这就是LRU的核心思想，和图书馆管理逻辑如出一辙。

二、LRU的实现思路：为什么需要双向链表+哈希表?

基础思路：仅用双向链表

LRU最基础的实现思路只需要一个双向链表，按照访问时间从新到旧排序：表头存放最近访问的数据，表尾存放最久未访问的数据。核心操作逻辑如下：

当访问一个已经在缓存中的数据时，把这个节点从原来的位置删除，重新插入到链表表头，表示它是最近刚被访问过。

当插入一个不在缓存中的新数据时：如果缓存还没满，直接把新节点插入表头即可;如果缓存已经满了，删除链表的表尾节点(最久未访问)，然后把新节点插入表头。

这个思路虽然简单，但存在一个致命问题：查找数据时需要从头到尾遍历链表，时间复杂度是O(n)，当缓存容量较大时，访问性能非常差，无法满足实际使用需求。

优化方案：哈希表加速查找

为了把查找的时间复杂度降到O(1)，我们引入哈希表：哈希表中存储key到对应链表节点的映射，只要通过key就能在O(1)时间内定位到节点，不需要遍历链表。这样一来，查找、插入、删除操作的平均时间复杂度都能达到O(1)，满足高性能要求。

最终我们确定了LRU的经典数据结构组合：双向链表负责维护数据的访问顺序，哈希表负责O(1)快速查找节点，两种结构配合工作，完美实现LRU算法。

三、C语言结构体定义：清晰规划数据结构

接下来我们开始用C语言实现LRU缓存，第一步是定义需要用到的结构体。首先是链表节点结构体，每个节点需要存储key、value，以及前驱和后继指针：

#include

#define KEY_SIZE 32 // key最大长度

#define VALUE_SIZE 128 // value最大长度

// 双向链表节点(同时也是哈希表节点)

typedef struct cacheEntry {

char key[KEY_SIZE]; // 数据的键

char value[VALUE_SIZE]; // 数据的值

struct cacheEntry *lruPrev; // 双向链表前驱指针

struct cacheEntry *lruNext; // 双向链表后继指针

struct cacheEntry *hashPrev; // 哈希链表前驱指针

struct cacheEntry *hashNext; // 哈希链表后继指针

} cacheEntry;

// LRU缓存整体结构体

typedef struct {

int capacity; // 缓存最大容量

int size; // 当前缓存已使用大小

cacheEntry *head; // 双向链表表头(最近访问)

cacheEntry *tail; // 双向链表表尾(最久未访问)

cacheEntry **hashMap; // 哈希表(数组存储，每个元素是哈希链表头)

int hashCapacity; // 哈希表容量

} LRUCache;

这里我们采用链式哈希解决哈希冲突，所以每个节点额外保留哈希链表的前后指针;如果key是整数，也可以采用简单数组直接映射，实现更简单。

四、核心操作实现：一步步搭建LRU

1. 缓存创建与初始化

创建LRU缓存时，需要分配缓存结构体的内存，初始化双向链表表头表尾，分配哈希表数组空间：

// 哈希函数，简单的字符串哈希

static unsigned int hash(const char *key) {

unsigned int hash = 0;

while (*key) {

hash = hash * 31 + *key++;

}

return hash;

}

// 创建LRU缓存，capacity为缓存最大容量，hashCap为哈希表容量

LRUCache* lruCacheCreate(int capacity, int hashCap) {

LRUCache *cache = (LRUCache*)malloc(sizeof(LRUCache));

if (!cache) return NULL;

cache->capacity = capacity;

cache->size = 0;

cache->head = NULL;

cache->tail = NULL;

cache->hashCapacity = hashCap;

cache->hashMap = (cacheEntry**)calloc(hashCap, sizeof(cacheEntry*));

if (!cache->hashMap) {

free(cache);

return NULL;

}

return cache;

}

2. 移动节点到表头：标记为最近访问

当某个数据被访问后，我们需要把它移动到双向链表表头，标记为最近访问：

// 把节点从双向链表中移除

void removeNodeFromList(LRUCache *cache, cacheEntry *node) {

if (node->lruPrev) {

node->lruPrev->lruNext = node->lruNext;

} else {

// 移除的是头节点，更新头指针

cache->head = node->lruNext;

}

if (node->lruNext) {

node->lruNext->lruPrev = node->lruPrev;

} else {

// 移除的是尾节点，更新尾指针

cache->tail = node->lruPrev;

}

// 把节点插入到双向链表表头

void addNodeToHead(LRUCache *cache, cacheEntry *node) {

node->lruPrev = NULL;

node->lruNext = cache->head;

if (cache->head) {

cache->head->lruPrev = node;

}

cache->head = node;

// 如果原来链表为空，尾指针也要指向该节点

if (!cache->tail) {

cache->tail = node;

}

// 移动已存在节点到表头

void moveToHead(LRUCache *cache, cacheEntry *node) {

removeNodeFromList(cache, node);

addNodeToHead(cache, node);

}

3. 哈希表查找节点

通过key在哈希表中查找对应的节点：

// 在哈希表中查找节点

cacheEntry* findNodeInHash(LRUCache *cache, const char *key) {

unsigned int idx = hash(key) % cache->hashCapacity;

cacheEntry *node = cache->hashMap[idx];

while (node) {

if (strcmp(node->key, key) == 0) {

return node;

}

node = node->hashNext;

}

return NULL;

}

4. 删除表尾节点：淘汰最久未访问的数据

当缓存满了，插入新数据前需要删除表尾节点，同时也要从哈希表中移除：

// 从哈希表中删除节点

void removeNodeFromHash(LRUCache *cache, cacheEntry *node) {

unsigned int idx = hash(node->key) % cache->hashCapacity;

if (node->hashPrev) {

node->hashPrev->hashNext = node->hashNext;

} else {

cache->hashMap[idx] = node->hashNext;

}

if (node->hashNext) {

node->hashNext->hashPrev = node->hashPrev;

}

// 删除LRU尾部的最久未访问节点

cacheEntry* removeTail(LRUCache *cache) {

cacheEntry *node = cache->tail;

removeNodeFromList(cache, node);

removeNodeFromHash(cache, node);

return node;

}

5. 对外接口：get和put操作

LRU缓存最核心的两个对外接口就是获取数据get和插入/更新数据put：

// 获取key对应的值，不存在返回NULL

char* lruCacheGet(LRUCache *cache, const char *key) {

cacheEntry *node = findNodeInHash(cache, key);

if (!node) {

return NULL;

}

// 找到后移动到表头，标记为最近访问

moveToHead(cache, node);

return node->value;

}

// 插入或更新key-value

void lruCachePut(LRUCache *cache, const char *key, const char *value) {

// 先看是否已经存在

cacheEntry *node = findNodeInHash(cache, key);

if (node) {

// 存在则更新值，移动到表头

strncpy(node->value, value, VALUE_SIZE - 1);

moveToHead(cache, node);

return;

}

// 不存在，创建新节点

node = (cacheEntry*)malloc(sizeof(cacheEntry));

if (!node) return;

strncpy(node->key, key, KEY_SIZE - 1);

strncpy(node->value, value, VALUE_SIZE - 1);

// 插入哈希表

unsigned int idx = hash(key) % cache->hashCapacity;

node->hashNext = cache->hashMap[idx];

if (cache->hashMap[idx]) {

cache->hashMap[idx]->hashPrev = node;

}

cache->hashMap[idx] = node;

node->hashPrev = NULL;

// 插入链表表头

addNodeToHead(cache, node);

cache->size++;

// 如果超过容量，淘汰尾部

if (cache->size > cache->capacity) {

cacheEntry *tail = removeTail(cache);

free(tail);

cache->size--;

}

6. 缓存销毁：释放内存

最后我们需要提供销毁缓存释放内存的接口，避免内存泄漏：

void lruCacheDestroy(LRUCache *cache) {

cacheEntry *cur = cache->head;

while (cur) {

cacheEntry *next = cur->lruNext;

free(cur);

cur = next;

}

free(cache->hashMap);

free(cache);

}

五、测试与验证：看看我们的LRU是否正确

我们写一个简单的main函数测试LRU缓存的功能：

// 打印当前缓存内容，从表头到表尾

void lruCachePrint(LRUCache *cache) {

printf("当前缓存顺序(表头->表尾，最近访问->最久未访问)：");

cacheEntry *cur = cache->head;

while (cur) {

printf("%s ", cur->key);

cur = cur->lruNext;

}

printf("\n");

}

int main() {

// 创建容量为3的LRU缓存，哈希表容量为10

LRUCache *cache = lruCacheCreate(3, 10);

printf("创建容量为3的LRU缓存\n");

// 插入三个数据

lruCachePut(cache, "key1", "value1");

lruCachePut(cache, "key2", "value2");

lruCachePut(cache, "key3", "value3");

lruCachePrint(cache);

// 插入第四个数据，淘汰key1

lruCachePut(cache, "key4", "value4");

lruCachePrint(cache);

printf("访问key1结果：%s\n", lruCacheGet(cache, "key1")?lruCacheGet(cache, "key1"):"不存在");

// 访问key3，移动到表头，此时最久未访问是key2

printf("访问key3结果：%s\n", lruCacheGet(cache, "key3"));

lruCachePrint(cache);

// 插入新数据key5，淘汰key2

lruCachePut(cache, "key5", "value5");

lruCachePrint(cache);

printf("访问key2结果：%s\n", lruCacheGet(cache, "key2")?lruCacheGet(cache, "key2"):"不存在");

lruCacheDestroy(cache);

return 0;

}

程序运行结果和我们预期完全一致：

创建容量为3的LRU缓存

当前缓存顺序(表头->表尾，最近访问->最久未访问)：key3 key2 key1

当前缓存顺序(表头->表尾，最近访问->最久未访问)：key4 key3 key2

访问key1结果：不存在

访问key3结果：value3

当前缓存顺序(表头->表尾，最近访问->最久未访问)：key3 key4 key2

当前缓存顺序(表头->表尾，最近访问->最久未访问)：key5 key3 key4

访问key2结果：不存在

六、LRU的局限性与优化方向

我们实现的是基础版本的LRU，在实际应用中还可以做很多优化：基础LRU存在缓存污染问题：一次性批量访问大量冷数据会把缓存中的热点数据全部淘汰，导致命中率骤降。针对这个问题的优化方案有LRU-K，要求数据被访问K次才会进入主缓存，过滤掉一次性冷数据;还有分段LRU，把缓存分为热点段和冷段，只有热点段的数据才会被淘汰，减少缓存污染。

另外如果是并发场景，我们的实现还需要添加锁控制，我们上面示例代码中预留了锁的位置，可以根据需求给整个缓存加锁，或者分段加锁减少锁冲突，提升并发性能。

LRU缓存策略是计算机领域非常经典的算法，用双向链表加哈希表实现O(1)平均时间复杂度，逻辑清晰，性能优异，非常适合作为数据结构学习的入门案例。本文我们从原理讲起，一步步用C语言完成了完整的LRU缓存实现，并且通过测试验证了功能正确性。掌握LRU不仅能帮助你应对算法面试，更能理解缓存设计的核心思想，在实际开发中合理使用缓存提升系统性能。