C语言哈希表实现：线性探测法
东城
·2026-01-31
🧠 用C语言构建简单哈希表（使用线性探测）
#c #hashing #datastructures #programming
🧠 用C语言构建简单哈希表（使用线性探测）
哈希表是最高效的数据结构之一，在快速查找、插入和删除方面表现出色。在本文中，我们将从头开始用C语言实现一个简单的哈希表——使用开放寻址法中的线性探测。
我们将涵盖：
使用结构体创建键值对
简单的字符串哈希函数
使用线性探测解决冲突
插入、搜索和删除操作
完整的演示和解释
🧱 数据结构设计
我们定义了一个结构体HashItem来存储哈希表中的每个键值对。
#define TABLE_SIZE 100
typedef struct {
char* key;
int value;
int isOccupied; // 0 = 空, 1 = 占用, -1 = 已删除
} HashItem;

HashItem table[TABLE_SIZE]; // 全局哈希表
这里：
key是字符串（字符指针）
value是整数
isOccupied跟踪槽位状态：
0: 空
1: 占用
-1: 已删除（墓碑标记）
🔑 哈希函数
一个基本的字符串哈希函数，能够合理地分散键。
unsigned int hash(const char* key) {
unsigned int hash = 0;
while (*key)
hash = (hash * 31) + *key++; // 简单哈希逻辑
return hash % TABLE_SIZE;
}
这给了我们一个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; // 如果键已存在则更新值
}
}
⚠️ 注意事项：
strdup()为键分配内存。
如果键已存在，它会更新值。
🔍 搜索函数
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; // 未找到
}
如果找到则返回值，如果不存在则返回-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);
}
我们使用-1作为删除标记，这样我们可以在未来的搜索中继续探测。
🧪 演示
int main() {
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
✅ 总结
我们使用以下方法实现了一个简单的固定大小哈希表：
字符串的基本哈希函数
线性探测解决冲突
已删除槽位的标记
手动内存管理（malloc, strdup, free）
这对于学习哈希映射在底层如何工作来说是完美的。
🚀 额外想法
实现动态调整大小（重新哈希）
使用双重哈希或二次探测
使用void存储通用值
添加负载因子阈值
Aa