第30章：哈希表项目实战——从零构建一个完整的哈希表库

终于到了最后一章。说实话，前面讲了那么多理论、原理、冲突处理、扩容策略，如果不亲手写一个完整的库，总觉得少了点什么。这一章，我们就来干这件事——把哈希表从理论变成可用的代码库。

我个人习惯，写库之前先想清楚三件事：接口怎么设计？测试怎么覆盖？性能怎么保证？咱们一个一个来。

30.1 库的整体设计

先画个图，看看这个库长什么样。

三层架构，各司其职。用户只管调用接口，不用关心底层怎么存。这就是封装的好处。

30.2 接口设计

先定义头文件。我习惯把类型定义和函数声明分开，这样看起来清爽。

/* hashtable.h */
#ifndef HASHTABLE_H
#define HASHTABLE_H

#include <stddef.h>  /* size_t */
#include <stdbool.h> /* bool   */

/* 哈希表节点 */
typedef struct ht_node {
    char       *key;      /* 键（字符串） */
    void       *value;    /* 值（泛型指针） */
    struct ht_node *next; /* 冲突链指针 */
} ht_node_t;

/* 哈希表主结构 */
typedef struct {
    ht_node_t **buckets;  /* 桶数组 */
    size_t      size;     /* 当前元素个数 */
    size_t      capacity; /* 桶的数量 */
    float       load_factor; /* 负载因子阈值 */
} hashtable_t;

/* 创建哈希表 */
hashtable_t *ht_create(size_t capacity, float load_factor);

/* 插入键值对 */
bool ht_insert(hashtable_t *ht, const char *key, void *value);

/* 查找键对应的值 */
void *ht_search(hashtable_t *ht, const char *key);

/* 删除键值对 */
bool ht_delete(hashtable_t *ht, const char *key);

/* 销毁哈希表 */
void ht_destroy(hashtable_t *ht);

#endif /* HASHTABLE_H */

嗯，这里要注意：value 用 void*，意味着你可以存任何类型的数据。但这也意味着调用者要自己管理内存——我当年第一次写泛型容器时就踩过这个坑，以为库能帮我释放所有内存，结果内存泄漏查了一整天。

30.3 核心实现

咱们挑几个关键函数说说。

30.3.1 哈希函数

字符串哈希，我推荐 djb2 算法。简单、分布均匀、速度也快。

static unsigned long hash_djb2(const char *str) {
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    }
    return hash;
}

为什么选 5381 和 33？说实话，这是经验值。Dan Bernstein 当年测试了很多组合，发现这个效果最好。我在项目中直接拿来用，从来没出过问题。

30.3.2 插入与扩容

插入的逻辑不复杂：计算哈希 -> 找到桶 -> 遍历链表 -> 插入或更新。但有个关键点——扩容。

bool ht_insert(hashtable_t *ht, const char *key, void *value) {
    if (ht == NULL || key == NULL) return false;

    /* 检查负载因子，决定是否扩容 */
    if ((float)ht->size / ht->capacity >= ht->load_factor) {
        if (!ht_resize(ht, ht->capacity * 2)) {
            return false; /* 扩容失败 */
        }
    }

    unsigned long idx = hash_djb2(key) % ht->capacity;
    ht_node_t *node = ht->buckets[idx];

    /* 查找是否已存在 */
    while (node) {
        if (strcmp(node->key, key) == 0) {
            node->value = value; /* 更新值 */
            return true;
        }
        node = node->next;
    }

    /* 头插法插入新节点 */
    ht_node_t *new_node = malloc(sizeof(ht_node_t));
    if (!new_node) return false;

    new_node->key   = strdup(key);
    new_node->value = value;
    new_node->next  = ht->buckets[idx];
    ht->buckets[idx] = new_node;
    ht->size++;

    return true;
}

扩容函数 ht_resize 要做三件事：申请新桶数组、重新哈希所有旧节点、释放旧数组。这里有个性能陷阱——如果一次扩容的数据量很大，会卡住。我曾经在线上服务里遇到过，扩容时请求超时，后来改成渐进式扩容才解决。

30.3.3 查找与删除

查找很简单，哈希定位然后链表遍历。删除稍微麻烦点，要处理链表节点的摘除。

bool ht_delete(hashtable_t *ht, const char *key) {
    unsigned long idx = hash_djb2(key) % ht->capacity;
    ht_node_t *node = ht->buckets[idx];
    ht_node_t *prev = NULL;

    while (node) {
        if (strcmp(node->key, key) == 0) {
            if (prev) {
                prev->next = node->next;
            } else {
                ht->buckets[idx] = node->next;
            }
            free(node->key);
            free(node);
            ht->size--;
            return true;
        }
        prev = node;
        node = node->next;
    }
    return false; /* 没找到 */
}

注意：删除时只释放了 key 和节点本身，value 由调用者负责。这是设计上的取舍——库不知道 value 是怎么分配的。

30.4 测试用例

写测试，我习惯分三步走：基本功能测试、边界测试、压力测试。

测试类型	测试内容	预期结果
基本功能	插入10个键值对，逐个查找	全部找到，值正确
重复键	插入相同key两次，值不同	第二次覆盖第一次的值
删除操作	插入后删除，再查找	查找返回NULL
扩容触发	插入超过负载因子的元素数	桶数量翻倍，所有元素可查
空表操作	对空表执行查找、删除	返回false或NULL，不崩溃
大量数据	插入100万条记录	耗时在可接受范围内

写测试代码时，我建议用断言 assert，简单直接。如果项目大，可以考虑用 CUnit 或 Check 这类测试框架。

30.5 性能调优

性能调优，说白了就是找瓶颈。我一般用 perf 或 gprof 做 profiling。常见的优化点有：

• 哈希函数：djb2 已经很快了，但如果 key 很长，可以考虑只取前几个字符做哈希。
• 负载因子：默认 0.75 是个好选择。调高了节省内存但冲突多，调低了浪费内存但速度快。
• 内存分配：频繁 malloc/free 是性能杀手。可以考虑内存池，预分配一批节点。
• 缓存友好：链地址法天然对缓存不友好。如果数据量不大，可以考虑开放地址法+线性探测。

30.6 文档编写

文档怎么写？我有个原则：告诉用户怎么用，也告诉维护者怎么改。

一份好的哈希表库文档应该包含：

• 快速开始：一个完整的示例，从创建到销毁。
• API 参考：每个函数的参数、返回值、注意事项。
• 性能说明：时间复杂度、内存占用、推荐使用场景。
• 常见问题：比如线程安全吗？value 的内存谁管？

我个人习惯用 Doxygen 生成文档，注释写好了，文档自动生成，省心。

30.7 项目总结

回顾整个哈希表项目，我们做了这些事：

1. 从零设计了一个泛型哈希表库的接口
2. 实现了核心的插入、查找、删除、扩容逻辑
3. 编写了覆盖基本功能和边界情况的测试用例
4. 做了性能分析和调优
5. 编写了用户文档

说实话，写一个能用的哈希表不难，但写一个好用的哈希表库，需要考虑很多细节。比如错误处理是否完整？内存管理是否清晰？接口是否直观？这些都是在实际项目中慢慢积累的经验。

最后，我想说：不要怕自己写轮子。虽然 C 语言有很多现成的哈希表库（如 uthash），但自己动手写一遍，你对内存管理、算法设计、接口抽象的理解会深很多。下次面试被问到哈希表，你不仅能说出原理，还能说出实现中的坑——这就是实战的价值。

---

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