C语言实现哈希表（开放地址法详解：小白也能掌握的哈希冲突解决方案）

什么是开放地址法？

开放地址法是一种处理哈希冲突的方法。当发生冲突时，它不会使用链表或其他结构来存储多个元素，而是继续在哈希表数组中寻找下一个“空闲”的位置来存放冲突的元素。

常见的探测方式包括：

• 线性探测（Linear Probing）：依次检查下一个位置（i+1, i+2, ...）
• 二次探测（Quadratic Probing）：按二次方跳跃（i+1², i+2², ...）
• 双重哈希（Double Hashing）：使用第二个哈希函数计算步长

本文将以最简单的 线性探测 为例进行讲解。

C语言哈希表设计思路

我们需要定义一个结构体来表示哈希表中的每个“槽位”（slot）。每个槽位需要包含：

• 键（key）
• 值（value）
• 状态（state）：用于标记该槽位是空（EMPTY）、已占用（OCCUPIED）还是曾被删除（DELETED）

为什么需要“DELETED”状态？因为如果直接将删除的槽设为空，会影响后续查找（线性探测路径会被截断）。

完整代码实现

下面是一个完整的、可运行的 C 语言开放地址哈希表示例：

// hash_table.h#include <stdio.h>#include <stdlib.h>#include <string.h>#define TABLE_SIZE 10#define EMPTY 0#define OCCUPIED 1#define DELETED 2typedef struct {    int key;    int value;    int state; // 状态标记} HashItem;typedef struct {    HashItem* items;    int size;} HashTable;void initHashTable(HashTable* table) {    table->items = (HashItem*)malloc(sizeof(HashItem) * TABLE_SIZE);    table->size = TABLE_SIZE;    for (int i = 0; i < TABLE_SIZE; i++) {        table->items[i].state = EMPTY;    }}int hash(int key) {    return key % TABLE_SIZE;}void insert(HashTable* table, int key, int value) {    int index = hash(key);    int original = index;    while (table->items[index].state == OCCUPIED) {        if (table->items[index].key == key) {            table->items[index].value = value; // 更新已有键            return;        }        index = (index + 1) % TABLE_SIZE;        if (index == original) {            printf("哈希表已满！\n");            return;        }    }    table->items[index].key = key;    table->items[index].value = value;    table->items[index].state = OCCUPIED;}int search(HashTable* table, int key) {    int index = hash(key);    int original = index;    while (table->items[index].state != EMPTY) {        if (table->items[index].state == OCCUPIED &&            table->items[index].key == key) {            return table->items[index].value;        }        index = (index + 1) % TABLE_SIZE;        if (index == original) break;    }    return -1; // 未找到}void deleteKey(HashTable* table, int key) {    int index = hash(key);    int original = index;    while (table->items[index].state != EMPTY) {        if (table->items[index].state == OCCUPIED &&            table->items[index].key == key) {            table->items[index].state = DELETED;            return;        }        index = (index + 1) % TABLE_SIZE;        if (index == original) break;    }    printf("键 %d 不存在！\n", key);}void freeHashTable(HashTable* table) {    free(table->items);}// 测试主函数int main() {    HashTable table;    initHashTable(&table);    insert(&table, 10, 100);    insert(&table, 20, 200);    insert(&table, 30, 300);    printf(查找键 20: %d\n", search(&table, 20));    deleteKey(&table, 20);    printf(删除后查找键 20: %d\n", search(&table, 20));    freeHashTable(&table);    return 0;}

代码解析

1. hash() 函数使用取模运算将键映射到 0~9 的索引范围。
2. 插入时，若当前位置已被占用且键不同，则线性探测下一个位置。
3. 删除时，不设为 EMPTY，而是设为 DELETED，避免破坏探测链。
4. 查找时，跳过 DELETED 状态的槽位，直到遇到 EMPTY 或找到目标。

总结

通过本教程，你已经掌握了如何用 C语言 实现一个基于 开放地址法 的哈希表。这种方法虽然简单，但在实际应用中非常有效，尤其适合内存受限或对缓存友好性要求高的场景。

记住，良好的 C语言数据结构 基础是成为优秀程序员的关键。而理解 哈希冲突解决 机制，能让你在面试和项目中脱颖而出！

赶快动手试试吧！修改 TABLE_SIZE、尝试二次探测，或者加入字符串键支持，都是不错的进阶练习。