刷算法题刷多了会发现一个规律很多题第一眼看上去毫无头绪但只要往哈希表上靠一下代码复杂度就能直接从 O(n²) 掉到 O(n)。哈希表就是这么个不讲道理的东西它用空间换时间把“查找”这个最基础的操作从遍历优化到近 O(1)。这篇就专门聊聊哈希表刷题这件事从底层原理、高频题型、经典题目拆解到 Python 和 C 里各种容易翻车的细节一篇串清楚。适合正在刷力扣LeetCode或洛谷、刚开始接触哈希类题目、或者刷了一堆题但总觉得没形成套路的人。看完你至少能解决一个困惑哈希表到底存什么、什么时候查、为什么有的题用哈希反而更蠢。1. 哈希表凭什么成为刷题效率神器哈希表的底层原理其实一句话就能说透用一个函数把任意键映射到数组的一个下标然后把值存在这个位置。问题是这个看似简单的思路背后藏着三个工程问题哈希函数怎么设计、冲突怎么解决、表满了怎么办。把这些搞明白你刷题时才能真正理解为什么哈希表有时候快有时候反而被卡。1.1 哈希函数、冲突处理与负载因子底层不玄就三件事第一个问题是哈希函数。理想情况是一个键对应一个位置现实是键的范围往往远大于表的大小所以多个键映射到同一个下标是必然的这就叫哈希冲突。解决冲突的常见方案有两种一种是链地址法也就是每个数组下标挂一个链表冲突了就在链表后面追加C 的std::unordered_map就是这思路另一种是开放寻址法冲突了往后找空位Python 的 dict 内部更接近这种方式。刷题时不需要会手写这些但要知道一点冲突越严重哈希表的实际查询性能越差最坏情况下链表退化查找变回 O(n)。第二个问题是负载因子就是表里已存元素数量和桶数量的比值。负载因子超过阈值比如 0.7哈希表就会扩容重新分配更大的数组把旧数据全部重新哈希一遍。刷题时你几乎感知不到这个过程因为语言层面的实现已经帮你处理了但“哈希表会扩容”这个事实意味着如果你提前知道数据规模可以手动指定初始容量减少扩容次数在极大数据量下会快不少。刷题一般不用优化到这一步笔试面试更不会考这个知道即可。第三个问题也是刷题时最常用的视角哈希表到底能用什么当键。这就要引出“可哈希”这个概念。Python 里数字、字符串、元组都可以当键但列表不行因为列表可变它的哈希值会变C 里如果想让结构体或者 pair 当键还得自己写哈希函数。这一块细节多后面第 4 章专门讲但底子在这里先打个底哈希表靠键找值键必须是不可变的、可计算哈希的。1.2 降复杂度视角暴力遍历到哈希查找的思维转变刷题时哈希表最大的价值是把“查找是否存在”从 O(n) 变成 O(1)。这句话看起来简单但很多人做题时想不到去用它原因是大脑习惯了“两层循环”这种最直观的解法。举个例子假设要给一个数组配对满足两数之和等于目标值。最暴力的做法是两层循环枚举所有组合时间复杂度 O(n²)。但如果第一层循环遍历数组时把已经遍历过的数存进哈希表第二层循环就变成了“查目标值减当前数是否存在”整个算法立刻变成 O(n)。这就是哈希表刷题的核心思维用空间记录已经见过的信息避免重复遍历。哈希表存的东西往往是“某个值对应的下标”或者“某个值出现的次数”具体存什么决定了你能不能写出高效解法。后面讲题型时会反复用到这个思维这里先记住一句话哈希表不是用来存答案的是用来存“历史遍历信息”的查询历史才是它最擅长的事。2. 哈希表题目到底考什么五大高频模型哈希表的题看起来五花八门但归纳下来就是五个高频模型。我刷了上百道哈希类题目之后发现只要看到“数组中查找配对”“统计出现次数”“判断重复”“字符串分组”这四类关键词基本可以断定这题是要用哈希表来解的。下面把这五个模型逐一拆开每个都讲识别特征、解题思路和对应典型题。2.1 存在性查重模型哈希集合的拿手好戏这可能是最基础的哈希场景只需要判断某个元素之前有没有出现过。典型题是力扣 217 题“存在重复元素”和 141 题“环形链表”。环形链表这题有点意思遍历链表时把每个节点指针存进集合如果走到一个之前见过的节点就说明有环。这里哈希表存的是“节点地址”不是值这恰好体现了“哈希表存什么都可以”的灵活性。识别这种题非常容易题干里只要出现“是否出现过”“是否存在重复”“判断有没有环”这类字眼第一时间想 set。Python 里直接用一个set就够C 用std::unordered_set。注意一个常见误区查重题只需要存键不需要存值所以用集合而不是映射别杀鸡用牛刀。2.2 频率计数模型字符串题的基本盘如果说查重是判断“出现过没有”那频率统计就是“出现了多少次”。典型题有 242 题“有效的字母异位词”、387 题“字符串中的第一个唯一字符”、383 题“赎金信”。这类题的核心是构建一个“字符或元素 → 出现次数”的映射然后基于计数做进一步判断。写这类题时有个小技巧如果没有特别说明别用 Python 的collections.Counter以外的容器直接用Counter就能完成多数计数学场景。C 则用unordered_mapchar, int遍历一遍字符串填充计数即可。频率模型属于哈希表题里最温和的一类难度不大但它是很多中等题的基础比如后面讲的异位词分组本质就是频率计数的变体。2.3 配对与差值模型两数之和的完整体系这个模型是哈希表刷题里最经典的一类核心思路是遍历过程中算出“当前元素需要和谁配对”然后去哈希表里查这个配对对象是否出现过。最典型的莫过于力扣 1 题“两数之和”扩展题包括 454 题“四数相加 II”和 447 题“回旋镖的数量”。我一开始刷两数之和时也会想为什么不能先把所有元素塞进哈希表再查询后来发现如果数组里有重复元素先存再查很容易出现同一个下标被用两次的 bug正确做法是边遍历边存保证查询时只用到已经出现过的元素。这个“先查后存”的顺序在配对模型里非常重要后面第 3 章会专门展开。另外提一个判断标准如果题目要求“返回两个数的下标”或“统计配对组合的数量”大概率属于这个模型。但如果题目只是问“满足条件的三元组数量”比如三数之和那哈希表反而会带来去重麻烦排序加双指针可能更适合。这就是前面说的哈希表不是任何题的银弹要能判断什么时候不用它。2.4 分组归类模型把键设计成序列化的样子分组模型的特征是要把满足某种特征的元素放到同一组里最典型的就是 49 题“字母异位词分组”。给定一组字符串字母组成相同但顺序不同的分到一组比如 eat、tea、ate 应该在一组。这类题的难点不是数据结构而是“如何设计一个能代表同类特征的键”。异位词有两个常见的键设计一是把字符串排序后的结果当键eat 和 tea 排序后都是 aet二是统计每个字母的出现次数拼成一个 26 位计数串当键。这两种方案的核心逻辑都是“同类元素拥有相同的哈希键”。键设计是哈希表刷题里最考验创造力的一环很多题目从“暴力”到“精妙”的差距本质就是键设计从粗到精的差距。2.5 前缀和与哈希组合模型零基础也能突破的子数组题这可以说是哈希表题里最套路化的一个模型一旦理解了原理就能通吃一大片子数组类问题。代表题是力扣 560 题“和为 K 的子数组”。很多初学者看到这类题第一反应是滑动窗口但注意数组里可能有负数滑动窗口在这里不是万能的。这时需要引入前缀和的概念sum[i]表示数组从开头到第 i 个位置的累加和子数组和等于sum[i] - sum[j]。于是题目转化为遍历数组的每个位置 i 时需要知道之前有多少个前缀和恰好等于sum[i] - k。这个“查询历史前缀和出现次数”的操作就是哈希表的完美应用场景。我们只需要用一个哈希表记录“前缀和 → 出现次数”边遍历边查询、边更新时间复杂度 O(n)。这个模型已经超过青铜段位了但原理其实很好理解一旦吃透很多中等难度的题目都能迎刃而解。3. 经典题目手把手拆解从暴力到哈希的完整推演光讲模型还是虚的我挑四道最典型的哈希表题把从暴力思路到哈希优化的完整过程走一遍。这个部分建议自己跟着代码在脑海里跑一遍理解每个变量存的是什么、什么时候存进去的、什么时候取出来的。这几道题吃透了哈希表刷题的底子就算打牢了。3.1 两数之和一次遍历先查后存题目描述不赘述直接看哈希解法的 Python 实现def twoSum(nums, target): seen {} for i, num in enumerate(nums): need target - num if need in seen: return [seen[need], i] seen[num] i return []C 版本几乎长得一样只是换成了unordered_map#include unordered_map #include vector std::vectorint twoSum(std::vectorint nums, int target) { std::unordered_mapint, int seen; for (int i 0; i nums.size(); i) { int need target - nums[i]; if (seen.find(need) ! seen.end()) { return {seen[need], i}; } seen[nums[i]] i; } return {}; }关键点在于循环内部的顺序先查need是否在哈希表里再把当前元素存进去。为什么要先查后存因为题目要求“每个下标只能使用一次”如果先把当前元素存进去那查询need时如果need num就可能把当前正在遍历的元素两次使用导致错误结果。数组[3, 2, 4]、目标6这个例子最直观先存3遍历到2查4不在哈希表存2遍历到4查2在哈希表返回下标[1, 2]。如果是先存后查遍历到最后一个元素时4自己也会出现在哈希表里逻辑依然能跑对但在数组[3, 3]、目标6时就会出错。这个小顺序就是两数之和哈希解法的灵魂。时间复杂度 O(n)空间复杂度 O(n)。相比暴力 O(n²)哈希表的优势一眼可见。3.2 字母异位词分组排序字符串当键再看分组模型的经典题。Python 实现非常短from collections import defaultdict def groupAnagrams(strs): groups defaultdict(list) for s in strs: key .join(sorted(s)) groups[key].append(s) return list(groups.values())这题的关键是键设计。eat排序后是aettea排序后也是aet所以它们自动进同一组。为什么要用排序串而不是原字符串当键因为排序过程本质上抽取了“字母组成”这个特征把顺序差异抹掉了。如果你追求更优的时间复杂度可以把排序换成 26 个字母计数串统计每个字符串中每个字母出现的次数拼成一个类似1#1#0#...的键。排序方案的时间复杂度是 O(k log k)其中 k 是字符串长度计数方案是 O(k)因为只需要遍历一次并对 26 个位置计数。实际刷题时字符串长度通常很短排序方案代码更简洁也完全够用。但面试时如果被追问优化能说出计数方案会加分。3.3 最长连续序列从序列起点才开始数这道题是哈希表刷题里一个很妙的例子力扣 128 题。给定一个未排序的数组要求找出数字连续的最长序列长度。注意这里不用排序排序是 O(n log n)而哈希解法的目标做到 O(n)。def longestConsecutive(nums): nums_set set(nums) longest 0 for num in nums_set: if num - 1 not in nums_set: cur num length 1 while cur 1 in nums_set: cur 1 length 1 longest max(longest, length) return longest这段代码看似简单但里面的一个判断很容易被忽略只有当num - 1不在集合中时才以num为起点向后数。举例说明数组是[100, 4, 200, 1, 3, 2]集合里包含1, 2, 3, 4, 100, 200。遍历到1时因为0不在集合从1开始数到4得到长度 4。遍历到2时因为1已经在了说明2是某个序列的中间部分如果这时候再向后数一遍算法就退化成了 O(n²)。这个“只从起点开始数”的技巧就是整道题复杂度保持在 O(n) 的关键。另一个细节是必须先转成set。如果直接对原数组nums进行num - 1 not in nums判断每次都是 O(n) 的成员查找整体复杂度会变成 O(n²)。这也解释了为什么刷题时涉及大量存在性查询第一反应就是构建一个集合。3.4 和为 K 的子数组前缀和配哈希一次看懂最后拆一道中等题力扣 560 题。前面说过这题不能用滑动窗口因为数组有负数。解法是把“子数组和等于 k”转化为“前缀和之差等于 k”。公式推导是核心设prefix[i]表示从开头到第 i 个位置的和那么从第 j 个位置到第 i 个位置的子数组和就是prefix[i] - prefix[j-1]。题目要求这个差值等于 k也就是prefix[j-1] prefix[i] - k。所以当我们遍历到第 i 个位置时只需要知道“之前有多少个前缀和等于prefix[i] - k”把数量加到答案里。from collections import defaultdict def subarraySum(nums, k): prefix 0 count 0 seen defaultdict(int) seen[0] 1 for num in nums: prefix num count seen[prefix - k] seen[prefix] 1 return count为什么初始化seen[0] 1因为前缀和为 0 的情况代表空数组这是边界条件。比如数组[1]、k 1遍历到第一个元素prefix 1seen[1 - 1] seen[0] 1答案加 1正好匹配“子数组 [1] 的和为 1”。如果不初始化 0这种从开头开始计数的子数组就会被漏掉。这个边界条件刷题时极容易被忽略但一旦理解前缀和类型题基本就不会再卡壳。4. Python 与 C 刷题差异字典、unordered_map 与自造哈希很多人从 Python 切换到 C 刷哈希题时会遇到各种奇怪的编译错误比如list不能当 key、pair不能存进unordered_map。这些都属于语言细节但刷题时它们会实实在在地卡住你。我两类语言都刷了不少下面把最容易踩的坑集中讲一遍。4.1 Python 的 dict 与 set可哈希是硬门槛Python 里dict 的键和 set 的元素都必须是可哈希的。什么是可哈希简单说对象必须有__hash__和__eq__两个方法并且哈希值在生命周期内不能变化。因此数字、字符串、元组都可哈希列表不可哈希。刷题时最容易碰到的坑有这几个第一不要直接用列表当键。如果想用两个数组成的 pair 作为键请换成元组例如(x, y)而不是[x, y]。第二如果自定义了一个类作为键一定要同时实现__hash__和__eq__否则 dict 无法正确判断键是否相等。多数刷题场景用元组就够了。第三Python 3.7 之后 dict 保持插入顺序这不是 bug也不影响哈希表复杂度只是有些题目如果需要“按第一次出现顺序输出”这个特性反而能帮到你比如“第一个唯一字符”这类题。还有一个值得说的小知识点defaultdict和Counter是刷题高频工具。defaultdict(int)可以免去检查键是否存在的烦恼Counter则能一键完成频率统计。但注意Counter的底层就是 dict如果你只是判断存在性不要无脑用Counterset就够了更省空间。4.2 C 的 unordered_map从 pair 键到自定义哈希C 的std::unordered_map默认只支持哈希内置类型比如 int、string、char。如果你想把std::pairint, int或者自定义结构体当键标准库没有提供现成的哈希函数编译会直接报错。这时候需要自己写一个哈希仿函数。下面是一个简短的示例#include unordered_map #include utility struct PairHash { size_t operator()(const std::pairint, int p) const { return std::hashint{}(p.first) ^ (std::hashint{}(p.second) 1); } }; std::unordered_mapstd::pairint, int, int, PairHash mp;这里用了异或加移位的方式把两个 int 的哈希值混合成一个。刷题时绝大多数情况不需要想得太复杂这个写法够用。但要注意一个小陷阱如果你用一个可变对象作为键比如结构体里有指针而且之后修改了它哈希值就变了查询会失败。刷题时尽量用值类型作键别在存进去之后偷偷改。另一个 C 特有的坑是迭代器失效。在遍历unordered_map的过程中如果插入新元素导致扩容之前拿到的迭代器可能全部失效。刷题时如果需要边遍历边插入常见做法是先记录需要插入的内容遍历完再统一插入或者使用索引而不是迭代器。4.3 哈希表 vs 字典到底有什么区别很多人会把“哈希表”和“字典”当成同一个东西包括我在内刚学的时候也混着叫。严格来说字典Map是一种抽象数据结构描述的是“键到值的映射关系”哈希表Hash Table是实现这种映射关系的一种具体方法。字典也可以用平衡树来实现比如 C 里的std::map就是红黑树实现的它有顺序但查找是 O(log n)std::unordered_map才是哈希表实现平均 O(1) 查找但无序。Python 的 dict 本身基于哈希表实现所以日常语境里把 dict 叫成哈希表也没大问题。维度字典 / Map哈希表 / Hash Table本质抽象数据结构键到值的映射具体实现方法数组加哈希函数实现方式举例Python dict、C std::map、Java TreeMapPython dict 底层、C std::unordered_map、Java HashMap有序性可能有序树实现可能无序哈希实现通常无序Python dict 保留插入序是特殊细节查找复杂度取决于实现平衡树 O(log n)平均 O(1)最坏 O(n)刷题选型建议需要有序遍历时用std::map绝大多数情况选哈希实现刷题时这个区别的意义在于如果你需要按顺序遍历键比如要求输出“按字典序排序后的结果”std::map就比unordered_map方便如果只追求查询速度哈希实现才是首选。搞清楚这一点不同语言里选容器就不会犹豫了。5. 刷题节奏、调试技巧与避坑清单哈希表题小而灵活但正因为实现太自由最容易看别人题解秒懂、自己一写就崩。最后这部分把常见问题、调试技巧和刷题方法论整理成清单形式日常参考价值很高。5.1 三个高频翻车现场第一个翻车现场遍历字典时修改字典。Python 里直接在 for 循环中删除或新增 dict 元素会出现运行时错误。比如# 错误示范 for key in d: if d[key] 0: d.pop(key)正确做法是遍历一份键副本for key in list(d.keys())或者用字典推导式重建。第二个翻车现场可变键。这个前面已经提过核心原则是放进哈希表后不要修改键。Python 里用列表当键会直接报TypeError: unhashable type: listC 里则是返回 false 或者行为未定义。第三翻车现场默认值处理不当。查询哈希表时如果键不存在两种语言处理方式不同C 的mp[k]会默认插入一个零值并返回引用这很隐蔽如果你只是“想查一下有没有”用了mp[k]就会莫名其妙往表里塞一个空键。C 里查存在性用find或count别用[]。5.2 能用数组替代哈希的场景小范围键不要杀鸡用牛刀哈希表虽然好用但有一个常被忽略的平替当键的取值范围很小时直接用数组存比哈希表快得多。最典型的场景是处理小写字母。很多字符串题都限定只包含 26 个小写字母这时可以用int[26]用char - a作为下标。同理ASCII 字符范围内用int[128]数字范围有限时用数组计数。为什么数组更好因为数组连续内存、零哈希冲突、零扩容开销访问一个位置的耗时比哈希表小一个量级。我实测过同样一道“判断两个字符串是否为字母异位词”的题在数据量极大时int[26]方案比unordered_mapchar, int快出不少。刷题时先问自己一句键的范围有限吗如果有限优先数组。这个话题在优动漫 c 的题解评论区经常被反复提起确实是高频考点。5.3 哈希题怎么刷才高效题型归档与复刷策略聊一下方法论。很多新手刷力扣喜欢按题号从 1 开始按顺序刷这其实效率不高。哈希表题建议按题型归档刷比如分五类查重、计数、配对、分组、前缀和。每类先挑 2 到 3 道经典题吃透再把同类的新题往模板上套。一个比较有效的学习路径是先把力扣 1、217、242、49、128、560 这几道基础哈希题做完再对照题解总结每道题“哈希表存了什么”。你会发现存的无非是“下标、次数、布尔值、键分组”就这四种东西没有更多了。刷的时候我建议动手写“暴力版”和“哈希版”两个版本。先写暴力版确认思路正确再写哈希版感受复杂度怎么降下来的。这个过程能帮你把“什么时候该用哈希”的直觉练出来。遇到实在不会的题可以翻算法笔记类的资料比如 labuladong 的刷题笔记或者洛谷的题单但看完一定要能自己默写一遍否则很容易陷入“看懂了合上书就不会”的困境。5.4 哈希表刷题常见问题速查表问题原因解法Python 报 TypeError: unhashable type: list列表不可哈希改用元组自定义类需实现__hash__C 编译报错pair 和结构体无法作为 unordered_map 键标准库未提供对应哈希函数自定义哈希仿函数遍历 dict 时删除元素报 RuntimeError迭代过程中改变表的大小遍历键副本或放在循环外统一处理空间占用太大内存超限无脑哈希没有利用键范围有限的条件小范围键优先用数组 / 位图哈希表查询但mp[k]后表悄悄变大Coperator[]会自动插入默认值存在性查询用find或count明明用了 set 去重复杂度还是高对原列表反复做 in 判断先构建 set再对 set 做存在性查询哈希冲突导致特定数据下非常慢极端输入下哈希退化最坏 O(n)换用平衡树实现如 std::map或自定义更好哈希这套速查表是我自己踩坑总结出来的不少问题在面试或者 OJ 提交时出现过。尤其最后一条有些 OJ 的测试数据会刻意构造哈希冲突来卡unordered_map如果发现自己写的哈希题频繁超时不要只怪常数太大有可能是输入数据针对默认哈希函数做了攻击这种情况换成std::map往往能稳定通过。最后再分享一个小经验。哈希表刷题重点从来不是背代码而是想清楚每次存进去的是什么、在什么时候取出来。两数之和存的是“补数的下标”560 题存的是“前缀和的出现次数”异位词分组存的是“排序串对应的字符串列表”。只要这三个“存什么”想明白了哈希表这套东西基本就通了。多做几道你会发现哈希表真的就是一把万能的扳手但用得好的关键是知道该拧哪颗螺丝。