LRU缓存算法

引言

LRU（最近最少使用算法），是一种内存数据淘汰策略，使用常见是当内存不足时，需要淘汰最近最少使用的数据，以腾出空间给新的数据

LRU缓存算法原理

下面会重点介绍核心的数据结构和操作原理

核心数据结构：双向链表 + 哈希表

LRU缓存算法的核心思想是维护一个有序的数据结构，记录数据的使用顺序。当数据被访问时，将其移动到数据结构的头部，表示它是最近使用的数据。当缓存达到容量限制时，淘汰数据结构尾部的数据，即最少使用的数据

核心操作原理

1. 读取数据 (Get)

• 查找：在哈希表中查找该 key。
• 命中：如果找到，根据哈希表记录的指针直接访问链表节点，获取 value。
• 更新状态：因为该节点被访问了，它变成了“最新”的，所以将其从链表当前位置删除，并重新插入到链表尾部。
• 未命中：返回 -1。

2. 写入/更新数据 (Put)
节点已存在：

• 修改该节点的 value。
• 将该节点移到链表尾部（更新时序）。

节点不存在：

• 检查容量：如果缓存已满（size == capacity），则执行“淘汰”：
  • 删除链表头部（Head->next）的节点，因为它最久没被使用。
  • 同步在哈希表中删除该节点的 key。
• 插入新节点：创建新节点，放入链表尾部，并在哈希表中记录映射关系。

C语言实现

LeetCode 146. LRU 缓存
下面是LRU缓存算法的C语言实现代码

使用uthash库实现

#include "uthash.h"

typedef struct {
    int key;
    int val;
    UT_hash_handle hh;
} LRUNode;

typedef struct {
    LRUNode* cacheTable;
    int capacity;
} LRUCache;

LRUCache* lRUCacheCreate(int capacity) {
    LRUCache* cache = (LRUCache*)malloc(sizeof(LRUCache));
    cache->cacheTable = NULL;
    cache->capacity = capacity;
    return cache;
}

int lRUCacheGet(LRUCache* obj, int key) {
    if (!obj) return -1;
    LRUNode* node = NULL;
    HASH_FIND_INT(obj->cacheTable, &key, node);
    if (node) {
        HASH_DEL(obj->cacheTable, node);
        HASH_ADD_INT(obj->cacheTable, key, node);
        return node->val;
    }
    return -1;
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    if (!obj) return;
    LRUNode* node = NULL;
    HASH_FIND_INT(obj->cacheTable, &key, node);
    if (node) {
        HASH_DEL(obj->cacheTable, node);
        node->val = value;
        HASH_ADD_INT(obj->cacheTable, key, node);
    } else {
        if (HASH_COUNT(obj->cacheTable) == obj->capacity) {
            LRUNode* oldestNode = obj->cacheTable;
            HASH_DEL(obj->cacheTable, oldestNode);
            free(oldestNode);
        }
        LRUNode* newNode = (LRUNode*)malloc(sizeof(LRUNode));
        newNode->key = key;
        newNode->val = value;
        HASH_ADD_INT(obj->cacheTable, key, newNode);
    }
}

void lRUCacheFree(LRUCache* obj) {
    if (!obj) return;
    LRUNode* node, *tmp;
    HASH_ITER(hh, obj->cacheTable, node, tmp) {
        HASH_DEL(obj->cacheTable, node);
        free(node);
    }
    free(obj);
}

手搓双向链表 + 哈希表实现

// 双向链表节点
typedef struct DLinkNode {
    int key;
    int val;
    struct DLinkNode* prev;
    struct DLinkNode* next;
} DLinkNode;

