C语言链式哈希表详解（从零开始掌握哈希冲突解决方案）

什么是链式哈希表？

链式哈希表（Chained Hash Table）是哈希表的一种实现方式，它通过在每个哈希桶中维护一个链表来处理冲突。当两个或多个键经过哈希函数计算后得到相同的索引时，它们会被添加到同一个链表中。

这种设计使得即使发生大量冲突，哈希表依然能正常工作，只是性能会有所下降（最坏情况退化为链表查找）。

实现步骤

我们将逐步构建一个简单的链式哈希表，支持插入、查找和删除操作。

1. 定义节点和哈希表结构

// 链表节点结构typedef struct Node {    int key;    int value;    struct Node* next;} Node;// 哈希表结构#define TABLE_SIZE 10typedef struct {    Node* buckets[TABLE_SIZE];} HashTable;

2. 初始化哈希表

void initHashTable(HashTable* table) {    for (int i = 0; i < TABLE_SIZE; i++) {        table->buckets[i] = NULL;    }}

3. 哈希函数

unsigned int hash(int key) {    return key % TABLE_SIZE;}

4. 插入操作

void insert(HashTable* table, int key, int value) {    unsigned int index = hash(key);        // 检查是否已存在该键    Node* current = table->buckets[index];    while (current != NULL) {        if (current->key == key) {            current->value = value; // 更新值            return;        }        current = current->next;    }        // 创建新节点并插入到链表头部    Node* newNode = (Node*)malloc(sizeof(Node));    newNode->key = key;    newNode->value = value;    newNode->next = table->buckets[index];    table->buckets[index] = newNode;}

5. 查找操作

int search(HashTable* table, int key) {    unsigned int index = hash(key);    Node* current = table->buckets[index];        while (current != NULL) {        if (current->key == key) {            return current->value;        }        current = current->next;    }        // 未找到    printf("Key %d not found!\n", key);    return -1; // 假设-1表示未找到}

6. 删除操作

void deleteKey(HashTable* table, int key) {    unsigned int index = hash(key);    Node* current = table->buckets[index];    Node* prev = NULL;        while (current != NULL && current->key != key) {        prev = current;        current = current->next;    }        if (current == NULL) {        printf("Key %d not found for deletion!\n", key);        return;    }        // 如果要删除的是头节点    if (prev == NULL) {        table->buckets[index] = current->next;    } else {        prev->next = current->next;    }        free(current);}

完整示例与测试

#include <stdio.h>#include <stdlib.h>// ... 上面定义的所有结构和函数 ...int main() {    HashTable table;    initHashTable(&table);        // 插入数据    insert(&table, 10, 100);    insert(&table, 20, 200);    insert(&table, 5, 50);        // 查找数据    printf("Value for key 10: %d\n", search(&table, 10));    printf("Value for key 20: %d\n", search(&table, 20));        // 删除数据    deleteKey(&table, 10);        // 再次查找（应提示未找到）    search(&table, 10);        return 0;}

为什么选择链式哈希表？

链式哈希表是解决哈希冲突的经典方法之一。相比开放寻址法，它有以下优点：

• 实现简单直观，易于理解和调试
• 不受装载因子限制，可以容纳任意数量的元素（虽然性能会下降）
• 删除操作更简单，不会影响其他元素的位置

总结

通过本教程，我们详细讲解了如何用C语言实现链式哈希表，包括结构定义、初始化、哈希函数、插入、查找和删除等核心操作。掌握这一C语言数据结构不仅有助于理解底层原理，也为后续学习更高级的数据结构打下坚实基础。

记住，良好的哈希函数和合适的表大小是保证哈希表高效运行的关键。在实际项目中，你可能需要根据具体需求调整这些参数。

希望这篇教程能帮助你轻松入门C语言哈希表！如果你有任何问题，欢迎在评论区留言交流。