哈希表在c语言中通过哈希函数、冲突解决策略和数据存储实现。1. 哈希函数将键转换为索引，常用方法包括取模法和乘法哈希；2. 冲突解决采用开放寻址或链地址法，前者通过线性探测、二次探测或双重哈希寻找空槽位，后者使用链表存储冲突元素；3. 数据存储方式上，开放寻址直接存数据于数组，链地址法则存链表指针。开放寻址节省空间但易聚集且删除复杂，链地址法实现简单、支持动态增长但需额外内存且查找效率受链表长度影响。选择策略取决于数据量、空间利用率、查找效率及删除频率，若哈希函数均匀分布，开放寻址性能更佳，否则链地址法更优。
哈希表，简单来说，就是一种能够快速查找数据的结构。C语言里实现哈希表，两种常见方法是开放寻址和链地址法。它们各有千秋，选择哪个取决于你的具体应用场景。
解决方案
C语言实现哈希表的核心在于：哈希函数、冲突解决策略和数据存储。
-
哈希函数： 将键（key）转换为数组索引。一个好的哈希函数应该尽量均匀地分布键，减少冲突。常见的哈希函数包括取模法、乘法哈希等。
立即学习“C语言免费学习笔记（深入）”；
unsigned int hash(char *key, int table_size) { unsigned int hashVal = 0; while (*key != '\0') { hashVal = (hashVal << 5) + *key++; // 左移5位相当于乘以32 } return hashVal % table_size; } -
冲突解决： 当不同的键映射到相同的索引时，就会发生冲突。开放寻址和链地址法是两种主要的冲突解决策略。
数据存储： 哈希表本质上是一个数组，数组的每个元素可以存储数据（开放寻址）或者指向链表的指针（链地址法）。
开放寻址（Open Addressing）：
开放寻址是指在发生冲突时，通过某种探测方法在哈希表中寻找下一个可用的空槽位。
线性探测： 简单地检查下一个槽位，如果被占用，继续检查下一个，直到找到空槽位。
二次探测： 以二次方步长检查槽位，例如 h+1², h+2², h+3²...
-
双重哈希： 使用另一个哈希函数来计算步长。
// 线性探测示例 int insert_open_addressing(char *key, int value, int *table, int table_size) { int index = hash(key, table_size); int original_index = index; while (table[index] != -1) { // -1 表示空槽位 index = (index + 1) % table_size; // 线性探测 if (index == original_index) { // 表已满 return -1; } } table[index] = value; return index; }
链地址法（Separate Chaining）：
链地址法是指哈希表的每个槽位都指向一个链表，所有哈希到同一个槽位的键值对都存储在该链表中。
实现简单： 插入和删除操作相对简单。
-
允许负载因子大于1： 链表可以动态增长，因此哈希表可以存储比槽位数更多的元素。
// 链地址法示例 typedef struct HashNode { char *key; int value; struct HashNode *next; } HashNode; int insert_chaining(char *key, int value, HashNode **table, int table_size) { int index = hash(key, table_size); HashNode *newNode = (HashNode*)malloc(sizeof(HashNode)); if (!newNode) { return -1; // 内存分配失败 } newNode->key = strdup(key); // 复制key，避免key被修改 newNode->value = value; newNode->next = table[index]; table[index] = newNode; return index; }
开放寻址的优缺点？
开放寻址的优点是节省空间，因为它不需要额外的链表结构。缺点是容易产生聚集（clustering）现象，导致查找效率降低。聚集是指哈希到相邻槽位的键值对会形成连续的占用区域，使得查找时间变长。删除操作也比较复杂，需要特殊处理，否则会影响后续查找。
链地址法的优缺点？
链地址法的优点是实现简单，插入和删除操作容易，并且允许负载因子大于1。缺点是需要额外的空间来存储链表，并且如果链表过长，查找效率会降低。如果哈希函数设计不好，所有键都哈希到同一个槽位，那么链地址法就退化成了链表，查找时间复杂度变为O(n)。
如何选择开放寻址和链地址法？
选择哪种方法取决于你的具体需求。如果你的数据量不大，并且对空间利用率要求较高，那么开放寻址可能更适合。如果你的数据量很大，并且对查找效率要求较高，那么链地址法可能更适合。此外，如果你的哈希函数能够保证键的均匀分布，那么开放寻址的性能也会更好。在实际应用中，也可以将两种方法结合起来，例如使用开放寻址来解决小规模的冲突，而使用链地址法来解决大规模的冲突。另一个考虑因素是删除操作的频率。如果删除操作很频繁，那么链地址法通常是更好的选择，因为它更容易实现删除操作。
