刷算法题的人应该都见过这道两数之和Two Sum给定一个整数数组和一个目标值返回两个元素的下标让它们加起来等于目标值。不少教程习惯用 Java、Python 直接调现成的 HashMap 或 dict几行搞定。但我一直觉得用 C 语言自己写一个哈希表来做这道题才是真正把“哈希表”这颗数据结构之树连根拔起的过程——你需要自己设计哈希函数、处理冲突、管理内存每一步都能踩出真实的经验。这篇文我就完整拆一下 C 语言实现两数之和的全过程从暴力解法的瓶颈讲起到哈希表的原理和选型再到完整的代码实现与调试实录最后聊聊那些文档里不会写的坑。不管你是刚学完指针和结构体的 C 语言新手还是在准备笔试面试想补数据结构基础都可以在这篇里找到能直接抄作业的东西。1. 从暴力解法讲起看清两数之和的题眼1.1 问题本身看起来简单其实有三道门槛先把题目老老实实摆出来给定一个数组nums给定一个整数target要求返回两个下标i和j使得nums[i] nums[j] target。题目有几个容易被忽略的约束每个输入只有唯一解不能使用同一个元素两次数组长度可以很大大到 O(n²) 的算法可能直接超时。我用 C 语言实现之前一直觉得这道题“就这”。实际上手之后才发现考点根本不在于“会不会数学变形”而在于三件事一是能不能意识到暴力循环的慢二是知不知道哈希表能把这个问题的复杂度从 O(n²) 降到 O(n)三是用 C 语言实现哈希表时能不能把内存、哈希函数、冲突处理这些底层细节都收拾干净。这三道门槛一过两数之和就不再是“会写循环”就能糊弄过去的题而是考察数据结构和工程习惯的试金石。1.2 暴力解法为什么慢看循环嵌套的实际成本最简单的写法是双层循环外层固定一个数内层扫剩余的数int *twoSumBruteForce(int *nums, int numsSize, int target, int *returnSize) { for (int i 0; i numsSize; i) { for (int j i 1; j numsSize; j) { if (nums[i] nums[j] target) { int *res (int *)malloc(2 * sizeof(int)); res[0] i; res[1] j; *returnSize 2; return res; } } } *returnSize 0; return NULL; }这个代码的语义没有问题问题出在它的复杂度。当numsSize n时内层循环次数是等差数列求和(n-1) (n-2) ... 1 n(n-1)/2。也就是说当 n 1 万时要比较约 5000 万次n 10 万时要比较 50 亿次。这个增长趋势是平方级的在实际的笔试评测里数组稍微给大一点就能让你眼睁睁看着超时。你可能会想“那我可以提前排序再用二分查找。”确实可以排序 O(n log n)二分 O(n log n)整体能压到 O(n log n)。但这个思路有个附加成本排序会打乱元素顺序你要想找回原始下标就得用结构体把值和下标绑定再排序代码会变得啰嗦。哈希表方案的优势就在于既不改变原数组顺序又能把查找时间降到常数级别。1.3 空间换时间为什么“边查边插”比“先插满再查”更聪明哈希表的思路用一个生活类比来说就是查字典暴力解法相当于把整本书从头翻到尾找某个字哈希表方案则是先把“字 - 页码”的索引建立起来然后直接翻到那一页。但两数之和有一个非常刁钻的细节如果你先把整个数组一次性全部插入哈希表再回过头来查遇到数组里有重复元素时会出错。比如nums [3, 3]、target 6两个 3 都在数组里但同一个 key3在哈希表里只能存一个下标。如果先插入后一个 3 会把前一个 3 的下标覆盖掉最后你只能得到一个下标找不到两个。正确的做法是边遍历边查询遍历到第 i 个元素时先查target - nums[i]在不在表里如果不在再把nums[i]作为 key、i 作为 value 插入。这样既不会丢重复元素的下标还能保证每次查询到的下标一定在 i 之前天然满足“不能用同一个元素两次”的约束。这个“边查边插”的细节就是我开头说的题眼。很多初学者甚至一些网上的代码都是先填满表再查询遇到[3, 3]或者[2, 2, 2]这类用例就会翻车。从数据结构设计的角度看这一个细节决定了代码正确性的边界。2. C 语言实现哈希表的全套方案2.1 为什么不用现成的哈希表库C 语言没有“白嫖”的快乐写 Java 和 Python 的人可能体会不到C 标准库里没有通用哈希表。虽然有些项目会引入 glib、uthash 这类第三方库但在刷题场景和很多嵌入式/底层开发场景里要么不允许要么不值得为一道题引入一个依赖。所以你想在 C 语言里用哈希表只能自己写。自己写的第一个好处是彻底搞清楚哈希表的内部结构桶数组、节点链表、哈希函数、冲突处理缺一不可。第二个好处是你能按需裁剪两数之和只需要存 int 键和 int 值那就不需要泛型直接用两个 int 字段搞定。第三个好处是如果将来面试官追问“这个哈希表能不能扩容”或者“冲突太多怎么办”你至少知道答案在哪里。这部分内容都可以在我的 GitHub 仓库里看到完整源码见文章最后的链接下面我先把最关键的设计决策讲清楚。2.2 哈希函数怎么选直接取模 vs 位运算扰动哈希函数的价值是让不同的 key 尽可能均匀地落在桶里减少冲突。最简单的做法是对容量取模hash key % capacity。但直接取模在两种情况下会很难看一是 key 是负数时C 语言的%运算结果也是负数直接拿它当数组下标就会越界二是当 capacity 是 2 的幂时直接取模只保留低几位如果 key 的最低几位呈现规律性比如全是偶数冲突就会扎堆链表拉得老长。我的做法是先把 key 转成无符号整数再做一个类似 MurmurHash 的扰动处理最后对容量取模static int hash_key(int key, int capacity) { unsigned int h (unsigned int)key; h ^ h 16; h * 0x7feb352d; h ^ h 15; h * 0x846ca68b; h ^ h 16; return (int)(h % (unsigned int)capacity); }这种做法的原理是h ^ h 16把高 16 位的信息扩散到低 16 位两个乘法用的是大质数常量让 bit 之间的互相影响更充分。处理完后再取模无论 key 是正数、负数还是很大的数结果都会均匀分布在[0, capacity)区间内。虽说两数之和的测试用例不至于这么刁钻但把哈希函数写规范了以后你把它抠出来还能用在别的地方。如果追求极致性能因为哈希表容量我会特意设计成 2 的幂取模可以用位运算替代h (capacity - 1)。位与运算比除法快很多这在循环密集的场景下有实际意义。2.3 数据结构定义与内存布局链表法和开放寻址二选一哈希表的冲突处理有两个主流流派链地址法和开放寻址法。链地址法在每个桶下面挂一条链表key 冲突了就链到桶后面开放寻址法不挂链表而是顺着数组往后找空位。我选了链地址法因为它实现直观节点删除和遍历都好写而且不受“装太满”的致命影响只是链表变长性能退化。对应地结构体定义如下typedef struct HashNode { int key; // 数组元素值 int value; // 数组下标 struct HashNode *next; // 指向同桶下一个节点 } HashNode; typedef struct HashTable { HashNode **buckets; // 桶数组元素是指针 int size; // 桶数量 int count; // 已存储节点数 } HashTable;这里的重点理解在于HashNode **buckets的双重指针。buckets本身是一块连续内存每个元素是一个HashNode *这个指针要么是 NULL要么指向一个链表头。分配桶数组时我用calloc因为calloc会把内存清零所有桶初始都是 NULL如果用malloc还要手动 memset 一遍容易漏。2.4 容量规划与扩容机制为什么我建议容量取大一点哈希表的性能受负载因子影响负载因子 节点数 / 桶数。链地址法最简单实用的经验值是把负载因子控制在 0.75 以下超过这个值冲突概率会快速上升。因为两数之和已经知道numsSize最省事的做法是让容量直接满足capacity 2 * numsSize再向上取整到 2 的幂。比如numsSize 5那我至少需要容量 10向上取到 16。这样负载因子最多 0.5冲突很少而且不需要实现扩容逻辑代码干净。如果做可用于更多场景的通用哈希表那扩容逻辑就得保留当count * 10 size * 7即负载因子超过 0.75时新建一个双倍大小的桶数组把所有旧节点重新计算哈希并插入新桶。这一步叫 rehash看起来简单但漏了它哈希表在数据量大了以后会慢到让你怀疑人生。3. 完整代码与逐步拆解3.1 核心函数清单分四层写逻辑才清晰我习惯把代码拆成四块哈希函数、哈希表基础操作创建、销毁、插入、查询、主流程 twoSum、测试用例。这样每个函数都短小精悍出问题也容易定位。整体流程是这样的先根据numsSize算容量创建哈希表然后从头到尾遍历数组对于每个元素nums[i]先查target - nums[i]是否在表里如果在直接返回[查到的下标, i]如果不在把nums[i] - i插入哈希表。遍历完还没找到就返回 NULL并把returnSize置为 0。3.2 初始化与释放malloc 之后必须配对 free我见过太多 C 语言同学写出能跑的哈希表却在内存管理上翻车。初始化一个哈希表的完整代码如下HashTable *ht_create(int capacity) { HashTable *ht (HashTable *)malloc(sizeof(HashTable)); if (!ht) return NULL; ht-buckets (HashNode **)calloc(capacity, sizeof(HashNode *)); if (!ht-buckets) { free(ht); return NULL; } ht-size capacity; ht-count 0; return ht; }注意第二层calloc失败时不仅要把buckets释放掉还要把ht也释放掉否则就内存泄漏了。很多入门教程写代码只检查最后一层失败中间的失败路径全漏了这是坏习惯。销毁函数更要仔细必须遍历每一个桶把链表上的每个节点都 free 掉再释放桶数组本身最后释放哈希表结构体void ht_destroy(HashTable *ht) { if (!ht) return; for (int i 0; i ht-size; i) { HashNode *node ht-buckets[i]; while (node) { HashNode *next node-next; free(node); node next; } } free(ht-buckets); free(ht); }这里的顺序非常重要先保存next再free(node)。如果你先 free 了节点再去访问node-next那就是典型的 use-after-free编译器不一定报错运行起来却可能随机崩溃。3.3 插入与查询的实现两个操作围绕同一个头插法插入操作ht_put的逻辑是先算出哈希桶下标再遍历桶链表。如果链表中已有相同的 key说明插入的是重复元素此时应更新 value 而不是再建一个新节点否则同一个 key 会占两个位置查询时很难保证返回哪个。如果没找到相同 key就新建一个节点用头插法挂到链头void ht_put(HashTable *ht, int key, int value) { int idx hash_key(key, ht-size); HashNode *node ht-buckets[idx]; while (node) { if (node-key key) { node-value value; return; } node node-next; } HashNode *new_node (HashNode *)malloc(sizeof(HashNode)); new_node-key key; new_node-value value; new_node-next ht-buckets[idx]; ht-buckets[idx] new_node; ht-count; }查询操作ht_get和插入前半段几乎一样算下标遍历链表比对 key。找到了就把 value 通过指针参数带出去返回 1没找到返回 0。这里把“是否找到”和“值是多少”分开用返回值表达状态用指针参数带出数据是 C 语言里很常见的接口风格比单纯返回 -1 或 0 要清晰得多。3.4 主流程 twoSum把查和插的顺序反一反就是正确与错误的差别主函数一点也不复杂但顺序是精华int *twoSum(int *nums, int numsSize, int target, int *returnSize) { *returnSize 0; if (numsSize 2) return NULL; int capacity 16; while (capacity numsSize * 2) { capacity 1; } HashTable *ht ht_create(capacity); if (!ht) return NULL; int *res (int *)malloc(2 * sizeof(int)); if (!res) { ht_destroy(ht); return NULL; } for (int i 0; i numsSize; i) { int complement target - nums[i]; int j 0; if (ht_get(ht, complement, j)) { res[0] j; res[1] i; *returnSize 2; ht_destroy(ht); return res; } ht_put(ht, nums[i], i); } ht_destroy(ht); free(res); return NULL; }为什么先查询再插入我再强调一遍因为要保证查询到的下标一定小于当前下标i。如果nums[i]和complement相等比如[3, 3]这种情况遍历到第二个 3 时哈希表里存的第一个 3 的下标还在查询能正确返回[0, 1]如果先插入再查询第二个 3 会把第一个 3 覆盖成 1查询到自己就返回了错误结果。capacity的起点是 16然后不断自我翻倍直到不小于numsSize * 2。这个写法保证了桶数量始终是 2 的幂并且负载因子不超过 0.5。capacity 16的初始值意味着数组长度在 1 到 8 之间时都用 16 个桶避免了频繁扩容。注意while (capacity numsSize * 2)用的是而不是否则当numsSize * 2正好等于 capacity 时还会多扩一次倍白白浪费内存。3.5 测试用例跑一遍不仅测正常输入还要测边界我不会只在 main 里测一个用例就收工至少要覆盖这几类普通用例[2, 7, 11, 15]、重复元素用例[3, 3]、负数用例[-3, 4, 3, 90]、找不到解的情况。测试代码本身不复杂重要的是养成“写完算法先跑边界用例”的习惯。int main(void) { int nums1[] {2, 7, 11, 15}; int returnSize 0; int *res1 twoSum(nums1, 4, 9, returnSize); printf(test1: res [%d, %d]\n, res1[0], res1[1]); free(res1); int nums2[] {3, 3}; res1 twoSum(nums2, 2, 6, returnSize); printf(test2: res [%d, %d]\n, res1[0], res1[1]); free(res1); int nums3[] {-3, 4, 3, 90}; res1 twoSum(nums3, 4, 0, returnSize); printf(test3: res [%d, %d]\n, res1[0], res1[1]); free(res1); int nums4[] {1, 2, 3}; res1 twoSum(nums4, 3, 99, returnSize); printf(test4: res %p (NULL means not found)\n, (void *)res1); return 0; }这里要特别强调free(res1)和 NULL 检查。你从twoSum拿到的结果是在堆上分配的不用了就得 free。在第 4 个用例里找不到结果时函数返回 NULLprintf(%p, res1)不会崩但你如果直接res1[0]就会解引用空指针。真正常用的严谨做法是调用 twoSum 后判断if (res1 ! NULL)再访问数组我在测试代码里省略了是为了示意实操中不要学。4. 实操踩坑实录常见问题与排查技巧4.1 内存泄漏与 use-after-free最容易犯也最难看出来用 C 语言写哈希表内存问题是老大难。我第一次跑通代码时哈希表销毁函数写得特别随意只释放了桶数组没释放每个节点。结果程序跑完内存占用不释放用 valgrind 一查整屏都是 lost records。排查这类问题的经验是顺手就用 valgrind。命令很简单gcc -g -o two_sum two_sum.c valgrind --leak-checkfull ./two_sum看到definitely lost: 0 bytes说明内存全部回收如果有 lost它会精确告诉你是在哪个函数里 malloc 的。我还会把-fsanitizeaddress也加上它能在运行时就报越界和 use-after-free比事后看日志更快定位。老规矩malloc / calloc 和 free 必须成对出现。我在twoSum函数里有三个退出路径找到解返回、没找到返回、参数非法返回。每一个返回之前都要考虑哈希表释放了没有、结果数组释放了没有。这种“多返回值路径下的资源管理”是 C 语言的必修课也是面试官最爱追问的点。4.2 负数键与哈希函数的坑不转无符号就等着崩如果哈希函数写成key % size直接用遇到负数键时会发生什么C 99 之前的行为是实现相关的可能是负数目前的 C 标准里%的符号由被除数决定-3 % 16结果也是负数具体是 -3。拿负数当下标访问buckets[idx]轻则访问到错误位置重则导致段错误。我的解决办法是先用(unsigned int)key转换再参与位运算。无符号整数的运算结果始终是非负的最后再% (unsigned int)capacity得到的一定是[0, capacity)区间内的下标。这样无论原始 key 是-7、-100000还是2147483647都不会发生越界。这个转换的原理说起来也很简单C 语言里无符号整数有自己的一套取模运算规则相当于把负数的二进制补码当成了一个大正数来处理。对于哈希散列来说我们本来就不关心它的数学含义只关心 bit 模式和均匀性所以这种转换是安全的。4.3 重复元素和相同的 key更新还是新建必须想清楚链地址法哈希表里插入时如果发现 key 已经存在是新建一个节点链上去还是更新原节点的 value这个问题我第一次写的时候没细想直接无脑头插结果同一个 key 在链表里出现了两个节点。查询时找到的是哪一个是随链表顺序决定的两数之和的答案就变得不确定了。正确语义应该是更新原节点的 value因为从两数之和的角度看同一个数组元素值只能对应最新的下标遍历到哪个就存哪个。插入时先遍历链表命中了就node-value value; return;没命中才新建节点。这个更新语义在其它哈希表应用里同样重要。比如做词频统计时同一个单词第一次出现 value 1第二次出现应该在原 value 上加 1而不是再插一个新节点。牢记哈希表的语义是 key 唯一value 可覆盖。4.4 性能退化哈希函数不行桶再大也白搭我做过一个很有意思的实验把一个很差的哈希函数比如直接取模capacity 也是 2 的幂应用在一个全是偶数的数组上。假设数组长度是 10000容量是 16384直接key 16383偶数 key 后三位永远是 0结果所有元素都落到 0、8、16……之类的桶里其他桶全是空的链表长度几百上千查找退化成线性扫描。好的哈希函数要做的事情就是把低位的规律性打散。我前面写的那个扰动函数本质就是“雪崩效应”任何一位 bit 的变化经过右移、异或、乘法之后会影响结果的一半以上 bit。这样即使输入是连续的偶数落在桶里的下标也会均匀分布。如果你懒可以用最简单但有效的方式给 capacity 选一个大质数而不是 2 的幂然后用直接取模也能获得不错的分布。只是质数容量没法用位与替代取模速度会略慢。这是空间和时间的权衡看场景取舍。5. 复杂度分析与方案对比这道题还能玩出什么花5.1 复杂度分析从 O(n²) 到 O(n)代价是什么暴力解法的时间复杂度是 O(n²)空间复杂度是 O(1)。哈希表方案把遍历一遍的过程中每次查询和插入的平均耗时都压到 O(1)所以总时间降到 O(n)代价是额外空间 O(n)因为最多需要存储 n 个节点。这里有个细节值得说清楚哈希表的 O(1) 是平均情况不是严格意义的最坏情况。最坏情况下如果所有 key 都撞到同一个桶链表长度是 n查询复杂度退化到 O(n)整体又变成 O(n²)。所以哈希函数的均匀性和容量的合理性不是可选项而是性能安全的保证。我在代码里把容量设为不小于两倍数组长度负载因子压到 0.5 以下配合扰动哈希函数最坏情况在实际测试数据里几乎不可能出现。这是工程思维的体现算法理论上限很重要但你要是真跑一个百万级数组哈希分布好坏直接决定会不会超时。5.2 和其它解法对比排序加双指针、暴力、哈希表排序加双指针是另一种经典思路先把数组排成升序再用两个指针从首尾往中间夹逼寻找目标。它的时间复杂度是 O(n log n)空间 O(1)。相比哈希表它不需要额外内存但不能直接用原数组下标因为排序后下标变了。如果题目返回的是值而不是下标排序解法是个不错的选择。这三种方案适合的场景完全不同我做了一个简单的对比方案时间复杂度空间复杂度是否保持原数组顺序适合场景暴力双层循环O(n²)O(1)是数组很小只为理解题意排序 双指针O(n log n)O(1)否需记录原下标内存受限值而非下标哈希表O(n)O(n)是数组较大笔试面试标准解从刷题和面试的角度看哈希表是默认首选。但懂一点排序解法也有价值因为当面试官追问“如果内存很小怎么办”你能立刻给出降空间的方案这种对比展示比单纯背题更有说服力。5.3 扩展思考从两数之和到三数之和、四数之和把问题扩展一下如果要求返回三个数a b c 0的所有组合怎么办一个通用做法是固定一个数然后对剩下的区间做两数之和。最外层的数用循环枚举内层的两数之和可以用哈希表或双指针。类似地四数之和就是固定两个数再对剩余区间做两数之和。这种扩展题的目的不只是考你会不会套模板而是考你有没有真正理解“如何把一个大问题分解成子问题”。两数之和的哈希表解法在这里的价值是它让你直观体会“查找操作如何从线性变成常数”这种体会放在任何后续题目里都能迁移。哈希表在真实项目里的应用就更多了缓存 LRU、全局唯一 ID 到对象映射、字频统计、数据库索引底层思想、布隆过滤器前置可以说 C 语言开发的很多系统底层都少不了它。5.4 通用化改造让两数之和的哈希表变成你的工具库两数之和的哈希表特化得比较厉害key 和 value 都是 int。如果你希望这套代码能在更多场景用可以考虑三步改造一是把 value 从 int 换成任意类型需要引入void *和比较函数指针二是把容量规划做成自动扩容负载因子到 0.75 时自动翻倍重建三是把哈希函数做成可配置支持字符串 key。这已经不是“两数之和”的范畴了而是写一个你自己的通用哈希表库。我建议有精力的人做一次这样的改造因为 C 语言里任何自带的数据结构都会限制你思考深度而自己写过的哈希表会让你对“查找”这件事的理解彻底不一样。以后再看 Java 的 HashMap、Redis 的 dict你都会发现它们的设计思路和你手写的版本一脉相承。我在实际使用 C 语言实现这个题目时最大的体会是刷题最怕的不是做不出来而是以为自己做出来了。代码跑通给你造成的“我很会了”的错觉往往会在真正考察细节的时候一击即溃。哈希表这道题能不能写得又快又稳基本能反映你对数据结构、内存管理和边界条件的综合把握程度。建议你也亲手跑一遍上面的代码再把负数、重复元素、大数组三个用例测完然后试着改造成通用版本试试手——这个过程比看十篇教程都有用。