C语言哈希表实战指南（开放地址法详解与代码实现）

C语言实现开放地址法（线性探测）

下面我们用C语言实现一个简单的哈希表，使用线性探测作为开放地址法的策略。

#include <stdio.h>#include <stdlib.h>#define TABLE_SIZE 10#define EMPTY -1      // 表示该位置为空#define DELETED -2    // 表示该位置曾被删除typedef struct {    int key;    int value;} HashItem;// 哈希表结构HashItem hashTable[TABLE_SIZE];// 初始化哈希表void initHashTable() {    for (int i = 0; i < TABLE_SIZE; i++) {        hashTable[i].key = EMPTY;    }}// 简单的哈希函数int hashFunction(int key) {    return key % TABLE_SIZE;}// 插入键值对void insert(int key, int value) {    int index = hashFunction(key);    int originalIndex = index;    // 线性探测寻找空位    while (hashTable[index].key != EMPTY &&            hashTable[index].key != DELETED &&            hashTable[index].key != key) {        index = (index + 1) % TABLE_SIZE;        // 如果回到起点，说明表已满        if (index == originalIndex) {            printf("哈希表已满，无法插入！\n");            return;        }    }    hashTable[index].key = key;    hashTable[index].value = value;}// 查找键对应的值int search(int key) {    int index = hashFunction(key);    int originalIndex = index;    while (hashTable[index].key != EMPTY) {        if (hashTable[index].key == key) {            return hashTable[index].value;        }        index = (index + 1) % TABLE_SIZE;        if (index == originalIndex) break; // 已遍历完整个表    }    return -1; // 未找到}// 删除键值对（懒删除）void deleteKey(int key) {    int index = hashFunction(key);    int originalIndex = index;    while (hashTable[index].key != EMPTY) {        if (hashTable[index].key == key) {            hashTable[index].key = DELETED;            hashTable[index].value = 0;            return;        }        index = (index + 1) % TABLE_SIZE;        if (index == originalIndex) break;    }    printf("未找到要删除的键：%d\n", key);}// 打印哈希表void printHashTable() {    printf("当前哈希表状态：\n");    for (int i = 0; i < TABLE_SIZE; i++) {        if (hashTable[i].key == EMPTY) {            printf("%d: [空]\n", i);        } else if (hashTable[i].key == DELETED) {            printf("%d: [已删除]\n", i);        } else {            printf("%d: (%d, %d)\n", i, hashTable[i].key, hashTable[i].value);        }    }    printf("\n");}// 主函数测试int main() {    initHashTable();    insert(5, 50);    insert(15, 150); // 与5冲突，线性探测到下一位    insert(25, 250); // 再次冲突    insert(7, 70);    printHashTable();    printf("查找 key=15 的值: %d\n", search(15));    printf("查找 key=99 的值: %d\n", search(99));    deleteKey(15);    printHashTable();    return 0;}

关键点解析

1. EMPTY 和 DELETED 标记：我们使用 -1 表示空槽，-2 表示已被删除的槽。这是为了确保查找操作能正确跳过已删除项但继续探测。

2. 循环探测：使用 (index + 1) % TABLE_SIZE 实现环形探测，避免越界。

3. 表满判断：如果探测一圈又回到起点，说明表已满，无法插入新元素。

开放地址法的优缺点

优点：

• 不需要额外的指针或链表，内存更紧凑
• 缓存友好，数据局部性好

缺点：

• 容易产生“聚集”现象（尤其是线性探测）
• 删除操作复杂，通常采用“懒删除”
• 负载因子（元素数量/表大小）不能太高，一般建议 ≤ 0.7

总结

通过本教程，你已经掌握了C语言哈希表中开放地址法的基本原理和实现方式。这种C语言冲突解决策略非常适合内存受限或对缓存性能要求高的场景。

记住，良好的哈希表实现需要选择合适的哈希函数、表大小（建议质数）和负载因子控制。希望你能动手尝试修改代码，比如实现二次探测或双重哈希，进一步加深理解！