深入理解C语言哈希函数（从零开始构建高效哈希表）

设计一个简单的哈希函数

最经典的字符串哈希函数之一是 djb2，由 Daniel J. Bernstein 提出。它简单、快速且分布均匀。下面是我们用 C 语言实现的版本：

// djb2 哈希函数实现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 开始，对字符串中的每个字符进行位运算和加法操作，最终返回一个无符号长整型哈希值。

构建哈希表（Hash Table）

有了哈希函数，我们就可以构建一个完整的哈希表。哈希表通常由一个数组组成，每个数组元素（称为“桶”）可以存储一个或多个键值对。为了简化，我们使用链地址法（Chaining）来处理 哈希冲突处理 ——即不同键产生相同哈希值的情况。

首先定义数据结构：

// 键值对节点typedef struct Node {    char *key;    int value;    struct Node *next;} Node;// 哈希表结构#define TABLE_SIZE 100Node *hash_table[TABLE_SIZE] = {NULL};

接下来是插入和查找函数：

// 插入键值对void insert(const char *key, int value) {    unsigned long index = hash_djb2(key) % TABLE_SIZE;        Node *new_node = (Node*)malloc(sizeof(Node));    new_node->key = strdup(key);    new_node->value = value;    new_node->next = hash_table[index];    hash_table[index] = new_node;}// 查找值int get(const char *key) {    unsigned long index = hash_djb2(key) % TABLE_SIZE;    Node *current = hash_table[index];        while (current != NULL) {        if (strcmp(current->key, key) == 0) {            return current->value;        }        current = current->next;    }        // 未找到    return -1;}

完整示例与测试

下面是一个完整的可运行示例，展示了如何使用上述代码：

#include <stdio.h>#include <stdlib.h>#include <string.h>// 此处插入上面定义的 hash_djb2、Node、hash_table、insert、get 函数int main() {    insert("apple", 10);    insert("banana", 20);    insert("cherry", 30);        printf("apple: %d\n", get("apple"));     // 输出 10    printf("banana: %d\n", get("banana"));   // 输出 20    printf("orange: %d\n", get("orange"));   // 输出 -1（未找到）        return 0;}

为什么学习 C语言数据结构 中的哈希表很重要？

掌握 C语言数据结构 中的哈希表不仅有助于理解底层内存管理，还能提升你在算法竞赛、系统编程和嵌入式开发中的能力。哈希表是面试高频考点，也是许多高级数据结构（如布隆过滤器、一致性哈希）的基础。

总结

通过本教程，你已经学会了：

• 什么是 C语言哈希函数 及其作用
• 如何实现一个高效的 djb2 哈希函数
• 如何用链地址法构建哈希表并处理哈希冲突
• 完整的插入与查找操作代码

希望这篇教程能帮助你打下坚实的 哈希表实现 基础。动手写一写代码，你会理解得更深刻！