引言
在刷完《代码随想录》的数组和链表章节后，我进入了哈希表这一部分。哈希表（Hash Table）是解决“查找/判断是否存在”类问题的利器。无论是简单题“两数之和”，还是稍复杂的“三数之和”，核心思想都是利用空间换时间，将查找的复杂度降低到 O(1)。本文将总结我在学习过程中对哈希表应用的理解，以及不同场景下容器（数组、set、map）的选择策略。
一、什么时候该用哈希表？
当我们需要快速判断一个元素是否出现过，或者统计一个元素出现的频率时，哈希表是第一选择。例如，给定一个字符串，判断另一个字符串的字符是否都能在第一个字符串中找到（字母异位词），这就是典型的哈希表应用场景。
二、C 语言中哈希表的实现选择
C 语言没有内置的哈希表容器，通常有以下几种方式：
数组：当数值范围有限且分布均匀时，数组是最简单的哈希表。
例子：判断两个字符串是否为字母异位词。由于字母只有 26 个，可以直接开一个大小为 26 的数组int hash[26]，下标对应'a'到'z'。uthash：当数值范围很大，或需要存储键值对时，可以使用开源库uthash。它通过宏定义提供了哈希表的增删改查功能，非常方便。
例子：“两数之和”需要存储数值和下标，用 uthash 实现最为简洁。手写哈希表：对于特定场景（如固定大小、开放地址法），也可以自己实现，但会增加代码量。
三、实战演练：两数之和
这是哈希表最经典的入门题。题目要求返回两个数下标，使得它们的和等于目标值。
思路：遍历数组，对于当前元素nums[i]，查找target - nums[i]是否在之前的遍历中出现过。
使用 uthash，我们将遍历过的元素存入哈希表（key 为元素值，value 为下标），查找时间 O(1)，整体复杂度 O(n)。
完整代码（C语言）：
c
#include <stdio.h> #include <stdlib.h> #include "uthash.h" // 需要包含 uthash 头文件 // 定义哈希表结构体 struct hash_table { int key; // 数组元素值 int index; // 元素下标 UT_hash_handle hh; // 使结构体支持哈希操作 }; int* twoSum(int* nums, int numsSize, int target, int* returnSize) { struct hash_table *hash = NULL, *item, *tmp; int *result = (int*)malloc(2 * sizeof(int)); *returnSize = 0; for (int i = 0; i < numsSize; i++) { int complement = target - nums[i]; // 查找 complement 是否在哈希表中 HASH_FIND_INT(hash, &complement, item); if (item) { result[0] = item->index; result[1] = i; *returnSize = 2; break; } // 未找到，将当前元素插入哈希表 item = (struct hash_table*)malloc(sizeof(struct hash_table)); item->key = nums[i]; item->index = i; HASH_ADD_INT(hash, key, item); } // 释放哈希表内存（可选） HASH_ITER(hh, hash, item, tmp) { HASH_DEL(hash, item); free(item); } return result; }四、进阶难点：三数之和的去重问题
做完“两数之和”，做“三数之和”时发现，如果单纯延续哈希法的思路，虽然也能做，但去重非常棘手。
题目要求返回所有不重复的三元组。如果使用哈希法，把a+b+c=0转化为a+b = -c，将两数之和的解法套进来，虽然能找到结果，但在去重时需要非常复杂的判断。
转折点：通过《代码随想录》的视频讲解，我意识到对于“三数之和”这种需要去重且不要求返回下标的问题，排序 + 双指针是比哈希法更优雅的方案。
具体做法：
先将数组排序（qsort）。
固定一个指针
i（代表a），然后使用左右指针left和right在i的右侧寻找b和c。去重技巧：
当
i > 0且nums[i] == nums[i-1]时，跳过该i，避免重复的三元组。当找到满足条件的组合后，移动
left和right时，跳过相邻重复的元素。
核心代码
#include <stdlib.h> int cmp(const void *a, const void *b) { return *(int*)a - *(int*)b; } int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) { qsort(nums, numsSize, sizeof(int), cmp); int **res = (int**)malloc(sizeof(int*) * numsSize * numsSize); *returnSize = 0; *returnColumnSizes = (int*)malloc(sizeof(int) * numsSize * numsSize); for (int i = 0; i < numsSize - 2; i++) { // 去重 if (i > 0 && nums[i] == nums[i-1]) continue; int left = i + 1, right = numsSize - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum < 0) { left++; } else if (sum > 0) { right--; } else { // 找到一个解 res[*returnSize] = (int*)malloc(3 * sizeof(int)); res[*returnSize][0] = nums[i]; res[*returnSize][1] = nums[left]; res[*returnSize][2] = nums[right]; (*returnColumnSizes)[*returnSize] = 3; (*returnSize)++; // 去重 while (left < right && nums[left] == nums[left+1]) left++; while (left < right && nums[right] == nums[right-1]) right--; left++; right--; } } } return res; }五、总结
数据结构的选择至关重要：在 C 语言中，根据场景选择数组、uthash 或手写哈希表，能让代码事半功倍。
哈希法虽好，但不是万能的：当题目对去重要求较高，或者结果集需要去重时，结合“排序+双指针”往往能简化代码逻辑，降低思维复杂度。
时空复杂度分析：要时刻保持对 O(n) 和 O(n²) 的敏感度，哈希表就是用空间换时间的典型代表
