C语言哈希表实现：线性探测法

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

  7. HashItem table[TABLE_SIZE]; // 全局哈希表
这里：
key是字符串（字符指针）
value是整数
isOccupied跟踪槽位状态：
0: 空
1: 占用
-1: 已删除（墓碑标记）
🔑 哈希函数
一个基本的字符串哈希函数，能够合理地分散键。
  1. unsigned int hash(const char* key) {
  2. unsigned int hash = 0;
  3. while (*key)
  1. hash = (hash * 31) + *key++; // 简单哈希逻辑
  1. return hash % TABLE_SIZE;
  1. }
这给了我们一个0到TABLE_SIZE - 1之间的索引。
🔧 插入逻辑
使用线性探测处理冲突。
  1. void insert(const char* key, int value) {
  2. int index = hash(key);
  3. int originalIndex = index;
  1. while (table[index].isOccupied == 1 && strcmp(table[index].key, key) != 0) {
  2. index = (index + 1) % TABLE_SIZE;
  1. if (index == originalIndex) {
  2. printf("哈希表已满！\n");
  3. return;
  4. }
  5. }
  1. if (table[index].isOccupied != 1) {
  2. table[index].key = strdup(key); // 将键复制到堆内存
  3. table[index].value = value;
  4. table[index].isOccupied = 1;
  5. } else {
  6. table[index].value = value; // 如果键已存在则更新值
  7. }
  1. }
⚠️ 注意事项：
strdup()为键分配内存。
如果键已存在，它会更新值。
🔍 搜索函数
  1. int get(const char* key) {
  2. int index = hash(key);
  3. int originalIndex = index;
  1. while (table[index].isOccupied != 0) {
  2. if (table[index].isOccupied == 1 && strcmp(table[index].key, key) == 0)
  3. return table[index].value;
  1. index = (index + 1) % TABLE_SIZE;
  2. if (index == originalIndex)
  3. break;
  4. }
  1. return -1; // 未找到
  1. }
如果找到则返回值，如果不存在则返回-1。
🗑️ 删除
  1. void delete(const char* key) {
  2. int index = hash(key);
  3. int originalIndex = index;
  1. while (table[index].isOccupied != 0) {
  2. if (table[index].isOccupied == 1 && strcmp(table[index].key, key) == 0) {
  3. free(table[index].key); // 释放内存
  1. table[index].key = NULL;
  2. table[index].isOccupied = -1;
  3. printf("已删除 '%s'\n", key);
  4. return;
  5. }
  1. index = (index + 1) % TABLE_SIZE;
  2. if (index == originalIndex)
  3. break;
  4. }
  5. printf("未找到键 '%s'。\n", key);
  1. }
我们使用-1作为删除标记，这样我们可以在未来的搜索中继续探测。
🧪 演示
  1. int main() {
  2. insert("apple", 10);
  3. insert("banana", 20);
  4. insert("orange", 30);
  5. insert("grape", 40);

  7. printf("apple: %d\n", get("apple"));
  8. printf("banana: %d\n", get("banana"));

  10. delete("banana");

  12. printf("删除后 banana: %d\n", get("banana"));

  14. insert("banana", 50); // 重新插入
  15. printf("新的 banana: %d\n", get("banana"));

  17. return 0;
  18. }
📤 输出
apple: 10
banana: 20
已删除 'banana'
删除后 banana: -1
新的 banana: 50
✅ 总结
我们使用以下方法实现了一个简单的固定大小哈希表：
字符串的基本哈希函数
线性探测解决冲突
已删除槽位的标记
手动内存管理（malloc, strdup, free）
这对于学习哈希映射在底层如何工作来说是完美的。
🚀 额外想法
实现动态调整大小（重新哈希）
使用双重哈希或二次探测
使用void存储通用值
添加负载因子阈值