20、哈希表的内存管理：内存池设计、节点复用、内存碎片控制、valgrind内存检测

哈希表跑得快不快，除了哈希函数好不好，还有一个关键因素——内存管理。我见过不少项目，哈希函数写得漂亮，但频繁 malloc/free 导致性能雪崩，甚至内存泄漏查都查不出来。说白了，哈希表的内存管理，是决定它能不能上生产环境的最后一道坎。

这一章，我们就来聊聊怎么把内存管好。我会从内存池设计讲起，再到节点复用、碎片控制，最后用 valgrind 做一次完整的内存检测。嗯，都是我在实际项目中踩过的坑，希望能帮你少走弯路。

20.1 为什么需要内存池？

先问一个问题：哈希表里每个节点都单独 malloc，会有什么后果？

我举个例子。假设你的哈希表要插入 100 万个键值对，每个节点 malloc 一次，那就是 100 万次系统调用。每次 malloc 还要带上内存对齐、元信息开销，平均一次可能浪费 16~32 字节。100 万次下来，光浪费的内存就几十 MB。更可怕的是，频繁分配释放会导致内存碎片——明明还有空闲内存，但连续的大块内存已经找不到了。

所以，内存池的核心思路就是：一次性申请一大块内存，然后自己管理分配和回收。这样既减少了系统调用次数，又能有效控制碎片。

20.2 内存池设计：从零开始

我个人习惯把内存池设计成「固定大小块」的分配器。因为哈希表的节点结构是固定的——每个节点包含 key、value、next 指针，大小完全一致。这正好适合固定块内存池。

下面是一个简单的内存池结构：

// 内存池节点
typedef struct MemPoolNode {
    void *block;                // 指向一大块连续内存
    size_t block_size;          // 这块内存的大小
    size_t used;                // 已使用字节数
    struct MemPoolNode *next;   // 指向下一个内存块
} MemPoolNode;

// 内存池
typedef struct {
    MemPoolNode *head;          // 当前使用的内存块
    size_t node_size;           // 每个节点的大小（固定）
    void *free_list;            // 空闲节点链表（复用用）
} MemPool;

这里有个关键设计：free_list。它用来存放被释放的节点，实现节点复用。后面会详细讲。

分配函数也很直接：

void *mem_pool_alloc(MemPool *pool) {
    // 先检查空闲链表
    if (pool->free_list) {
        void *ptr = pool->free_list;
        pool->free_list = *(void **)ptr;  // 空闲链表是单向链表
        return ptr;
    }

    // 当前块不够了，申请新块
    if (pool->head == NULL || 
        pool->head->used + pool->node_size > pool->head->block_size) {
        MemPoolNode *new_node = malloc(sizeof(MemPoolNode));
        new_node->block = malloc(BLOCK_SIZE);  // BLOCK_SIZE 比如 64KB
        new_node->block_size = BLOCK_SIZE;
        new_node->used = 0;
        new_node->next = pool->head;
        pool->head = new_node;
    }

    void *ptr = (char *)pool->head->block + pool->head->used;
    pool->head->used += pool->node_size;
    return ptr;
}

20.3 节点复用：让释放的内存「活」起来

哈希表经常有删除操作。如果删掉的节点直接 free 掉，那内存池的优势就没了。更好的做法是：把删掉的节点放回空闲链表，下次分配时优先复用。

释放函数实现：

void mem_pool_free(MemPool *pool, void *ptr) {
    // 把 ptr 插入到空闲链表头部
    *(void **)ptr = pool->free_list;
    pool->free_list = ptr;
}

你看，这里有个巧妙的地方：*(void **)ptr = pool->free_list。因为节点本身的内存已经不用了，我们直接用它来存储下一个空闲节点的指针。这样不需要额外空间，就维护了一个单向链表。

我在项目中遇到过一个问题：如果节点里包含指向其他资源的指针（比如动态分配的 key 字符串），释放节点前必须先释放那些资源，否则就泄漏了。所以，mem_pool_free 只适合释放节点本身，外部资源要单独处理。

20.4 内存碎片控制：从源头抓起

内存碎片分两种：外部碎片和内部碎片。

• 外部碎片：频繁分配释放导致内存被切成很多小块，无法满足大块分配请求。
• 内部碎片：分配的内存比实际需要的大，比如你只要 30 字节，但 malloc 给了 48 字节（对齐后）。

内存池对这两种碎片都有抑制作用：

• 一次性申请大块内存，外部碎片基本不存在（因为大块内部自己管理）。
• 固定大小分配，内部碎片最多浪费一个节点大小（对齐后）。

但有一个坑：如果哈希表扩容了，旧的内存池怎么办？

我建议的做法是：扩容时创建新的内存池，旧的内存池不释放，等哈希表缩容或销毁时再统一释放。这样避免了扩容时的大量内存拷贝和碎片。

// 哈希表扩容时
void hash_table_resize(HashTable *table, size_t new_capacity) {
    // 创建新内存池
    MemPool *new_pool = mem_pool_create(sizeof(HashNode));
    
    // 重新哈希所有节点到新表
    // ... 这里省略具体逻辑
    
    // 旧内存池保留，等缩容或销毁时释放
    // 注意：不能直接 free 旧池，因为节点指针还在用
}

20.5 Valgrind 内存检测：别让泄漏「潜伏」

写完了内存池，怎么验证它没问题？valgrind 是必备工具。我每次提交代码前，都会跑一遍 valgrind，确保没有泄漏和越界。

基本用法：

gcc -g -o hash_table hash_table.c
valgrind --leak-check=full --show-leak-kinds=all ./hash_table

valgrind 会输出类似这样的信息：

==12345== HEAP SUMMARY:
==12345==     in use at exit: 0 bytes in 0 blocks
==12345==     total heap usage: 10 allocs, 10 frees, 1,048,576 bytes allocated
==12345== 
==12345== All heap blocks were freed -- no leaks are possible

看到「no leaks are possible」就放心了。但如果内存池设计不当，可能会出现「still reachable」的警告——意思是内存没释放，但指针还保留着。这通常是因为内存池的底层大块内存没有在程序退出时释放。

解决办法：在哈希表销毁时，遍历所有内存块并释放：

void mem_pool_destroy(MemPool *pool) {
    MemPoolNode *cur = pool->head;
    while (cur) {
        MemPoolNode *next = cur->next;
        free(cur->block);
        free(cur);
        cur = next;
    }
    pool->head = NULL;
    pool->free_list = NULL;
}

20.6 本章小结

哈希表的内存管理，说白了就是三件事：

• 内存池：减少 malloc 次数，提升分配效率。
• 节点复用：让释放的内存「活」起来，避免频繁分配。
• 碎片控制：从设计上避免外部碎片和内部碎片。

最后，别忘了用 valgrind 做一次完整检测。内存泄漏这种东西，越早发现越好。等上了生产环境再查，那可就头疼了。

嗯，这一章就到这里。下一章我们会聊聊哈希表的并发访问——那又是一个全新的世界。