DLinkNode* createNode(int key, int val) {
    DLinkNode* node = (DLinkNode*)malloc(sizeof(DLinkNode));
    node->key = key;
    node->val = val;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

// 简易哈希表（数组+链地址法）
#define HASH_TABLE_SIZE 1009

typedef struct HashBucket {
    int key;
    DLinkNode* node;
    struct HashBucket* next;
} HashBucket;

static inline unsigned int hashFunc(int key) {
    return (unsigned int)(key < 0 ? -key : key) % HASH_TABLE_SIZE;
}

// LRU缓存对象
typedef struct {
    DLinkNode* head;
    DLinkNode* tail;
    HashBucket* hashTable[HASH_TABLE_SIZE];
    int capacity;
    int size;
} LRUCache;

// 辅助函数，双向链表操作
// 将新节点加到双向链表尾部
void addToTail(LRUCache* cache, DLinkNode* node) {
    node->prev = cache->tail->prev;
    node->next = cache->tail;
    cache->tail->prev->next = node;
    cache->tail->prev = node;
}

// 从链表中移除节点
// 因为有哨兵节点，所以不需要考虑边界
void removeNode(LRUCache* cache, DLinkNode* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

// 将已有节点移到链表尾部（表示最近使用过）
void moveToTail(LRUCache* cache, DLinkNode* node) {
    removeNode(cache, node);
    addToTail(cache, node);
}

// 删除头部节点，也就是最近没使用过，并返回key
int removeHead(LRUCache* cache) {
    DLinkNode* oldest = cache->head->next;
    int key = oldest->key;
    removeNode(cache, oldest);
    free(oldest);
    return key;
}

// 哈希表操作
// 查找key对应的节点指针
DLinkNode* hashFind(LRUCache* cache, int key) {
    unsigned int idx = hashFunc(key);
    HashBucket* bucket = cache->hashTable[idx];
    while (bucket) {
        if (bucket->key == key) {
            return bucket->node;
        }
        bucket = bucket->next;
    }
    return NULL;
}

// 插入，key->node的映射
void hashInsert(LRUCache* cache, int key, DLinkNode* node) {
    unsigned int idx = hashFunc(key);
    HashBucket* newBucket = (HashBucket*)malloc(sizeof(HashBucket));
    newBucket->key = key;
    newBucket->node = node;
    newBucket->next = cache->hashTable[idx];
    cache->hashTable[idx] = newBucket;
}

// 删除key的映射
void hashDelete(LRUCache* cache, int key) {
    unsigned int idx = hashFunc(key);
    HashBucket** indirect = &(cache->hashTable[idx]);
    while (*indirect) {
        if ((*indirect)->key == key) {
            HashBucket* toFree = *indirect;
            *indirect = toFree->next;
            free(toFree);
            return;
        }
        // indirect本身,而不是*indirect指向的内容
        indirect = &((*indirect)->next);
    }
}

// LRU接口实现
LRUCache* lRUCacheCreate(int capacity) {
    LRUCache* cache = (LRUCache*)malloc(sizeof(LRUCache));
    cache->capacity = capacity;
    cache->size = 0;

    // 初始化哨兵节点
    cache->head = createNode(0, 0);
    cache->tail = createNode(0, 0);
    cache->head->next = cache->tail;
    cache->tail->prev = cache->head;

    // 初始化哈希表
    memset(cache->hashTable, 0, sizeof(cache->hashTable));
    return cache;
}

int lRUCacheGet(LRUCache* obj, int key) {
    if (!obj) return -1;
    DLinkNode* node = hashFind(obj, key);
    if (node == NULL) return -1;
    moveToTail(obj, node);
    return node->val;
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    if (!obj) return;
    DLinkNode* node = hashFind(obj, key);
    if (node) {
        node->val = value;
        moveToTail(obj, node);
    } else {
        if (obj->size >= obj->capacity) {
            int oldestKey = removeHead(obj);
            hashDelete(obj, oldestKey);
            obj->size--;
        }
        DLinkNode* newNode = createNode(key, value);
        addToTail(obj, newNode);
        hashInsert(obj, key, newNode);
        obj->size++;
    }
}

void lRUCacheFree(LRUCache* obj) {
    if (!obj) return;
    DLinkNode* cur = obj->head->next;
    while (cur != obj->tail) {
        DLinkNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(obj->head);
    free(obj->tail);
    for (int i = 0; i < HASH_TABLE_SIZE; i++) {
        HashBucket* bucket = obj->hashTable[i];
        while (bucket) {
            HashBucket* next = bucket->next;
            free(bucket);
            bucket = next;
        }
    }
    free(obj);
}

代码分析

结构体分析

1. DLinkNode：双向链表节点，包含 key、val、prev、next。用于维护最近使用顺序（尾部为最近使用，头部为最久未用）。
2. HashBucket：哈希桶中的链表节点（链地址法），每个桶是一个链表，解决哈希冲突。存储 key 和对应的 DLinkNode* 指针，避免重复存储值
3. LRUCache：缓存主体，head / tail：哨兵节点（dummy nodes），简化边界处理。hashTable：静态数组 + 链表，快速查找。capacity / size：容量控制

操作分析

1. addToTail：将节点添加到链表尾部，表示最近使用
2. removeNode：从链表中移除节点
3. moveToTail：将已有节点移到链表尾部，更新使用顺序
4. removeHead：删除链表头部节点，淘 汰最久未用数据
5. hashFind / hashInsert / hashDelete：哈希表的基本操作
6. lRUCacheGet：获取数据，更新使用顺序
7. lRUCachePut：插入/更新数据，处理容量限制

亮点学习

1. 哨兵节点：使用 head / tail 哨兵节点，简化链表边界操作，避免频繁判断 NULL
2. 链地址法哈希表：使用静态数组 + 链表解决哈希冲突，节省空间
3. 时间复杂度：所有操作均为 O(1)，满足 LRU 缓存的高效需求

总结

LRU缓存算法通过双向链表和哈希表实现高效的缓存管理，本文介绍了两种C语言实现方式：一种使用uthash库简化哈希操作，另一种手搓数据结构以深入理解底层原理