17、LRU缓存淘汰策略：基于双向链表+哈希表的LRU实现

LRU，全称 Least Recently Used，翻译过来就是「最近最少使用」。说白了，这是一种缓存淘汰策略——当缓存满了，新数据要进来，就得把最久没被用过的那个数据踢出去。

我刚开始接触 LRU 时，觉得这玩意儿不就是「谁最后被访问，谁就留在最前面」嘛。但真正动手实现时，才发现坑不少。尤其是性能要求高的场景，比如嵌入式里的文件系统缓存、网络协议栈的报文缓存，随便写个 O(n) 的查找，系统直接卡死。

所以，工业级的 LRU 实现，几乎都是双向链表 + 哈希表的组合。今天我就带你手撕一个。

为什么是双向链表 + 哈希表？

先想想 LRU 需要哪些操作：

• 快速查找某个 key 是否存在
• 快速把某个节点移动到链表头部（表示最近被用过）
• 快速删除链表尾部节点（淘汰最久未使用的）

哈希表负责 O(1) 查找，双向链表负责 O(1) 插入和删除。两者一结合，所有操作都是常数时间。嗯，这才是嵌入式系统该有的样子。

数据结构设计

先定义节点和缓存结构。我个人习惯把节点设计成双向链表的标准形式，前后指针都带上。

// 缓存节点
typedef struct LRUNode {
    int key;
    int value;
    struct LRUNode *prev;
    struct LRUNode *next;
} LRUNode;

// LRU 缓存主体
typedef struct {
    int capacity;          // 最大容量
    int size;              // 当前节点数
    LRUNode *head;         // 虚拟头节点
    LRUNode *tail;         // 虚拟尾节点
    LRUNode **hashTable;   // 哈希表，存 key -> 节点指针
} LRUCache;

这里我用了虚拟头尾节点。为什么？因为这样在插入和删除时，不需要判断 head 或 tail 是否为 NULL，代码简洁很多，也不容易出空指针异常。我在项目中吃过这个亏——有一次嵌入式设备跑着跑着就重启了，查了半天发现是链表头节点为空时还在操作 next 指针。从那以后，虚拟节点就成了我的标配。

哈希表实现

哈希表的大小，我建议取 capacity 的 2 倍左右，并且最好是质数。这样可以减少哈希冲突。当然，嵌入式环境内存有限，你也可以直接用 capacity 大小，配合链表法解决冲突。

#define HASH_SIZE(cap)  ((cap) * 2 + 1)

// 简单的哈希函数
static int hashKey(int key, int tableSize) {
    return key % tableSize;
}

哈希表里存的是 LRUNode* 指针数组。如果发生冲突，用链地址法——也就是每个哈希桶挂一个链表。不过注意，这里的链表和 LRU 的双向链表是两码事，别搞混了。

核心操作实现

1. 初始化

LRUCache* lruCreate(int capacity) {
    LRUCache *cache = (LRUCache*)malloc(sizeof(LRUCache));
    cache->capacity = capacity;
    cache->size = 0;

    // 创建虚拟头尾节点
    cache->head = (LRUNode*)malloc(sizeof(LRUNode));
    cache->tail = (LRUNode*)malloc(sizeof(LRUNode));
    cache->head->next = cache->tail;
    cache->tail->prev = cache->head;

    // 初始化哈希表
    int tableSize = HASH_SIZE(capacity);
    cache->hashTable = (LRUNode**)calloc(tableSize, sizeof(LRUNode*));

    return cache;
}

初始化时，虚拟头尾节点互相指向，形成一个空的双向链表。哈希表全部置 NULL。

2. 节点移动到头部

这是 LRU 最核心的操作。每次访问一个节点，都要把它「抽出来」放到链表最前面。

static void moveToHead(LRUCache *cache, LRUNode *node) {
    // 先从当前位置摘下来
    node->prev->next = node->next;
    node->next->prev = node->prev;

    // 插入到虚拟头节点之后
    node->next = cache->head->next;
    node->prev = cache->head;
    cache->head->next->prev = node;
    cache->head->next = node;
}

你想想看，如果没有虚拟头节点，这里就要判断 cache->head->next 是不是 NULL，代码量至少翻一倍。嗯，这就是经验。

3. 删除尾部节点

当缓存满了，需要淘汰最久未使用的节点，也就是链表尾部那个。

