C语言哈希表入门详解（从零开始掌握C语言哈希表的实现与应用）

哈希函数的作用

哈希函数是哈希表的核心。它的作用是将任意大小的输入（键）转换为固定范围内的整数（索引）。例如：

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

上面这个函数使用了经典的 djb2 算法，将字符串键转换为一个整数索引。

冲突是什么？如何解决？

由于哈希函数的输出范围有限，不同的键可能被映射到同一个位置，这称为“冲突”。常见的冲突解决方法有：

• 链地址法（Chaining）：每个桶（bucket）是一个链表，所有映射到同一位置的元素都存入该链表。
• 开放地址法（Open Addressing）：当发生冲突时，在表中寻找下一个空闲位置。

本教程采用链地址法，因为它实现简单且易于理解。

动手实现一个简单的哈希表

下面我们将用 C 语言实现一个支持字符串键和整数值的哈希表。

#include <stdio.h>#include <stdlib.h>#include <string.h>#define TABLE_SIZE 100typedef struct Entry {    char *key;    int value;    struct Entry *next;} Entry;Entry *hash_table[TABLE_SIZE];unsigned int hash(const char *key) {    unsigned int hash_value = 0;    while (*key) {        hash_value = (hash_value << 5) - hash_value + *key;        key++;    }    return hash_value % TABLE_SIZE;}void insert(const char *key, int value) {    unsigned int index = hash(key);    Entry *new_entry = (Entry*)malloc(sizeof(Entry));    new_entry->key = strdup(key);    new_entry->value = value;    new_entry->next = hash_table[index];    hash_table[index] = new_entry;}int search(const char *key) {    unsigned int index = hash(key);    Entry *entry = hash_table[index];    while (entry) {        if (strcmp(entry->key, key) == 0) {            return entry->value;        }        entry = entry->next;    }    return -1; // 表示未找到}int main() {    for (int i = 0; i < TABLE_SIZE; i++) {        hash_table[i] = NULL;    }    insert("apple", 10);    insert("banana", 20);    printf("apple: %d\n", search("apple"));   // 输出 10    printf("banana: %d\n", search("banana")); // 输出 20    return 0;}

总结

通过本教程，你已经掌握了C语言哈希表的基本原理、哈希函数的设计、冲突解决的方法，并亲手实现了一个简单的哈希表。这是学习C语言数据结构的重要一步！

继续练习，尝试扩展功能，比如删除操作、动态扩容等，你的编程能力将大幅提升！