当前位置：首页 > news >正文

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

news 2025/6/6 9:18:14

一、引言

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

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 关键字实现