static LRUNode* removeTail(LRUCache *cache) {
    LRUNode *node = cache->tail->prev;
    if (node == cache->head) {
        return NULL;  // 链表为空
    }

    // 从链表中移除
    node->prev->next = cache->tail;
    cache->tail->prev = node->prev;

    return node;
}

注意，这里只是从链表移除，并没有释放内存。调用者需要从哈希表中删除对应 key，再 free 节点。

4. get 操作

int lruGet(LRUCache *cache, int key) {
    int idx = hashKey(key, HASH_SIZE(cache->capacity));
    LRUNode *node = cache->hashTable[idx];

    // 遍历哈希桶链表查找
    while (node) {
        if (node->key == key) {
            moveToHead(cache, node);
            return node->value;
        }
        node = node->next;  // 这里假设哈希桶用链表法
    }
    return -1;  // 没找到
}

这里有个细节：哈希桶里的链表和 LRU 的双向链表是同一个节点。也就是说，每个节点既在哈希桶的链表里，也在 LRU 的双向链表里。所以移动节点时，哈希桶的链表结构不受影响——我们只改了 prev 和 next 指针，而哈希桶链表是单向遍历的，不依赖 prev。

5. put 操作

void lruPut(LRUCache *cache, int key, int value) {
    int idx = hashKey(key, HASH_SIZE(cache->capacity));
    LRUNode *node = cache->hashTable[idx];

    // 先查找是否已存在
    while (node) {
        if (node->key == key) {
            node->value = value;
            moveToHead(cache, node);
            return;
        }
        node = node->next;
    }

    // 不存在，创建新节点
    LRUNode *newNode = (LRUNode*)malloc(sizeof(LRUNode));
    newNode->key = key;
    newNode->value = value;

    // 插入哈希表（头插法）
    newNode->next = cache->hashTable[idx];
    cache->hashTable[idx] = newNode;

    // 插入 LRU 链表头部
    newNode->prev = cache->head;
    newNode->next = cache->head->next;
    cache->head->next->prev = newNode;
    cache->head->next = newNode;

    cache->size++;

    // 如果超出容量，淘汰尾部
    if (cache->size > cache->capacity) {
        LRUNode *tailNode = removeTail(cache);
        if (tailNode) {
            int tailIdx = hashKey(tailNode->key, HASH_SIZE(cache->capacity));
            // 从哈希桶中删除
            LRUNode **pp = &cache->hashTable[tailIdx];
            while (*pp) {
                if (*pp == tailNode) {
                    *pp = tailNode->next;
                    break;
                }
                pp = &(*pp)->next;
            }
            free(tailNode);
            cache->size--;
        }
    }
}

这段代码看起来长，但逻辑很清晰：先查是否存在，存在就更新值并移到头部；不存在就新建节点，插入链表头部和哈希表。如果超容量，就淘汰尾部节点，同时从哈希表里删掉。

完整流程图

下面这张图展示了 LRU 缓存的核心流程，从 put 操作到淘汰的全过程：

性能分析与避坑

操作	时间复杂度	说明
get	O(1) 平均	哈希查找 + 链表移动
put（已存在）	O(1) 平均	更新值 + 移到头部
put（新插入）	O(1) 平均	插入 + 可能淘汰
淘汰	O(1)	删除尾部 + 哈希表删除

实际应用场景

LRU 在嵌入式系统里太常见了：

• 文件系统缓存：VFS 的 dentry 缓存、inode 缓存，都用 LRU 管理。
• 网络协议栈：ARP 缓存表、路由缓存，访问过的条目留在前面，不常用的被淘汰。
• 数据库缓冲池：MySQL 的 Buffer Pool 就用类 LRU 算法管理数据页。
• CPU 缓存：有些 CPU 的 L2 Cache 替换策略就是 LRU 的变种。

我记得有一次做车载信息娱乐系统，导航模块频繁读取地图数据，内存吃紧。用 LRU 缓存了最近访问的 200 个地图瓦片，切换地图时延迟从 800ms 降到了 50ms。嗯，这就是 LRU 的魅力——用有限的内存，换来最大的命中率。

好了，双向链表 + 哈希表的 LRU 实现就讲到这里。代码虽然不长，但每个细节都值得推敲。你可以在自己的项目里试试，把这段代码移植过去，稍微改改 key 和 value 的类型，就能用了。

---