24. 结构体与哈希表：链地址法实现、结构体作为哈希节点

哈希表，说白了就是“用空间换时间”的典型代表。你想想看，如果我们要在一个大数组里找一个元素，最坏情况得遍历整个数组——O(n)的复杂度，数据量一上来就扛不住了。哈希表能把这个降到O(1)，前提是哈希函数设计得好。

我个人习惯用链地址法来处理哈希冲突。为什么？因为简单、可靠，而且用结构体做节点非常自然。今天我们就来手撕一个链地址法的哈希表，看看结构体是怎么在里边扮演核心角色的。

24.1 哈希表的核心思想

哈希表的基本思路是这样的：

• 有一个固定大小的数组（桶数组）
• 通过哈希函数把key映射到某个桶的下标
• 如果多个key映射到同一个桶，就用链表把它们串起来

这个链表上的每个节点，就是一个结构体。嗯，这里要注意：节点里既要存key，也要存value，还得有个next指针指向下一个节点。

24.2 结构体作为哈希节点

我们先定义节点结构体。我在项目中遇到过不少新手把key和value混在一起，搞得后面查找时很痛苦。我的建议是：key和value分开存，哪怕key是整数，value是字符串，也要明确区分。

// 哈希节点结构体
typedef struct HashNode {
    int key;                // 键
    char value[64];         // 值（假设是字符串）
    struct HashNode *next;  // 链表指针
} HashNode;

这个结构体就是链地址法的基本单元。每个节点既是一个数据容器，又是链表的一部分。说白了，它身兼两职。

24.3 哈希表结构体定义

有了节点，我们还需要一个“桶数组”来管理这些节点。桶数组本身也是一个结构体数组，或者更准确地说，是一个指针数组——每个元素指向一个链表的头节点。

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

这里buckets是一个二级指针，因为它指向一个指针数组。每个buckets[i]要么是NULL（空桶），要么指向一个链表的头节点。

24.4 哈希函数

哈希函数的好坏直接影响性能。我常用的一个简单哈希函数是这样写的：

// 哈希函数：取模法
int hash(int key, int size) {
    return key % size;
}

取模法虽然简单，但有个坑：如果size是2的幂，比如16、32，那么key % size等价于key & (size-1)，速度更快。但这样会导致哈希分布不均匀，尤其是key本身有规律的时候。我曾经踩过这个坑——用16个桶，key全是4的倍数，结果所有元素都挤在0、4、8、12这四个桶里，其他桶全空着。性能直接退化成链表。

24.5 链地址法实现：插入操作

插入操作的逻辑很清晰：

1. 计算key的哈希值，得到桶下标
2. 遍历该桶的链表，检查key是否已存在
3. 如果存在，更新value
4. 如果不存在，在链表头部插入新节点

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

    // 检查key是否已存在
    while (cur != NULL) {
        if (cur->key == key) {
            strcpy(cur->value, value);  // 更新值
            return;
        }
        cur = cur->next;
    }

    // 创建新节点，头插法
    HashNode *new_node = (HashNode *)malloc(sizeof(HashNode));
    new_node->key = key;
    strcpy(new_node->value, value);
    new_node->next = ht->buckets[index];
    ht->buckets[index] = new_node;
    ht->count++;
}

为什么用头插法？因为简单、快。你想想看，新节点插在头部，不需要遍历到链表尾部，时间复杂度O(1)。

24.6 链地址法实现：查找操作

查找就更容易了：

char *hash_find(HashTable *ht, int key) {
    int index = hash(key, ht->size);
    HashNode *cur = ht->buckets[index];

    while (cur != NULL) {
        if (cur->key == key) {
            return cur->value;
        }
        cur = cur->next;
    }
    return NULL;  // 没找到
}

这个函数返回的是指向节点内部value的指针。注意：外部不要直接修改这个字符串，否则可能破坏哈希表内部结构。如果外部需要修改，应该调用插入接口。

24.7 链地址法实现：删除操作

删除稍微麻烦一点，因为要处理链表节点的摘除。我习惯用双指针法：

int hash_delete(HashTable *ht, int key) {
    int index = hash(key, ht->size);
    HashNode *cur = ht->buckets[index];
    HashNode *prev = NULL;

    while (cur != NULL) {
        if (cur->key == key) {
            if (prev == NULL) {
                // 删除的是头节点
                ht->buckets[index] = cur->next;
            } else {
                prev->next = cur->next;
            }
            free(cur);
            ht->count--;
            return 1;  // 删除成功
        }
        prev = cur;
        cur = cur->next;
    }
    return 0;  // 没找到
}

这里prev指针始终指向cur的前一个节点。删除时，只需要把prev->next指向cur->next，然后free掉cur即可。注意头节点的特殊情况。

24.8 哈希表的初始化与销毁

初始化要分配桶数组，并把每个桶置为NULL：

HashTable *hash_create(int size) {
    HashTable *ht = (HashTable *)malloc(sizeof(HashTable));
    ht->size = size;
    ht->count = 0;
    ht->buckets = (HashNode **)calloc(size, sizeof(HashNode *));
    // calloc会自动把每个指针初始化为NULL
    return ht;
}

销毁时要遍历每个桶的链表，逐个释放节点：

void hash_destroy(HashTable *ht) {
    for (int i = 0; i < ht->size; i++) {
        HashNode *cur = ht->buckets[i];
        while (cur != NULL) {
            HashNode *tmp = cur;
            cur = cur->next;
            free(tmp);
        }
    }
    free(ht->buckets);
    free(ht);
}

这里有个细节：先释放所有节点，再释放桶数组，最后释放哈希表本身。顺序不能乱，否则会造成内存泄漏。

24.9 链地址法的性能分析

链地址法的性能取决于两个因素：哈希函数的均匀性和负载因子。

负载因子	平均查找长度	说明
0.5	1.25	性能很好，但浪费空间
0.75	1.38	Java HashMap的默认阈值
1.0	1.50	空间利用率高，性能尚可
2.0	2.00	性能下降明显，建议扩容

负载因子 = 元素个数 / 桶数量。我一般控制在0.75左右，超过就扩容。扩容时要重新哈希所有元素，这是个O(n)操作，但均摊下来成本不高。

24.10 链地址法的优缺点

• 优点：实现简单，删除方便，对哈希函数要求不高
• 缺点：需要额外的指针存储空间，缓存不友好（链表节点在内存中不连续）

如果你对性能要求极高，可以考虑开放地址法（比如线性探测）。但链地址法胜在稳定，不容易出幺蛾子。我在嵌入式项目里基本都用链地址法，因为嵌入式环境下的内存分配器通常对小块内存管理得很好。

24.11 知识体系图

下面这张图展示了本章的核心逻辑：

从图中可以看到，buckets数组的每个元素要么指向一个链表，要么是NULL。链表中的每个节点都是一个结构体，包含key、value和next指针。这就是链地址法的全部秘密。

好了，链地址法哈希表的核心内容就这些。结构体在这里扮演了节点的角色，而哈希表本身也是一个结构体。说白了，C语言里一切复杂数据结构，最终都是结构体的组合。你想想看，是不是这个道理？

---

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