跳到主要内容
数据结构：哈希表原理与 C 语言实现 | 极客日志
C 算法
数据结构：哈希表原理与 C 语言实现 综述由AI生成 介绍哈希表的概念、核心思想及哈希函数设计方法，涵盖直接定址法、除留余数法等常见算法。详细讲解了哈希冲突的定义及开放定址法（线性探测、二次探测等）、链地址法的解决策略。提供了基于 C 语言的哈希表 ADT 实现，包括创建、插入、查找、删除、销毁等操作，并分析了装载因子与平均查找长度（ASL）。最后总结了哈希表的性能特点及适用场景，适合需要快速查找的场景。
kaikai 发布于 2026/3/29 更新于 2026/5/30 一、哈希表（Hash Table）
1. 哈希表概念
1.1 定义
哈希表是一种存储和查询技术 ，通过哈希函数 将关键字映射到表中位置，实现 O(1) 的平均查找时间。
1.2 核心思想
存储位置 = f(key)
存储位置 ：数组中存储数据的地址f ：哈希函数，根据存储内容计算下标的函数key ：需要存储的数据
1.3 特点
使用顺序表 实现，需要支持随机访问数据
在大量数据中快速查找 （O(1)或 O(log n)）
理想情况下查找时间为常数
既可用于存储 ，也可用于查询
2. 哈希函数设计
2.1 设计要点
计算相对简单 ：快速计算哈希值地址分布均匀 ：减少冲突概率
2.2 常见哈希函数
2.2.1 直接定址法
h(key) = a × key + b
优点 ：简单，无冲突缺点 ：需要关键字分布连续适用 ：关键字分布连续且范围小
2.2.2 除留余数法（最常用）
h(key) = key % p
p 的选择 ：通常为质数，且不大于表长 m优点 ：简单，分布相对均匀缺点 ：容易产生聚集
2.2.3 平方取中法
h(key) = (key²的中间几位)
步骤 ：key 平方 → 取中间几位作为地址适用 ：不知道关键字分布，位数适中
2.2.4 折叠法
将关键字分成几部分，然后相加
移位折叠 ：各部分直接相加边界折叠 ：相邻部分反向相加适用 ：关键字位数较多
2.2.5 数字分析法
抽取关键字中分布均匀的若干位作为哈希地址
3. 哈希冲突
3.1 冲突定义
f(key1) == f(key2), key1 != key2
需要存储的数据不同，但哈希函数计算出的下标相同。
3.2 冲突解决方法
3.2.1 开放定址法
线性探测法 ：
hᵢ(key) = (h(key) + i) % m, i = 0,1,2,...,m-1
优点 ：简单易实现缺点 ：容易产生堆积 （一次聚集）探测序列 ：+1, +2, +3, ..., +n (n < 数组容量) hᵢ(key) = (h(key) ± i²) % m, i = 0,1,2,...,m-1
优点 ：减少堆积现象缺点 ：不能探测所有位置探测序列 ：+1², -1², +2², -2², +4², -4², ... hᵢ(key) = (h(key) + rand()) % m
hᵢ(key) = (h₁(key) + i × h₂(key)) % m
h₁和 h₂是两个不同的哈希函数
优点 ：冲突少，分布均匀缺点 ：计算复杂
3.2.2 链地址法 typedef struct HashNode {struct HashNode *next ;typedef struct {
优点 ：无堆积现象，删除方便缺点 ：需要额外指针空间
3.2.3 公共溢出区法
哈希表分为基本表 和溢出表
冲突元素放入溢出表
优点 ：实现简单缺点 ：查找效率降低
4. 哈希表 ADT 实现
4.1 数据结构定义 typedef int DATATYPE;
typedef struct {int tlen;
int count;
int * status;
} HS_TABLE;
4.2 基本操作实现
4.2.1 创建哈希表 HS_TABLE* CreateHsTable (int len) {
HS_TABLE* hs = (HS_TABLE*)malloc (sizeof (HS_TABLE));
if (hs == NULL ) return NULL ;
hs->head = (DATATYPE*)malloc (sizeof (DATATYPE) * len);
hs->status = (int *)malloc (sizeof (int ) * len);
hs->tlen = len;
hs->count = 0 ;
if (hs->head == NULL || hs->status == NULL ) {
free (hs->head);
free (hs->status);
free (hs);
return NULL ;
}
for (int i = 0 ; i < len; i++) {
hs->status[i] = 0 ;
}
return hs;
}
4.2.2 哈希函数（除留余数法） int HashFunc (DATATYPE key, int size) {
return key % size;
}
4.2.3 插入元素（线性探测） int InsertHsTable (HS_TABLE* hs, DATATYPE data) {
if (hs == NULL || hs->count >= hs->tlen) {
return -1 ;
}
int index = HashFunc(data, hs->tlen);
int i = 0 ;
while (i < hs->tlen) {
int pos = (index + i) % hs->tlen;
if (hs->status[pos] == 0 || hs->status[pos] == 2 ) {
hs->head[pos] = data;
hs->status[pos] = 1 ;
hs->count++;
return pos;
}
else if (hs->status[pos] == 1 && hs->head[pos] == data) {
return -2 ;
}
i++;
}
return -1 ;
}
4.2.4 查找元素 int SearchHsTable (HS_TABLE* hs, DATATYPE data) {
if (hs == NULL ) return -1 ;
int index = HashFunc(data, hs->tlen);
int i = 0 ;
while (i < hs->tlen) {
int pos = (index + i) % hs->tlen;
if (hs->status[pos] == 0 ) {
return -1 ;
}
if (hs->status[pos] == 1 && hs->head[pos] == data) {
return pos;
}
i++;
}
return -1 ;
}
4.2.5 删除元素 int DeleteHsTable (HS_TABLE* hs, DATATYPE data) {
if (hs == NULL ) return -1 ;
int pos = SearchHsTable(hs, data);
if (pos == -1 ) {
return -1 ;
}
hs->status[pos] = 2 ;
hs->count--;
return pos;
}
4.2.6 销毁哈希表 int DestroyHsTable (HS_TABLE* hs) {
if (hs == NULL ) return -1 ;
free (hs->head);
free (hs->status);
free (hs);
return 0 ;
}
4.2.7 显示哈希表 void DisplayHsTable (HS_TABLE* hs) {
if (hs == NULL ) return ;
printf ("哈希表（长度=%d，元素数=%d）:\n" , hs->tlen, hs->count);
printf ("索引\t状态\t数据\n" );
printf ("-------------------\n" );
for (int i = 0 ; i < hs->tlen; i++) {
printf ("%d\t" , i);
switch (hs->status[i]) {
case 0 : printf ("空\t-\n" ); break ;
case 1 : printf ("占用\t%d\n" , hs->head[i]); break ;
case 2 : printf ("删除\t-\n" ); break ;
}
}
}
5. 哈希表性能分析
5.1 装载因子
n ：表中元素个数m ：哈希表长度α越大 ，冲突概率越高建议 ：α < 0.75
5.2 平均查找长度（ASL）
5.2.1 查找成功 ASL 成功 = Σ(查找每个元素的比较次数) / n
5.2.2 查找失败
5.3 不同方法的 ASL 冲突解决方法 ASL 成功（平均） ASL 失败（平均） 线性探测法 (1 + 1/(1-α)²)/2 (1 + 1/(1-α))/2 二次探测法 -ln(1-α)/α 1/(1-α) 链地址法 1 + α/2 α + e⁻α
6. 完整示例代码 #include <stdio.h>
#include <stdlib.h>
#define EMPTY 0
#define OCCUPIED 1
#define DELETED 2
typedef int DATATYPE;
typedef struct {int * status;
int size;
int count;
} HashTable;
HashTable* CreateHashTable (int size) {
HashTable* ht = (HashTable*)malloc (sizeof (HashTable));
if (!ht) return NULL ;
ht->data = (DATATYPE*)malloc (sizeof (DATATYPE) * size);
ht->status = (int *)calloc (size, sizeof (int ));
ht->size = size;
ht->count = 0 ;
if (!ht->data || !ht->status) {
free (ht->data);
free (ht->status);
free (ht);
return NULL ;
}
return ht;
}
int HashFunction (DATATYPE key, int size) {
return abs (key) % size;
}
int HashInsert (HashTable* ht, DATATYPE key) {
if (!ht || ht->count >= ht->size) return -1 ;
int index = HashFunction(key, ht->size);
int i = 0 ;
while (i < ht->size) {
int pos = (index + i) % ht->size;
if (ht->status[pos] == EMPTY || ht->status[pos] == DELETED) {
ht->data[pos] = key;
ht->status[pos] = OCCUPIED;
ht->count++;
return pos;
}
else if (ht->status[pos] == OCCUPIED && ht->data[pos] == key) {
return -2 ;
}
i++;
}
return -1 ;
}
int HashSearch (HashTable* ht, DATATYPE key) {
if (!ht) return -1 ;
int index = HashFunction(key, ht->size);
int i = 0 ;
while (i < ht->size) {
int pos = (index + i) % ht->size;
if (ht->status[pos] == EMPTY) {
return -1 ;
}
if (ht->status[pos] == OCCUPIED && ht->data[pos] == key) {
return pos;
}
i++;
}
return -1 ;
}
int HashDelete (HashTable* ht, DATATYPE key) {
if (!ht) return -1 ;
int pos = HashSearch(ht, key);
if (pos == -1 ) return -1 ;
ht->status[pos] = DELETED;
ht->count--;
return pos;
}
void DestroyHashTable (HashTable* ht) {
if (!ht) return ;
free (ht->data);
free (ht->status);
free (ht);
}
void DisplayHashTable (HashTable* ht) {
if (!ht) return ;
printf ("\n哈希表状态（大小=%d，元素=%d）:\n" , ht->size, ht->count);
printf ("索引\t状态\t数据\n" );
printf ("--------------------\n" );
for (int i = 0 ; i < ht->size; i++) {
printf ("%d\t" , i);
switch (ht->status[i]) {
case EMPTY: printf ("空\t-\n" ); break ;
case OCCUPIED: printf ("占用\t%d\n" , ht->data[i]); break ;
case DELETED: printf ("删除\t-\n" ); break ;
}
}
}
int main () {
HashTable* ht = CreateHashTable(10 );
if (!ht) {
printf ("创建哈希表失败！\n" );
return 1 ;
}
printf ("=== 哈希表测试 ===\n" );
int keys[] = {19 , 29 , 39 , 49 , 59 , 69 , 79 , 89 , 99 , 109 };
for (int i = 0 ; i < 10 ; i++) {
int result = HashInsert(ht, keys[i]);
if (result >= 0 ) {
printf ("插入 %d 成功，位置：%d\n" , keys[i], result);
} else if (result == -2 ) {
printf ("插入 %d 失败，元素已存在\n" , keys[i]);
} else {
printf ("插入 %d 失败，表满\n" , keys[i]);
}
}
DisplayHashTable(ht);
printf ("\n查找测试:\n" );
int search_keys[] = {39 , 50 , 89 };
for (int i = 0 ; i < 3 ; i++) {
int pos = HashSearch(ht, search_keys[i]);
if (pos >= 0 ) {
printf ("查找 %d 成功，位置：%d\n" , search_keys[i], pos);
} else {
printf ("查找 %d 失败，元素不存在\n" , search_keys[i]);
}
}
printf ("\n删除测试:\n" );
int delete_key = 49 ;
int del_pos = HashDelete(ht, delete_key);
if (del_pos >= 0 ) {
printf ("删除 %d 成功，位置：%d\n" , delete_key, del_pos);
} else {
printf ("删除 %d 失败\n" , delete_key);
}
DisplayHashTable(ht);
printf ("\n在删除位置插入新元素:\n" );
int new_key = 119 ;
int ins_pos = HashInsert(ht, new_key);
if (ins_pos >= 0 ) {
printf ("插入 %d 成功，位置：%d\n" , new_key, ins_pos);
}
DisplayHashTable(ht);
DestroyHashTable(ht);
return 0 ;
}
7. 应用场景
7.1 适合使用哈希表的场景
快速查找 ：字典、电话簿、用户数据库去重操作 ：统计唯一元素缓存系统 ：Redis、Memcached数据库索引 ：快速定位记录编译器符号表 ：变量名查找拼写检查 ：单词快速查找
7.2 不适合使用哈希表的场景
需要有序数据 ：哈希表无序范围查询 ：如"查找 10-20 之间的所有值"前缀搜索 ：如"查找以'abc'开头的所有词"数据量极小 ：直接线性查找更简单
8. 总结 特性 哈希表 查找速度 O(1) 平均，O(n) 最坏 插入速度 O(1) 平均 删除速度 O(1) 平均 空间复杂度 O(n) 是否有序 无序 最佳适用 快速查找，无需排序
核心优势 ：在理想情况下，哈希表提供了最快的查找速度（O(1)），特别适合需要频繁查找操作的场景。
注意事项 ：需要合理设计哈希函数和处理冲突的方法，否则可能退化为 O(n) 的查找效率。
相关免费在线工具 加密/解密文本 使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
Gemini 图片去水印 基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印，支持批量处理与下载。 在线工具，Gemini 图片去水印在线工具，online
Base64 字符串编码/解码 将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器 将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
Markdown转HTML 将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
HTML转Markdown 将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
