第12章哈希表在缓存系统中的应用

课程目录第12章哈希表在缓存系统中的应用

12、哈希表在缓存系统中的应用：LRU缓存原理

说到哈希表在实际项目中的应用，缓存系统绝对是最经典的场景之一。我个人在早年做嵌入式开发时，就吃过不少没用好缓存的亏。今天咱们就来聊聊缓存系统中一个非常核心的算法——LRU（Least Recently Used，最近最少使用）。

你想想看，内存是有限的，但数据是无限的。当缓存满了，必须淘汰一些旧数据，腾出空间给新数据。那问题来了：该淘汰谁？

LRU 的思路很简单：如果数据最近被访问过，那么将来被访问的概率也更高。所以，淘汰那些最久没被访问的数据。

核心思想：LRU 缓存维护一个固定大小的容器，每次访问数据时，把该数据移到“最近使用”的位置。当容器满了，移除“最久未使用”的那个数据。

12.1 哈希表 + 双向链表实现 LRU

纯用数组或链表实现 LRU 其实不难，但效率是个大问题。比如用单链表，每次查找一个节点需要 O(n) 时间，这在缓存场景下是不可接受的。

那怎么办？哈希表 + 双向链表 这个组合拳，就是业界公认的标准解法。我当年第一次看到这个设计时，忍不住拍了一下大腿——太巧妙了。

具体来说：

哈希表：负责 O(1) 的查找。key 映射到链表节点。
双向链表：负责 O(1) 的插入和删除。节点按访问时间排序，头部是最近使用的，尾部是最久未使用的。

为什么用双向链表而不是单向？因为我们需要在 O(1) 时间内删除一个节点。单向链表删除节点需要知道前驱节点，而双向链表每个节点都保存了前驱指针，直接就能删。

我的经验：曾经有个项目，我一开始用了单向链表 + 哈希表，结果删除节点时还得遍历链表找前驱，性能直接崩了。后来改成双向链表，问题瞬间解决。这个坑我替你们踩过了。

12.2 数据结构定义

我们先定义双向链表的节点和 LRU Cache 的结构体：

// 双向链表节点
typedef struct DListNode {
    int key;                // 键
    int value;              // 值
    struct DListNode *prev; // 前驱指针
    struct DListNode *next; // 后继指针
} DListNode;

// LRU Cache 结构
typedef struct LRUCache {
    DListNode *head;        // 虚拟头节点（方便操作）
    DListNode *tail;        // 虚拟尾节点（方便操作）
    int capacity;           // 缓存容量
    int size;               // 当前大小
    DListNode **hashTable;  // 哈希表，存储 key -> 节点指针
} LRUCache;

这里我用了虚拟头尾节点，这是个很实用的小技巧。没有虚拟节点的话，每次插入删除都要判断边界条件，代码会变得很啰嗦。有了虚拟节点，所有操作都统一了。

12.3 核心操作实现

LRU Cache 需要实现三个核心操作：

创建缓存：初始化哈希表和双向链表
获取数据 get(key)：如果 key 存在，返回 value 并将节点移到头部；否则返回 -1
写入数据 put(key, value)：如果 key 存在，更新 value 并移到头部；如果不存在，插入到头部。如果容量满了，先删除尾部节点再插入

其中，将节点移到头部 这个操作可以拆解为两步：先从链表中删除该节点，再插入到头部。我们把它封装成一个函数：

