哈希表入门：用 C 语言实现简单哈希表（开放寻址法解决冲突）

目录

一、引言

二、代码结构与核心概念解析

1. 数据结构定义

2. 初始化函数 initList

3. 哈希函数 hash

4. 插入函数 put（核心逻辑）

开放寻址法详解：

三、主函数验证与运行结果

1. 测试逻辑

2. 运行结果分析

四、完整代码

五、优化方向与注意事项

1. 现有代码局限性

2. 优化建议

3. 注意事项

六、总结

七、扩展思考

---

一、引言

哈希表（Hash Table）是一种高效的数据结构，通过哈希函数实现数据的快速查找与插入。本文将通过一段 C 语言代码实例，带大家理解哈希表的基本原理，并分析开放寻址法解决哈希冲突的实现逻辑。

二、哈希表基础概念

1. 定义与核心思想

哈希表（Hash Table，也称为散列表）是一种根据键（Key）直接访问内存存储位置的数据结构。它通过哈希函数（Hash Function）将键映射到存储桶（Bucket）或槽位（Slot），从而实现高效的数据插入、查找和删除操作。

核心思想：将数据的键通过哈希函数转换为数组索引，使数据可以直接定位，无需遍历整个数据集。

2. 基本结构

一个简单的哈希表通常由以下部分组成：

• 数组：作为存储数据的物理空间，每个位置称为一个 “槽位” 或 “桶”
• 哈希函数：将键转换为数组索引的映射函数
• 冲突处理机制：解决不同键映射到相同索引的问题

3. 关键操作时间复杂度

• 插入：平均 O (1)，最坏 O (n)（冲突严重时）
• 查找：平均 O (1)，最坏 O (n)
• 删除：平均 O (1)，最坏 O (n)

这种高效性使得哈希表广泛应用于数据库索引、缓存系统（如 Redis）、编程语言内置数据结构（如 Python 的字典、Java 的 HashMap）等场景。

三、代码结构

1. 数据结构定义

typedef struct HashList
{int num;        // 记录元素个数char *data;     // 哈希表数组
} HashList;

• num：用于统计哈希表中实际存储的元素数量
• data：字符型数组，作为哈希表的存储载体，大小由宏定义NUM（值为 10）决定

2. 初始化函数 initList

HashList *initList()
{HashList *list = (HashList *)malloc(sizeof(HashList));list->num = 0;list->data = (char *)malloc(sizeof(char) * NUM);for (int i = 0; i < NUM; i++){list->data[i] = 0;  // 初始化为0（空槽）}return list;
}

• 功能：分配哈希表结构体内存，初始化数组为空槽（0表示空）
• 关键点：动态内存分配确保哈希表可独立管理内存，初始化空槽为后续冲突处理奠定基础

3. 哈希函数 hash

int hash(char data)
{return data % NUM;  // 取模运算生成哈希地址
}

• 设计思路：利用字符 ASCII 码对哈希表大小NUM取模，将字符映射到[0, 9]的索引范围内
• 特点：简单直观，但可能产生哈希冲突（不同字符映射到相同索引）

4. 插入函数 put（核心逻辑）

void put(HashList *list, char data)
{if (list->num >= NUM){printf("哈希表已满，无法插入");return;}int index = hash(data);          // 初始哈希地址int count = 1;                   // 冲突次数计数器// 开放寻址法解决冲突（线性探测）while (list->data[index] != 0)  {index = hash(hash(data) + count);  // 新地址 = 原哈希值 + 增量再取模count++;if (count == NUM)  // 尝试所有位置后仍无空位{printf("无法找到空位插入");return;}}// 插入数据list->data[index] = data;list->num++;
}

开放寻址法详解：

• 冲突处理策略：线性探测（Linear Probing）
  • 当发现哈希地址index被占用时，按index+1, index+2,...的顺序依次查找下一个空槽
  • 代码中通过hash(hash(data) + count)实现等价于(index + count) % NUM的循环探测
• 终止条件：
  • 找到空槽（data[index] == 0）
  • 遍历所有槽位仍无空位（count == NUM）

四、主函数验证与运行结果

1. 测试逻辑

int main()
{HashList *list = initList();put(list, 'A');  // 'A'的ASCII码为65，65%10=5 → 初始地址5put(list, 'F');  // 'F'的ASCII码为70，70%10=0 → 初始地址0（假设空槽）// 打印非空槽位for (int i = 0; i < NUM; i++){if (list->data[i] != 0){printf("data[%d]=%c\n", i, list->data[i]);}}printf("哈希表中有%d个元素", list->num);return 0;
}

2. 运行结果分析

假设'A'和'F'插入时均未发生冲突：

data[5]=A
data[0]=F
哈希表中有2个元素

• 若插入顺序导致冲突（如先插入'K'（ASCII 75，75%10=5）再插入'A'），则'A'会探测到5+1=6号槽位（假设为空）并插入

五、完整代码

#include <stdio.h>
#include <stdlib.h>
#define NUM 10typedef struct HashList
{int num;char *data;
} HashList;HashList *initList()
{HashList *list = (HashList *)malloc(sizeof(HashList));list->num = 0;list->data = (char *)malloc(sizeof(char) * NUM);for (int i = 0; i < NUM; i++){list->data[i] = 0;}return list;
}int hash(char data)
{return data % NUM;
}void put(HashList *list, char data)
{if (list->num >= NUM){printf("哈希表已满，无法插入");}int index = hash(data);int count = 1;while (list->data[index] != 0){index = hash(hash(data) + count);count++;}if (count == NUM){printf("无法找到空位插入");}else{list->data[index] = data;list->num++;}
}int main()
{HashList *list = initList();put(list, 'A');put(list, 'F');for (int i = 0; i < NUM; i++){if (list->data[i] != 0){printf("data[%d]=%c\n", i, list->data[i]);}}printf("哈希表中有%d个元素", list->num);return 0;
}

六、优化方向与注意事项

1. 现有代码局限性

• 固定大小：哈希表大小由NUM硬编码，无法动态扩容
• 单一类型：仅支持字符型数据存储，可通过泛型改造支持多类型
• 线性探测缺陷：可能产生 “聚类”（Cluster）现象，导致后续插入效率下降

2. 优化建议

优化点	方案
动态扩容	当元素个数超过负载因子（如 0.75）时，重新分配更大数组并重新哈希所有元素
改进冲突处理	改用二次探测（index + i²）或双重哈希（多个哈希函数）
支持泛型	使用void*指针结合类型标签，或通过 C11 _Generic 关键字实现

3. 注意事项

• 内存管理：使用完哈希表后需调用free释放data和结构体内存，避免内存泄漏
• 负载因子控制：合理设置负载因子（元素数 / 表大小），平衡空间与时间效率
• 哈希函数设计：对于字符串等复杂数据，需设计更均匀的哈希函数（如 DJB2、FNV 算法）

七、总结

本文通过一个简单的 C 语言实例，演示了哈希表的基本实现流程：

1. 哈希函数将数据映射到表中位置
2. 开放寻址法（线性探测）处理哈希冲突
3. 动态内存管理实现表的初始化与数据存储

哈希表的核心优势在于 ** 平均 O (1)** 的插入和查找时间复杂度，但其性能高度依赖哈希函数设计和冲突处理策略。实际开发中需根据数据特性选择合适的哈希表实现方案。

八、扩展思考

1. 如何实现哈希表的查找（get）功能？
2. 尝试用链表法（链地址法）改写冲突处理逻辑
3. 分析线性探测与二次探测的性能差异

欢迎在评论区分享你的思路与实践！