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

目录

一、引言

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

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

2. 运行结果分析

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

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

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

五、完整代码

#include #include #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 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 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. 分析线性探测与二次探测的性能差异

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