数据结构:哈希表原理与 C 语言实现
本文介绍哈希表的概念、核心思想及哈希函数设计方法,涵盖直接定址法、除留余数法等常见算法。详细讲解了哈希冲突的定义及开放定址法(线性探测、二次探测等)、链地址法的解决策略。提供了基于 C 语言的哈希表 ADT 实现,包括创建、插入、查找、删除、销毁等操作,并分析了装载因子与平均查找长度(ASL)。最后总结了哈希表的性能特点及适用场景,适合需要快速查找的场景。

本文介绍哈希表的概念、核心思想及哈希函数设计方法,涵盖直接定址法、除留余数法等常见算法。详细讲解了哈希冲突的定义及开放定址法(线性探测、二次探测等)、链地址法的解决策略。提供了基于 C 语言的哈希表 ADT 实现,包括创建、插入、查找、删除、销毁等操作,并分析了装载因子与平均查找长度(ASL)。最后总结了哈希表的性能特点及适用场景,适合需要快速查找的场景。

哈希表是一种存储和查询技术,通过哈希函数将关键字映射到表中位置,实现 O(1) 的平均查找时间。
存储位置 = f(key)
h(key) = a × key + b
h(key) = key % p
h(key) = (key²的中间几位)
将关键字分成几部分,然后相加
抽取关键字中分布均匀的若干位作为哈希地址
f(key1) == f(key2), key1 != key2
需要存储的数据不同,但哈希函数计算出的下标相同。
线性探测法:
hᵢ(key) = (h(key) + i) % m, i = 0,1,2,...,m-1
二次探测法:
hᵢ(key) = (h(key) ± i²) % m, i = 0,1,2,...,m-1
随机探测法:
hᵢ(key) = (h(key) + rand()) % m
双散列法:
hᵢ(key) = (h₁(key) + i × h₂(key)) % m
typedef struct HashNode { KeyType key; DataType value; struct HashNode *next; } HashNode;
typedef struct { HashNode **table; // 指针数组 int size; // 表长 int count; // 元素个数 } HashTable;
typedef int DATATYPE;
typedef struct {
DATATYPE* head; // 数据数组
int tlen; // 表长度
int count; // 元素个数
int* status; // 状态数组:0-空,1-占用,2-删除
} HS_TABLE;
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;
}
// 初始化状态为 0(空)
for (int i = 0; i < len; i++) {
hs->status[i] = 0;
}
return hs;
}
int HashFunc(DATATYPE key, int size) {
return key % size;
}
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; // 未找到插入位置
}
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; // 未找到
}
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;
}
int DestroyHsTable(HS_TABLE* hs) {
if (hs == NULL) return -1;
free(hs->head);
free(hs->status);
free(hs);
return 0;
}
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;
}
}
}
α = n / m
ASL 成功 = Σ(查找每个元素的比较次数) / n
ASL 失败 = Σ(到空位置比较次数) / m
| 冲突解决方法 | ASL 成功(平均) | ASL 失败(平均) |
|---|---|---|
| 线性探测法 | (1 + 1/(1-α)²)/2 | (1 + 1/(1-α))/2 |
| 二次探测法 | -ln(1-α)/α | 1/(1-α) |
| 链地址法 | 1 + α/2 | α + e⁻α |
#include <stdio.h>
#include <stdlib.h>
#define EMPTY 0
#define OCCUPIED 1
#define DELETED 2
// 哈希表 ADT 实现
typedef int DATATYPE;
typedef struct {
DATATYPE* data; // 数据数组
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)); // 初始化为 0
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;
}
| 特性 | 哈希表 |
|---|---|
| 查找速度 | O(1) 平均,O(n) 最坏 |
| 插入速度 | O(1) 平均 |
| 删除速度 | O(1) 平均 |
| 空间复杂度 | O(n) |
| 是否有序 | 无序 |
| 最佳适用 | 快速查找,无需排序 |
核心优势:在理想情况下,哈希表提供了最快的查找速度(O(1)),特别适合需要频繁查找操作的场景。
注意事项:需要合理设计哈希函数和处理冲突的方法,否则可能退化为 O(n) 的查找效率。

微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML 转 Markdown 互为补充。 在线工具,Markdown 转 HTML在线工具,online
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML 转 Markdown在线工具,online
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online