53、哈希表：如何用 C 实现一个简单的哈希表？

哈希表，说白了就是「用空间换时间」的典型代表。你想想看，数组查找是 O(1)，但插入删除麻烦；链表插入删除快，但查找是 O(n)。哈希表呢？它把这两者的优点结合起来了——通过一个哈希函数，把 key 映射到数组的某个位置，然后在这个位置上挂一个链表处理冲突。

我刚开始学哈希表的时候，总觉得这东西很玄乎。后来在嵌入式项目里做配置参数缓存，才真正体会到它的威力。嗯，今天我们就手撸一个最简单的哈希表，把核心逻辑讲透。

哈希表的核心结构

一个哈希表，本质上就是一个「数组 + 链表」的组合。数组用来快速定位，链表用来解决哈希冲突（也就是不同的 key 算出了同一个下标）。

我个人习惯这样定义节点和表结构：

// 哈希表节点
typedef struct HashNode {
    char *key;
    int value;
    struct HashNode *next;
} HashNode;

// 哈希表本体
typedef struct {
    HashNode **buckets;  // 桶数组，每个元素是一个链表头指针
    int size;            // 桶的数量
    int count;           // 当前存储的元素个数
} HashTable;

这里有个细节：buckets 是一个二级指针，指向一个指针数组。每个数组元素又是一个链表的头指针。为什么要用二级指针？因为我们要动态分配桶数组的大小。

哈希函数：选对了一半

哈希函数的质量，直接决定了你的表性能好不好。如果哈希函数把所有的 key 都映射到同一个桶里，那哈希表就退化成了链表——查找 O(n)，还不如直接用数组。

我常用的一个简单哈希函数是这样的：

unsigned int hash(const char *key, int table_size) {
    unsigned int h = 0;
    while (*key) {
        h = (h << 5) + *key++;  // 相当于乘以 32 再加当前字符
    }
    return h % table_size;
}

这个算法叫「DJB2 变种」，实际效果还不错。为什么用左移 5 位？因为乘以 32 比直接乘 31 快，而且能更好地打散数据。我在项目中测试过，对于字符串 key，这个函数的冲突率比简单的累加求模低很多。

核心操作：插入、查找、删除

有了结构和哈希函数，剩下的就是三个基本操作。我们一个一个来看。

1. 插入

void ht_insert(HashTable *ht, const char *key, int value) {
    unsigned int index = hash(key, ht->size);
    HashNode *node = ht->buckets[index];

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

    // 不存在则创建新节点，头插法
    HashNode *new_node = (HashNode *)malloc(sizeof(HashNode));
    new_node->key = strdup(key);  // 注意：要复制字符串，不能直接赋值
    new_node->value = value;
    new_node->next = ht->buckets[index];
    ht->buckets[index] = new_node;
    ht->count++;
}

这里有个坑：strdup 不是标准 C 函数，但在 POSIX 系统上都有。如果你在嵌入式环境里没有这个函数，自己写一个也不难——就是 malloc + strcpy。

2. 查找

int ht_find(HashTable *ht, const char *key) {
    unsigned int index = hash(key, ht->size);
    HashNode *node = ht->buckets[index];

    while (node) {
        if (strcmp(node->key, key) == 0) {
            return node->value;
        }
        node = node->next;
    }
    return -1;  // 没找到，返回一个特殊值
}

查找的逻辑很简单：算哈希 -> 定位桶 -> 遍历链表。时间复杂度取决于链表的长度。如果哈希函数设计得好，每个桶里的节点数应该接近 count / size，也就是平均 O(1)。

3. 删除

void ht_delete(HashTable *ht, const char *key) {
    unsigned int index = hash(key, ht->size);
    HashNode *node = ht->buckets[index];
    HashNode *prev = NULL;

    while (node) {
        if (strcmp(node->key, key) == 0) {
            if (prev) {
                prev->next = node->next;
            } else {
                ht->buckets[index] = node->next;
            }
            free(node->key);
            free(node);
            ht->count--;
            return;
        }
        prev = node;
        node = node->next;
    }
}

删除要维护链表的前驱指针，这是链表操作的基本功。嗯，这里要注意：free(node->key) 别忘了，因为 key 是用 strdup 分配的，不释放就会内存泄漏。

哈希表的完整生命周期

除了增删查，我们还需要创建和销毁：

HashTable *ht_create(int size) {
    HashTable *ht = (HashTable *)malloc(sizeof(HashTable));
    ht->size = size;
    ht->count = 0;
    ht->buckets = (HashNode **)calloc(size, sizeof(HashNode *));
    return ht;
}

void ht_destroy(HashTable *ht) {
    for (int i = 0; i < ht->size; i++) {
        HashNode *node = ht->buckets[i];
        while (node) {
            HashNode *tmp = node;
            node = node->next;
            free(tmp->key);
            free(tmp);
        }
    }
    free(ht->buckets);
    free(ht);
}

销毁时一定要遍历所有桶，释放每个节点。我曾经见过有人只释放了桶数组，没释放链表节点——结果内存泄漏得一塌糊涂。

哈希表的核心逻辑图

下面这张图展示了哈希表的核心工作流程：

哈希表的性能关键

哈希表的性能，说白了就三个因素：

负载因子超过 0.7 时，冲突会急剧增加。这时候就需要「rehash」——重新分配一个更大的桶数组，把所有元素重新插入。rehash 的代价是 O(n)，但可以分摊到每次插入中，这就是「均摊分析」的思想。

避坑指南

最后，分享几个我踩过的坑：

• 字符串 key 的内存管理： 插入时一定要复制字符串，不要直接保存传入的指针。因为调用方可能释放或修改那个字符串。
• 哈希函数不要用简单的累加： 比如 return key[0] + key[1] + key[2]，这种函数会把 "abc" 和 "cba" 映射到同一个位置，冲突率极高。
• 删除后记得释放内存： 嵌入式系统内存有限，泄漏一点就可能出问题。
• 线程安全： 上面的实现不是线程安全的。多线程环境下需要加锁，或者使用无锁哈希表。

嗯，哈希表的内容就讲到这里。代码虽然简单，但核心思想都在里面了。你可以在自己的项目里试试，把配置参数、设备状态这些用哈希表来管理，效果会很不错。

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