C语言哈希表实现：线性探测法深度解析
C语言哈希表实现：线性探测法深度解析
今日目标
理解哈希表的基本概念和工作原理
掌握线性探测法的冲突解决机制
学会用C语言实现完整的哈希表
了解哈希函数的设计原则
掌握内存管理和性能优化技巧
哈希表概述
哈希表是最高效的数据结构之一，在快速查找、插入和删除操作方面表现出色。本文将从头开始实现一个简单的C语言哈希表，使用开放寻址法中的线性探测来解决冲突。
我们将涵盖：
使用结构体创建键值对
简单的字符串哈希函数
线性探测的冲突解决
插入、搜索和删除操作
完整的演示和解释
数据结构设计
哈希表项结构
#define TABLE_SIZE 100
typedef struct {
char* key; // 键（字符串）
int value; // 值（整数）
int isOccupied; // 槽位状态：0=空，1=占用，-1=已删除
} HashItem;
HashItem table[TABLE_SIZE]; // 全局哈希表
状态标记说明
0 (空): 槽位从未被使用过
1 (占用): 槽位当前存储着有效数据
-1 (已删除): 槽位之前被使用过但已被删除（墓碑标记）
哈希函数设计
基本字符串哈希函数
unsigned int hash(const char* key) {
unsigned int hash = 0;
while (*key) {
hash = (hash * 31) + *key++; // 简单哈希逻辑
}
return hash % TABLE_SIZE;
}
哈希函数特点
使用31作为乘数（质数，减少冲突）
逐字符计算哈希值
通过模运算确保索引在有效范围内
返回0到TABLE_SIZE-1之间的索引
插入操作实现
线性探测插入逻辑
void insert(const char* key, int value) {
int index = hash(key);
int originalIndex = index;
// 线性探测：处理冲突
while (table[index].isOccupied == 1 && strcmp(table[index].key, key) != 0) {
index = (index + 1) % TABLE_SIZE;
if (index == originalIndex) {
printf("哈希表已满！\n");
return;
}
}
// 插入或更新
if (table[index].isOccupied != 1) {
table[index].key = strdup(key); // 将键复制到堆内存
table[index].value = value;
table[index].isOccupied = 1;
} else {
table[index].value = value; // 如果键已存在则更新值
}
}
查找操作实现
搜索函数
int get(const char* key) {
int index = hash(key);
int originalIndex = index;
// 线性探测搜索
while (table[index].isOccupied != 0) {
if (table[index].isOccupied == 1 && strcmp(table[index].key, key) == 0) {
return table[index].value;
}
index = (index + 1) % TABLE_SIZE;
if (index == originalIndex) {
break;
}
}
return -1; // 未找到
}
删除操作实现
删除函数
void delete(const char* key) {
int index = hash(key);
int originalIndex = index;
while (table[index].isOccupied != 0) {
if (table[index].isOccupied == 1 && strcmp(table[index].key, key) == 0) {
free(table[index].key); // 释放内存
table[index].key = NULL;
table[index].isOccupied = -1; // 标记为已删除
printf("已删除 '%s'\n", key);
return;
}
index = (index + 1) % TABLE_SIZE;
if (index == originalIndex) {
break;
}
}
printf("未找到键 '%s'。\n", key);
}
完整实现示例
主程序演示
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 100
typedef struct {
char* key;
int value;
int isOccupied;
} HashItem;
HashItem table[TABLE_SIZE];
// 初始化哈希表
void init_table() {
for (int i = 0; i < TABLE_SIZE; i++) {
table[i].key = NULL;
table[i].value = 0;
table[i].isOccupied = 0;
}
}
// 哈希函数
unsigned int hash(const char* key) {
unsigned int hash = 0;
while (*key) {
hash = (hash * 31) + *key++;
}
return hash % TABLE_SIZE;
}
// 插入函数
void insert(const char* key, int value) {
int index = hash(key);
int originalIndex = index;
while (table[index].isOccupied == 1 && strcmp(table[index].key, key) != 0) {
index = (index + 1) % TABLE_SIZE;
if (index == originalIndex) {
printf("哈希表已满！\n");
return;
}
}
if (table[index].isOccupied != 1) {
table[index].key = strdup(key);
table[index].value = value;
table[index].isOccupied = 1;
} else {
table[index].value = value;
}
}
// 查找函数
int get(const char* key) {
int index = hash(key);
int originalIndex = index;
while (table[index].isOccupied != 0) {
if (table[index].isOccupied == 1 && strcmp(table[index].key, key) == 0) {
return table[index].value;
}
index = (index + 1) % TABLE_SIZE;
if (index == originalIndex) {
break;
}
}
return -1;
}
// 删除函数
void delete(const char* key) {
int index = hash(key);
int originalIndex = index;
while (table[index].isOccupied != 0) {
if (table[index].isOccupied == 1 && strcmp(table[index].key, key) == 0) {
free(table[index].key);
table[index].key = NULL;
table[index].isOccupied = -1;
printf("已删除 '%s'\n", key);
return;
}
index = (index + 1) % TABLE_SIZE;
if (index == originalIndex) {
break;
}
}
printf("未找到键 '%s'。\n", key);
}
int main() {
init_table();
// 插入测试数据
insert("apple", 10);
insert("banana", 20);
insert("orange", 30);
insert("grape", 40);
printf("apple: %d\n", get("apple"));
printf("banana: %d\n", get("banana"));
// 删除测试
delete("banana");
printf("删除后 banana: %d\n", get("banana"));
// 重新插入
insert("banana", 50);
printf("重新插入后 banana: %d\n", get("banana"));
return 0;
}
运行结果
apple: 10
banana: 20
已删除 'banana'
删除后 banana: -1
重新插入后 banana: 50
性能分析
时间复杂度
平均情况: O(1) - 插入、查找、删除
最坏情况: O(n) - 当哈希表接近满时
最佳情况: O(1) - 无冲突时
空间复杂度
固定大小: O(1) - 预分配TABLE_SIZE个槽位
动态大小: O(n) - 根据实际数据量调整
优化建议
1. 动态扩容
// 动态扩容实现思路
void resize_table() {
// 1. 保存旧表数据
// 2. 创建更大的新表
// 3. 重新哈希所有数据
// 4. 释放旧表内存
}
2. 更好的哈希函数
// 改进的哈希函数
unsigned int improved_hash(const char* key) {
unsigned int hash = 5381;
int c;
while ((c = *key++)) {
hash = ((hash << 5) + hash) + c; // hash * 33 + c
}
return hash % TABLE_SIZE;
}
3. 双重哈希
// 双重哈希函数
unsigned int hash1(const char* key) {
// 主哈希函数
}
unsigned int hash2(const char* key) {
// 辅助哈希函数
}
// 双重哈希探测
int index = hash1(key);
int step = hash2(key);
while (冲突) {
index = (index + step) % TABLE_SIZE;
}
实际应用场景
1. 缓存系统
// 简单的LRU缓存
typedef struct {
char* key;
void* data;
time_t access_time;
int isOccupied;
} CacheItem;
2. 符号表
// 编译器符号表
typedef struct {
char* symbol_name;
int symbol_type;
int scope_level;
int isOccupied;
} SymbolTableItem;
3. 配置管理
// 配置项存储
typedef struct {
char* config_key;
char* config_value;
int isOccupied;
} ConfigItem;
常见问题解决
1. 内存泄漏
// 清理哈希表
void cleanup_table() {
for (int i = 0; i < TABLE_SIZE; i++) {
if (table[i].isOccupied == 1) {
free(table[i].key);
table[i].key = NULL;
}
}
}
2. 哈希冲突过多
// 监控冲突率
int collision_count(const char* key) {
int index = hash(key);
int originalIndex = index;
int collisions = 0;
while (table[index].isOccupied == 1 && strcmp(table[index].key, key) != 0) {
index = (index + 1) % TABLE_SIZE;
collisions++;
if (index == originalIndex) break;
}
return collisions;
}
今日总结
我们实现了一个简单但完整的C语言哈希表，使用线性探测法解决冲突：
核心要点
数据结构设计: 使用结构体存储键值对和状态信息
哈希函数: 简单有效的字符串哈希算法
冲突解决: 线性探测法处理哈希冲突
内存管理: 正确分配和释放动态内存
墓碑标记: 删除操作的特殊处理
关键特性
快速操作: 平均O(1)时间复杂度的查找、插入、删除
内存效率: 固定大小的数组存储
冲突处理: 线性探测确保数据完整性
易于理解: 清晰的代码结构和注释
扩展方向
动态扩容: 实现自动调整表大小
多种探测: 双重哈希、二次探测
泛型支持: 支持任意数据类型
性能优化: 负载因子监控和自动调整
练习建议
基础练习: 实现不同的哈希函数并比较性能
进阶练习: 添加动态扩容功能
实战练习: 实现LRU缓存或符号表
优化练习: 添加性能监控和统计功能
扩展阅读
掌握哈希表的实现原理，是理解高效数据结构的重要基础！