当前位置:首页 > 技术学院 > 技术前线
[导读]在计算机系统设计中,缓存是提升数据访问性能的核心技术——无论是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

#include

#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不仅能帮助你应对算法面试,更能理解缓存设计的核心思想,在实际开发中合理使用缓存提升系统性能。

本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除( 邮箱:macysun@21ic.com )。
关闭