C语言哈希算法详解（从零开始实现哈希表）

核心概念：哈希函数

哈希函数是哈希表的核心。一个好的哈希函数应具备以下特点：

• 计算速度快
• 分布均匀（减少冲突）
• 确定性（相同输入始终得到相同输出）

在本教程中，我们将使用最简单的除法取余法作为哈希函数：

unsigned int hash(const char* key, int table_size) {    unsigned int hash_value = 0;    while (*key) {        hash_value = (hash_value * 31 + *key);        key++;    }    return hash_value % table_size;}

处理冲突：链地址法

当两个不同的键通过哈希函数得到相同的下标时，就发生了哈希冲突。我们采用链地址法（Chaining）来解决：每个数组元素是一个链表，所有哈希到同一位置的元素都存入该链表。

完整C语言实现

下面是一个完整的、可运行的 C 语言哈希表实现，包含插入、查找和打印功能。

#include <stdio.h>#include <stdlib.h>#include <string.h>// 定义哈希表大小#define TABLE_SIZE 10// 链表节点结构typedef struct Node {    char* key;    int value;    struct Node* next;} Node;// 哈希表结构typedef struct {    Node* buckets[TABLE_SIZE];} HashTable;// 哈希函数unsigned int hash(const char* key) {    unsigned int hash_value = 0;    while (*key) {        hash_value = (hash_value * 31 + *key);        key++;    }    return hash_value % TABLE_SIZE;}// 创建新节点Node* create_node(const char* key, int value) {    Node* new_node = (Node*)malloc(sizeof(Node));    new_node->key = strdup(key);    new_node->value = value;    new_node->next = NULL;    return new_node;}// 初始化哈希表HashTable* create_hash_table() {    HashTable* table = (HashTable*)malloc(sizeof(HashTable));    for (int i = 0; i < TABLE_SIZE; i++) {        table->buckets[i] = NULL;    }    return table;}// 插入键值对void insert(HashTable* table, const char* key, int value) {    unsigned int index = hash(key);    Node* head = table->buckets[index];    // 检查是否已存在该键    while (head != NULL) {        if (strcmp(head->key, key) == 0) {            head->value = value; // 更新值            return;        }        head = head->next;    }    // 插入新节点到链表头部    Node* new_node = create_node(key, value);    new_node->next = table->buckets[index];    table->buckets[index] = new_node;}// 查找键对应的值int search(HashTable* table, const char* key) {    unsigned int index = hash(key);    Node* head = table->buckets[index];    while (head != NULL) {        if (strcmp(head->key, key) == 0) {            return head->value;        }        head = head->next;    }    return -1; // 未找到}// 打印整个哈希表void print_table(HashTable* table) {    for (int i = 0; i < TABLE_SIZE; i++) {        printf("Bucket %d: ", i);        Node* head = table->buckets[i];        while (head != NULL) {            printf("(%s, %d) -> ", head->key, head->value);            head = head->next;        }        printf("NULL\n");    }}// 主函数测试int main() {    HashTable* table = create_hash_table();    insert(table, "apple", 10);    insert(table, "banana", 20);    insert(table, "orange", 30);    insert(table, "grape", 40);    printf("Search 'banana': %d\n", search(table, "banana"));    printf("Search 'kiwi': %d\n", search(table, "kiwi"));    printf("\nFull Hash Table:\n");    print_table(table);    return 0;}

编译与运行

将上述代码保存为 hash_table.c，然后在终端执行：

gcc hash_table.c -o hash_table./hash_table

你将看到类似如下的输出：

Search 'banana': 20Search 'kiwi': -1Full Hash Table:Bucket 0: (grape, 40) -> NULLBucket 1: NULLBucket 2: (orange, 30) -> NULLBucket 3: NULLBucket 4: NULLBucket 5: (apple, 10) -> NULLBucket 6: NULLBucket 7: NULLBucket 8: (banana, 20) -> NULLBucket 9: NULL

总结

通过本教程，你已经掌握了如何用C语言实现哈希表，包括哈希函数设计、冲突处理以及基本操作。这是学习更高级C语言数据结构的重要一步。掌握这些知识后，你可以进一步优化哈希函数、实现动态扩容，甚至探索更复杂的哈希算法如一致性哈希。

记住，哈希算法不仅是面试常考内容，更是实际工程中提升程序性能的关键技术。希望这篇哈希函数教程能为你打下坚实基础！