// 从链表中移除一个节点
void removeNode(LRUCache *cache, DListNode *node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

// 将节点插入到头部（紧跟在虚拟头节点之后）
void addToHead(LRUCache *cache, DListNode *node) {
    node->prev = cache->head;
    node->next = cache->head->next;
    cache->head->next->prev = node;
    cache->head->next = node;
}

// 将节点移动到头部 = 移除 + 插入
void moveToHead(LRUCache *cache, DListNode *node) {
    removeNode(cache, node);
    addToHead(cache, node);
}

有了这些辅助函数，get 和 put 的实现就清晰多了：

int lruGet(LRUCache *cache, int key) {
    // 哈希表中查找
    DListNode *node = cache->hashTable[key];
    if (node == NULL) {
        return -1;  // 没找到
    }
    // 找到了，移到头部
    moveToHead(cache, node);
    return node->value;
}

void lruPut(LRUCache *cache, int key, int value) {
    DListNode *node = cache->hashTable[key];
    if (node != NULL) {
        // key 已存在，更新值并移到头部
        node->value = value;
        moveToHead(cache, node);
        return;
    }
    // key 不存在，创建新节点
    DListNode *newNode = (DListNode *)malloc(sizeof(DListNode));
    newNode->key = key;
    newNode->value = value;
    
    // 如果缓存满了，先淘汰尾部节点
    if (cache->size == cache->capacity) {
        DListNode *toRemove = cache->tail->prev; // 真正的最久未使用节点
        removeNode(cache, toRemove);
        cache->hashTable[toRemove->key] = NULL; // 从哈希表中移除
        free(toRemove);
        cache->size--;
    }
    
    // 插入新节点到头部
    addToHead(cache, newNode);
    cache->hashTable[key] = newNode;
    cache->size++;
}

注意：哈希表这里我用的是简单的数组实现，实际项目中建议用更完善的哈希表（比如链地址法）。另外，别忘了处理内存释放，否则会有内存泄漏。我曾经在一个线上服务中因为忘了 free 淘汰的节点，内存一路飙升，最后 OOM 了。

12.4 整体流程可视化

下面这张图展示了 LRU Cache 的核心工作流程。我特意画了哈希表和双向链表之间的对应关系，方便你理解它们是如何协同工作的。

12.5 实战：实现一个简单的 LRU Cache

好了，理论讲完了，咱们动手写一个完整的 LRU Cache。下面这个实现包含了初始化、销毁、get 和 put 四个接口。你可以直接拿去用，或者在此基础上扩展。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

// LRU Cache
typedef struct {
    DListNode *head;
    DListNode *tail;
    int capacity;
    int size;
    DListNode **hashTable;  // 简单哈希表，实际项目建议用链地址法
} LRUCache;

// 创建节点
DListNode* createNode(int key, int value) {
    DListNode *node = (DListNode *)malloc(sizeof(DListNode));
    node->key = key;
    node->value = value;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

// 初始化 LRU Cache
LRUCache* lruCreate(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;
    
    // 初始化哈希表（假设 key 范围 0-9999）
    cache->hashTable = (DListNode **)calloc(10000, sizeof(DListNode *));
    
    return cache;
}

// 移除节点
void removeNode(LRUCache *cache, DListNode *node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

// 插入到头部
void addToHead(LRUCache *cache, DListNode *node) {
    node->prev = cache->head;
    node->next = cache->head->next;
    cache->head->next->prev = node;
    cache->head->next = node;
}

// 移动到头部
void moveToHead(LRUCache *cache, DListNode *node) {
    removeNode(cache, node);
    addToHead(cache, node);
}

// 获取值
int lruGet(LRUCache *cache, int key) {
    DListNode *node = cache->hashTable[key];
    if (node == NULL) {
        return -1;
    }
    moveToHead(cache, node);
    return node->value;
}

// 写入值
void lruPut(LRUCache *cache, int key, int value) {
    DListNode *node = cache->hashTable[key];
    if (node != NULL) {
        node->value = value;
        moveToHead(cache, node);
        return;
    }
    
    DListNode *newNode = createNode(key, value);
    
    if (cache->size == cache->capacity) {
        // 淘汰尾部节点
        DListNode *toRemove = cache->tail->prev;
        removeNode(cache, toRemove);
        cache->hashTable[toRemove->key] = NULL;
        free(toRemove);
        cache->size--;
    }
    
    addToHead(cache, newNode);
    cache->hashTable[key] = newNode;
    cache->size++;
}

// 销毁缓存
void lruFree(LRUCache *cache) {
    DListNode *cur = cache->head->next;
    while (cur != cache->tail) {
        DListNode *tmp = cur;
        cur = cur->next;
        free(tmp);
    }
    free(cache->head);
    free(cache->tail);
    free(cache->hashTable);
    free(cache);
}

// 测试代码
int main() {
    LRUCache *cache = lruCreate(3);
    
    lruPut(cache, 1, 10);
    lruPut(cache, 2, 20);
    lruPut(cache, 3, 30);
    
    printf("get(1) = %d\n", lruGet(cache, 1)); // 10
    printf("get(2) = %d\n", lruGet(cache, 2)); // 20
    
    lruPut(cache, 4, 40); // 淘汰 key=3
    
    printf("get(3) = %d\n", lruGet(cache, 3)); // -1（已被淘汰）
    printf("get(4) = %d\n", lruGet(cache, 4)); // 40
    
    lruFree(cache);
    return 0;
}

避坑指南：我曾经在实现 LRU 时犯过一个低级错误——在 moveToHead 之后忘记更新哈希表。结果 get 操作返回了旧值，排查了半天才发现。记住：哈希表和链表必须保持同步，这是 LRU 实现中最容易出错的地方。

12.6 复杂度分析

操作	时间复杂度	空间复杂度
get(key)	O(1)	O(1)
put(key, value)	O(1)	O(1)
整体空间	—	O(capacity)

说白了，哈希表保证了查找是 O(1)，双向链表保证了插入和删除也是 O(1)。这两个数据结构一结合，LRU 的所有操作都是常数时间。这也是为什么这个方案能成为工业级标准。

嗯，LRU 缓存的内容就讲到这里。这个算法在 Redis、Memcached、操作系统页面置换等场景中都有广泛应用。你如果能把上面这份代码吃透，面试中遇到 LRU 相关的问题基本就稳了。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录

12、哈希表在缓存系统中的应用：LRU缓存原理

12.1 哈希表 + 双向链表实现 LRU

12.2 数据结构定义

12.3 核心操作实现

12.4 整体流程可视化

12.5 实战：实现一个简单的 LRU Cache

12.6 复杂度分析