C语言哈希表实现：线性探测法深度解析

作者头像东城·2026-01-31 23:32:12·
C语言哈希表实现：线性探测法深度解析
今日目标
理解哈希表的基本概念和工作原理
掌握线性探测法的冲突解决机制
学会用C语言实现完整的哈希表
了解哈希函数的设计原则
掌握内存管理和性能优化技巧
哈希表概述
哈希表是最高效的数据结构之一，在快速查找、插入和删除操作方面表现出色。本文将从头开始实现一个简单的C语言哈希表，使用开放寻址法中的线性探测来解决冲突。
我们将涵盖：
使用结构体创建键值对
简单的字符串哈希函数
线性探测的冲突解决
插入、搜索和删除操作
完整的演示和解释
数据结构设计
哈希表项结构
  1. #define TABLE_SIZE 100

  3. typedef struct {
  4. char* key; // 键（字符串）
  5. int value; // 值（整数）
  6. int isOccupied; // 槽位状态：0=空，1=占用，-1=已删除
  7. } HashItem;

  9. HashItem table[TABLE_SIZE]; // 全局哈希表
c
状态标记说明
0 (空): 槽位从未被使用过
1 (占用): 槽位当前存储着有效数据
-1 (已删除): 槽位之前被使用过但已被删除（墓碑标记）
哈希函数设计
基本字符串哈希函数
  1. unsigned int hash(const char* key) {
  2. unsigned int hash = 0;
  3. while (*key) {
  4. hash = (hash * 31) + *key++; // 简单哈希逻辑
  5. }
  6. return hash % TABLE_SIZE;
  7. }
c
哈希函数特点
使用31作为乘数（质数，减少冲突）
逐字符计算哈希值
通过模运算确保索引在有效范围内
返回0到TABLE_SIZE-1之间的索引
插入操作实现
线性探测插入逻辑
  1. void insert(const char* key, int value) {
  2. int index = hash(key);
  3. int originalIndex = index;
  5. // 线性探测：处理冲突
  6. while (table[index].isOccupied == 1 && strcmp(table[index].key, key) != 0) {
  7. index = (index + 1) % TABLE_SIZE;
  8. if (index == originalIndex) {
  9. printf("哈希表已满！\n");
  10. return;
  11. }
  12. }
  14. // 插入或更新
  15. if (table[index].isOccupied != 1) {
  16. table[index].key = strdup(key); // 将键复制到堆内存
  17. table[index].value = value;
  18. table[index].isOccupied = 1;
  19. } else {
  20. table[index].value = value; // 如果键已存在则更新值
  21. }
  22. }
c
查找操作实现
搜索函数
  1. int get(const char* key) {
  2. int index = hash(key);
  3. int originalIndex = index;
  5. // 线性探测搜索
  6. while (table[index].isOccupied != 0) {
  7. if (table[index].isOccupied == 1 && strcmp(table[index].key, key) == 0) {
  8. return table[index].value;
  9. }
  10. index = (index + 1) % TABLE_SIZE;
  11. if (index == originalIndex) {
  12. break;
  13. }
  14. }
  16. return -1; // 未找到
  17. }
c
删除操作实现
删除函数
  1. void delete(const char* key) {
  2. int index = hash(key);
  3. int originalIndex = index;
  5. while (table[index].isOccupied != 0) {
  6. if (table[index].isOccupied == 1 && strcmp(table[index].key, key) == 0) {
  7. free(table[index].key); // 释放内存
  8. table[index].key = NULL;
  9. table[index].isOccupied = -1; // 标记为已删除
  10. printf("已删除 '%s'\n", key);
  11. return;
  12. }
  14. index = (index + 1) % TABLE_SIZE;
  15. if (index == originalIndex) {
  16. break;
  17. }
  18. }
  20. printf("未找到键 '%s'。\n", key);
  21. }
c
完整实现示例
主程序演示
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  5. #define TABLE_SIZE 100

  7. typedef struct {
  8. char* key;
  9. int value;
  10. int isOccupied;
  11. } HashItem;

  13. HashItem table[TABLE_SIZE];

  15. // 初始化哈希表
  16. void init_table() {
  17. for (int i = 0; i < TABLE_SIZE; i++) {
  18. table[i].key = NULL;
  19. table[i].value = 0;
  20. table[i].isOccupied = 0;
  21. }
  22. }

  24. // 哈希函数
  25. unsigned int hash(const char* key) {
  26. unsigned int hash = 0;
  27. while (*key) {
  28. hash = (hash * 31) + *key++;
  29. }
  30. return hash % TABLE_SIZE;
  31. }

  33. // 插入函数
  34. void insert(const char* key, int value) {
  35. int index = hash(key);
  36. int originalIndex = index;
  38. while (table[index].isOccupied == 1 && strcmp(table[index].key, key) != 0) {
  39. index = (index + 1) % TABLE_SIZE;
  40. if (index == originalIndex) {
  41. printf("哈希表已满！\n");
  42. return;
  43. }
  44. }
  46. if (table[index].isOccupied != 1) {
  47. table[index].key = strdup(key);
  48. table[index].value = value;
  49. table[index].isOccupied = 1;
  50. } else {
  51. table[index].value = value;
  52. }
  53. }

  55. // 查找函数
  56. int get(const char* key) {
  57. int index = hash(key);
  58. int originalIndex = index;
  60. while (table[index].isOccupied != 0) {
  61. if (table[index].isOccupied == 1 && strcmp(table[index].key, key) == 0) {
  62. return table[index].value;
  63. }
  64. index = (index + 1) % TABLE_SIZE;
  65. if (index == originalIndex) {
  66. break;
  67. }
  68. }
  70. return -1;
  71. }

  73. // 删除函数
  74. void delete(const char* key) {
  75. int index = hash(key);
  76. int originalIndex = index;
  78. while (table[index].isOccupied != 0) {
  79. if (table[index].isOccupied == 1 && strcmp(table[index].key, key) == 0) {
  80. free(table[index].key);
  81. table[index].key = NULL;
  82. table[index].isOccupied = -1;
  83. printf("已删除 '%s'\n", key);
  84. return;
  85. }
  87. index = (index + 1) % TABLE_SIZE;
  88. if (index == originalIndex) {
  89. break;
  90. }
  91. }
  93. printf("未找到键 '%s'。\n", key);
  94. }

  96. int main() {
  97. init_table();
  99. // 插入测试数据
  100. insert("apple", 10);
  101. insert("banana", 20);
  102. insert("orange", 30);
  103. insert("grape", 40);
  105. printf("apple: %d\n", get("apple"));
  106. printf("banana: %d\n", get("banana"));
  108. // 删除测试
  109. delete("banana");
  110. printf("删除后 banana: %d\n", get("banana"));
  112. // 重新插入
  113. insert("banana", 50);
  114. printf("重新插入后 banana: %d\n", get("banana"));
  116. return 0;
  117. }
c
运行结果
  1. apple: 10
  2. banana: 20
  3. 已删除 'banana'
  4. 删除后 banana: -1
  5. 重新插入后 banana: 50
性能分析
时间复杂度
平均情况: O(1) - 插入、查找、删除
最坏情况: O(n) - 当哈希表接近满时
最佳情况: O(1) - 无冲突时
空间复杂度
固定大小: O(1) - 预分配TABLE_SIZE个槽位
动态大小: O(n) - 根据实际数据量调整
优化建议
1. 动态扩容
  1. // 动态扩容实现思路
  2. void resize_table() {
  3. // 1. 保存旧表数据
  4. // 2. 创建更大的新表
  5. // 3. 重新哈希所有数据
  6. // 4. 释放旧表内存
  7. }
c
2. 更好的哈希函数
  1. // 改进的哈希函数
  2. unsigned int improved_hash(const char* key) {
  3. unsigned int hash = 5381;
  4. int c;
  6. while ((c = *key++)) {
  7. hash = ((hash << 5) + hash) + c; // hash * 33 + c
  8. }
  10. return hash % TABLE_SIZE;
  11. }
c
3. 双重哈希
  1. // 双重哈希函数
  2. unsigned int hash1(const char* key) {
  3. // 主哈希函数
  4. }

  6. unsigned int hash2(const char* key) {
  7. // 辅助哈希函数
  8. }

  10. // 双重哈希探测
  11. int index = hash1(key);
  12. int step = hash2(key);
  13. while (冲突) {
  14. index = (index + step) % TABLE_SIZE;
  15. }
c
实际应用场景
1. 缓存系统
  1. // 简单的LRU缓存
  2. typedef struct {
  3. char* key;
  4. void* data;
  5. time_t access_time;
  6. int isOccupied;
  7. } CacheItem;
c
2. 符号表
  1. // 编译器符号表
  2. typedef struct {
  3. char* symbol_name;
  4. int symbol_type;
  5. int scope_level;
  6. int isOccupied;
  7. } SymbolTableItem;
c
3. 配置管理
  1. // 配置项存储
  2. typedef struct {
  3. char* config_key;
  4. char* config_value;
  5. int isOccupied;
  6. } ConfigItem;
c
常见问题解决
1. 内存泄漏
  1. // 清理哈希表
  2. void cleanup_table() {
  3. for (int i = 0; i < TABLE_SIZE; i++) {
  4. if (table[i].isOccupied == 1) {
  5. free(table[i].key);
  6. table[i].key = NULL;
  7. }
  8. }
  9. }
c
2. 哈希冲突过多
  1. // 监控冲突率
  2. int collision_count(const char* key) {
  3. int index = hash(key);
  4. int originalIndex = index;
  5. int collisions = 0;
  7. while (table[index].isOccupied == 1 && strcmp(table[index].key, key) != 0) {
  8. index = (index + 1) % TABLE_SIZE;
  9. collisions++;
  10. if (index == originalIndex) break;
  11. }
  13. return collisions;
  14. }
c
今日总结
我们实现了一个简单但完整的C语言哈希表，使用线性探测法解决冲突：
核心要点
数据结构设计: 使用结构体存储键值对和状态信息
哈希函数: 简单有效的字符串哈希算法
冲突解决: 线性探测法处理哈希冲突
内存管理: 正确分配和释放动态内存
墓碑标记: 删除操作的特殊处理
关键特性
快速操作: 平均O(1)时间复杂度的查找、插入、删除
内存效率: 固定大小的数组存储
冲突处理: 线性探测确保数据完整性
易于理解: 清晰的代码结构和注释
扩展方向
动态扩容: 实现自动调整表大小
多种探测: 双重哈希、二次探测
泛型支持: 支持任意数据类型
性能优化: 负载因子监控和自动调整
练习建议
基础练习: 实现不同的哈希函数并比较性能
进阶练习: 添加动态扩容功能
实战练习: 实现LRU缓存或符号表
优化练习: 添加性能监控和统计功能
扩展阅读
哈希表算法详解
线性探测法原理
C语言内存管理最佳实践
数据结构与算法分析
掌握哈希表的实现原理，是理解高效数据结构的重要基础！