哈希表Day6part01——如果你也在一轮轮啃算法训练营的进度这四个字应该不陌生。终于我们从数组、链表、双指针这些线性结构走进了“以空间换时间”的经典领域。哈希表是算法面试里性价比极高的一块概念不复杂代码模板固定刷题见效快。这套课的定位是哈希表入门第一讲核心就两件事什么时候用哈希结构以及数组、HashSet、HashMap之间怎么选。把这四道经典题吃透——有效的字母异位词、两个数组的交集、快乐数、两数之和——后续再遇到哈希相关题目基本就是套模板。这份笔记是我自己带训练营复盘时整理的完整版。除了每道题的思路和代码还写了不少我在实际刷题和带学员时反复踩过的坑。如果你正在准备校招、跳槽或者单纯想把算法基础打牢这一篇值得认真看完。1. 哈希表基础先想清楚它到底解决了什么问题1.1 为什么要用哈希表从“翻箱倒柜”说起数组要查找一个元素通常只能从头扫到尾平均时间复杂度O(n)。链表更慢要找一个值必须沿着指针一个个next。倒不是说数组和链表一无是处它们的优势在插入顺序、内存连续、动态长度这些方面。可一旦场景变成“频繁判断某个值是否存在”“统计某个值出现了几次”“查找某个键对应的信息”线性扫描就是浪费。哈希表解决的核心问题就是把“查找”从“逐个比”变成“直接去”。打个比方快递驿站如果没有货架编号你要找一件包裹只能翻遍所有箱子如果有编号区间快递员告诉你“B区07号”你直接走到对应位置就行。哈希表干的事就是给每个元素算出一个“编号”存储时按编号放查找时按编号取平均复杂度几乎O(1)。很多训练营前几天的内容比如链表反转、双指针是在训练你怎么“走完一条路”。哈希表则是训练你“别走直接跳过去”。这种思路转变是Day6真正要练的东西。1.2 哈希函数是怎么把数据映射到位置的哈希函数本质上是一段映射规则输入任意数据输出一个固定范围内的数字。在编程语言内置的HashMap或HashSet里这个映射规则已经封装好了你不需要自己写。但底层仍然在做三件事计算哈希码、压缩到桶范围、在桶内查找。有两个基础概念必须知道一是哈希冲突。两个不同的key算出了同一个下标就会撞车语言内部会处理Java里HashMap用的是链地址法加红黑树优化Python的dict也做了类似处理。二是因为存在冲突所以哈希表的查找是“平均O(1)”不是“严格O(1)”。极端场景下大量冲突退化成链表遍历复杂度最差O(n)。对刷题来说99%的情况都不用担心这个但面试官问“哈希表时间复杂度为什么是O(1)”时你要能接住这两个概念。1.3 数组、HashSet、HashMap怎么选一张表理顺很多新手看到“哈希表”三个字就只想到HashMap其实哈希思想包含三种常用结构。选错了结构代码也能写出来但可能多开一倍的变量或者多绕几步逻辑。我在训练营里反复强调选择逻辑可以浓缩成一张表场景推荐结构原因数据范围已知且较小26个字母、0~1000的数字数组下标就是哈希值最快最省空间只判断“是否存在”不关心下标和次数HashSet天然的“集合”语义去重方便需要存键值对比如值→下标、字符→频次HashMap既能判断存在又能取出关联信息训练营part01的四道题刚好把这三种结构各用了一遍字母异位词用数组数组交集用HashSet快乐数和两数之和用HashMap。一次课下来三种结构的适用场景基本就清楚了。1.4 哈希表不是银弹理解它的边界哈希表也不是万能药。如果题目要求保持输入序列顺序、要求输出所有排列组合、要求在连续内存上做某种运算哈希表未必合适。它最大的代价是空间所谓“空间换时间”就是用额外存储换取查找速度。所以刷题时要先问自己我想加速的是哪个操作这个操作是查找、去重、统计还是映射想清楚需求再选结构。训练营前四天学的双指针、滑动窗口很多场景依然有不可替代的价值不是说学了哈希就把前面全丢掉。2. 第一题有效的字母异位词——数组当哈希表的入门课2.1 题目拆解什么叫字母异位词题目内容很直白给定两个字符串s和t判断它们是不是字母异位词。字母异位词的意思是两个字符串包含的字母种类相同每种字母的数量也相同只是排列顺序可能完全不同。经典例子就是“anagram”和“nagaram”字母一样顺序打乱。拆解成三个判断点第一两个字符串长度必须相同否则字母数量不可能对得上第二字符种类必须完全一致第三每种字符出现的次数必须完全一致。这三个点缺一不可。很多同学第一次做这道题时只想到“统计字母个数然后比较两张表”这个方向是对的但没人告诉他可以只用“一张表”通过加减法搞定这正是这道题的精髓。2.2 先想到的笨办法排序后比较最容易想到的解法是把s和t分别转成字符数组排序再比较两个数组是否相等。字符串长度n时排序复杂度O(n log n)空间取决于语言实现。这个解法能过测试思路也完全正确。但面试官大概率会追问一句“能不能优化到O(n)”这就是哈希表的入场点。排序解法还有一个隐藏问题它把“判断两个字符串是否包含相同字符集合”变成了“判断排序后的序列是否相同”逻辑没问题但一旦题目条件改成“不区分大小写”“只统计字母不统计数字”等变体排序解法会立刻变质。哈希表解法却很容易扩展。2.3 哈希思路用一张“打卡表”同时处理两个字符串核心思路是维护一个长度为26的数组下标0~25对应a到z。遍历s时每遇到一个字符就在对应下标上1表示“s里这种字母多了一个”遍历t时在对应下标上-1表示“t里这种字母多了一个”。如果最终数组里所有值都是0说明s多出来的每一个字母都被t里相同的字母抵消掉了字符种类和数量完全一致。用生活类比解释假设两个人都往同一个筐里放水果A每放一个苹果记1B每放一个苹果记-1。最后筐为空说明B拿走的苹果种类和数量和A放进来的完全一样。这就是字母异位词的直观版本。public boolean isAnagram(String s, String t) { if (s.length() ! t.length()) { return false; } int[] table new int[26]; for (int i 0; i s.length(); i) { table[s.charAt(i) - a]; table[t.charAt(i) - a]--; } for (int count : table) { if (count ! 0) { return false; } } return true; }代码里最关键的两个细节一是s.charAt(i) - a字符相减得到的就是0到25的下标这是字符转数字的常用技巧二是两个遍历放在同一个循环里因为已经限定了长度相同可以同时处理两条字符串比先遍历s再遍历t更简洁。2.4 为什么使用数组而不是HashMap很多同学第一反应是用MapCharacter, Integer统计频次。这样当然能过但性能上没优势代码也长一些。原因在于题目明确限制了“只有小写字母”范围固定在26个。数组的天然优势是下标本身就是哈希值直接通过字符计算下标一步到位没有HashMap的哈希计算、装箱拆箱、equals比较的开销。刷题过程中希望大家养成一个条件反射数据范围是什么如果范围是已知且可数的优先考虑数组当哈希表。这道题的范围是26个字母数组长度26就够后面遇到“元素值在0到1000之间”的题目数组长度1001也是一个道理。数组当哈希表其实是用“下标”代替“哈希函数”最朴素也最稳定。2.5 复杂度分析与扩展思路时间上一次遍历O(n)一次数组检查O(1)总复杂度O(n)。空间上固定数组长度26O(1)。与排序法的O(n log n)相比提升了一个量级。这道题的扩展版本也很常见如果输入不仅仅是小写字母而是任意Unicode字符数组长度就无法确定了这时候要改用MapCharacter, Integer思路完全一样只是把“数组”换成“字典”。能讲出这两种实现的切换理由面试官会觉得你是真的理解问题而不是背模板。3. 第二题两个数组的交集——HashSet去重与集合语义3.1 题目拆解理解“唯一”和“顺序不限”很重要题目如下给两个整数数组nums1和nums2返回它们的交集。输出结果中的每个元素必须唯一顺序不限。两点需要注意“唯一”意味着结果要做去重就算原数组里3出现了十次交集中3也只能出现一次“顺序不限”意味着我们不需要维护元素的相对位置这让Set解法成为天然选择。这题不像字母异位词有严格的字符范围限制数组元素可能是任意整数所以不能用固定长度的数组当哈希表要用HashSet。HashSet的核心语义就是“集合”元素无重复、判断contains非常高效。用它来做交集一条主路走到底。3.2 不用HashSet的翻车现场有一个新手解法很容易想到把两个数组都排序然后用双指针同时扫描遇到相同元素就加入结果。思路有道理但实际写起来很痛苦。双指针遇到连续重复元素时必须跳过重复值否则结果里会出现重复数字。为了跳过重复又需要额外的while循环边界条件稍不注意就数组越界。我上一期训练营就有个A同学用双指针写了半小时代码三四十行最后测试还差几个用例没过。换成HashSet之后十行代码解决问题。这不是说双指针不好而是这个场景下它不够“匹配”。题目已经告诉你结果元素唯一那选一个天生去重的结构才是最省力的。3.3 HashSet标准解法两个Set各司其职标准解法分三步第一步遍历nums1把所有元素放入HashSet set1顺便完成去重第二步遍历nums2如果set1中有当前元素说明它是交集的一部分把它加入resultSet这里的resultSet也是HashSet用来避免交集本身重复第三步把resultSet转成int[]数组返回。public int[] intersection(int[] nums1, int[] nums2) { SetInteger set1 new HashSet(); for (int num : nums1) { set1.add(num); } SetInteger resultSet new HashSet(); for (int num : nums2) { if (set1.contains(num)) { resultSet.add(num); } } int[] result new int[resultSet.size()]; int index 0; for (int num : resultSet) { result[index] num; } return result; }这里需要解释一个初学者容易懵的点为什么需要两个Set第一个Set用来去重原数组中的元素让“是否出现过”的判断不受重复影响第二个Set用来去重交集结果。如果把两个职责混在一起比如只用一个set1遍历nums2时发现元素在set1里就直接加入结果数组那如果nums2本身有重复元素结果数组就会重复。这就是“唯一”两个字逼出来的细节。3.4 隐藏进阶如果数字范围很小呢这道题其实有一个很常见的变体如果题目改成“数组中的元素值在0到1000之间”那就可以放弃HashSet改用布尔数组当哈希表。长度为1001的boolean数组遍历nums1时把下标位置标记为true遍历nums2时检查对应下标是否已经标记。这个思路和字母异位词完全一脉相承。为什么数组方案更好因为它是纯下标的随机访问没有哈希运算、没有碰撞问题、也没有Integer装箱的开销。在数据量极大但值域很小的场景下数组方案的时间和空间表现都比HashSet更稳定。训练营里做这道题目的之一就是让你记住看到“值域有限”四个字第一反应应该是数组而不是Map或Set。3.5 复杂度与后续题目的隐藏联系时间复杂度O(mn)两个数组各遍历一次。空间上最坏情况是较小的那个数组的所有元素都存入SetO(min(m, n))。这道题做完后续你还会遇到“两个数组的交集II”那道题要求结果统计重复次数需要用HashMap记录频次而不是HashSet。区别就在“要不要统计个数”上一遍下来集合和映射的边界会非常清楚。4. 第三题快乐数——哈希表检测“死循环”4.1 题目拆解什么时候停下是关键快乐数的定义大家应该都看过对一个正整数每一次将该数的每位数字平方后求和得到一个新数。反复执行这个过程如果最终能变成1那这个数就是快乐数如果陷入一个不包含1的循环永远无法变成1那它不是快乐数。举一个例子19是快乐数1²9²828²2²686²8²1001²0²0²1成功收敛到1。而2不是快乐数2²44²161²6²373²7²585²8²898²9²1451²4²5²424²2²202²0²4注意看4又出现了进入循环。这道题初看很简单就是一个while循环不断算平方和。难的是循环什么时候终止如果只用while(n ! 1)那遇到非快乐数会永远算下去直接死循环。真正要解决的核心问题就是“怎么判断这个数已经出现过”。而“判断某个值是否出现过”正是哈希表最舒适的应用场景。4.2 用HashSet记录历史状态检测循环思路是这样的用一个HashSet保存所有出现过的数。在while循环里反复操作如果当前数等于1直接返回true如果当前数已经出现过了说明进入了循环返回false否则把当前数加入HashSet然后计算下一轮的平方和。为什么判断“已经出现过”就能证明不是快乐数因为这个变换过程是确定性的同一个数每次算出的下一个数完全相同。一旦一个数重复出现后续的序列会和上一轮一模一样永远不可能跳出这个环也永远到不了1。public boolean isHappy(int n) { SetInteger seen new HashSet(); while (n ! 1) { if (seen.contains(n)) { return false; } seen.add(n); n getNext(n); } return true; } private int getNext(int n) { int sum 0; while (n 0) { int digit n % 10; n / 10; sum digit * digit; } return sum; }getNext这个函数要单独抽出来因为主循环里需要反复调用。计算平方和的常见写法是对n不断取余和整除先把个位数取出来再加到sum里然后去掉个位直到n变成0。这个写法很基础但一定要熟练快乐数的后续变体题里还会用到。4.3 为什么不能直接循环100次或1000次有人会想到一个“偷懒”办法让循环最多跑100次超过就说明不是快乐数。测试用例可能能过但这个解法是脆弱的因为循环的长度不是固定的不同数字进入循环的步数完全不同而且题目没有保证数字范围。100次上限没有理论依据万一测试数据需要101步才走到1你的解法就错了。使用HashSet才是最通用、最符合题目本质的判断方式。这道题的价值在于它教会你一个重要的思维模型当问题描述中反复出现“不断变换”“最终会变成”“一旦重复就永远重复”这类字眼时本质上是在考“环检测”。哈希表可以记录访问历史快慢指针可以在O(1)空间下检测环。面试中我会建议先写HashSet版本因为它逻辑最直观如果面试官追问“能不能优化空间”再引出快慢指针思路。4.4 一个让人安心的细节计算过程中数字不会无限变大有人可能会担心这个平方和过程会不会越算越大导致int溢出有一个已知的事实是快乐数计算过程中数值会收敛到某个范围内不会无限膨胀。简单估算一下一个十位数每位最大是9平方和最多约810远小于原数一个一位数变成平方和后最多81。事实上在进入判断循环时数字很快会掉到几百以内。所以int完全够用不用使用long。5. 第四题两数之和——HashMap存储“历史下标”5.1 题目拆解几乎每场算法面试都会见面的老朋友两数之和这道题给定一个整数数组nums和一个目标值target请在数组中找出和等于目标值的两个整数返回它们的下标。题目保证只有一组答案且同一个元素不能使用两次。这道题的经典程度不必多说几乎所有训练营都会把它放到哈希表part01它也是最适合讲清楚“为什么需要HashMap”的题目。表面能看出两个信息要返回下标所以不能只判断存在还要能取出位置数组元素可能有负数、有重复值各种边界情况都要cover。很多人第一次看完题解觉得不难但真正自己写的时候最容易在“先存map还是先查map”这个细节上栽跟头。5.2 暴力解法的问题在哪里最直观的解法是双重循环外层固定一个数内层遍历它后面的所有数判断两个数的和是否等于target。时间复杂度O(n²)空间O(1)。如果数组长度是10⁴最坏情况下要执行约5000万次比较跑起来明显吃力。更关键的问题是每次内层循环都在重复“查找target - nums[i]等于什么”这件事完全没利用外层已经遍历过的信息。哈希表优化的本质就是把内层循环的“查找”从O(n)的线性扫描变成O(1)的哈希查找。你不需要再从数组开头找只需要看一眼这个“补数”之前有没有出现过。5.3 标准解法边查边放用HashMap记录“来时的路”核心思路一句话遍历数组时先把之前处理过的数字和下标放进HashMap然后在每一轮查找当前数字的“补数”是否已经在map里。如果在就找到了答案如果不在就把当前数字和下标放进去继续往后走。public int[] twoSum(int[] nums, int target) { MapInteger, Integer map new HashMap(); for (int i 0; i nums.length; i) { int need target - nums[i]; if (map.containsKey(need)) { return new int[]{map.get(need), i}; } map.put(nums[i], i); } return new int[0]; }代码看起来很短但每一步都有讲究。为什么要“边查边放”因为这样可以保证map里的元素全部是当前下标之前的“历史元素”查找补数时不会把当前元素自己当作答案。比如nums[3, 2, 4], target6遍历到i0时need3map为空于是put(3, 0)到i2时need2map中有2吗没有于是put(2, 1)不是其实遍历到i1时nums[1]2need4map没有4put(2,1)到i2时nums[2]4need2map里面有key2且下标是1返回[1,2]。这个计算过程完美避开了同一元素复用的坑。5.4 最常见错误先把所有数据放进去再查找新手很容易写成两步走第一次遍历把全部nums[i]和下标i放入map第二次遍历再查找target - nums[i]。这样做的最大风险是当target恰好是某个数的两倍时会把同一个元素用两次。例如nums[3, 2, 4], target6如果先全部放入mapkey为3的下标是0。第二次遍历到i0时need3map.get(3)返回0答案变成[0,0]这明显不对用了同一个元素两次。更糟糕的是如果数组里有两个3后放的会覆盖先放的答案的下标又变得不可预测。所以标准解法坚持“边查边放”map里永远只保存已经处理过的元素这就是避免复用的安全锁。5.5 一个容易忽略的边界重复值会覆盖下标吗如果数组是[3, 3, 4]target6会不会有问题走一遍过程i0时need3map为空put(3, 0)i1时need3map里key3的下标是0找到了返回[0,1]。这里没有触发覆盖问题因为在把第二个3放入map之前已经先查完了查到了就直接返回。所以重复值是安全处理的。但如果题目要求返回所有满足条件的结果对而不是“只有一组答案”那就需要换一种策略先按值分组记录所有下标再做配对还要注意不能重复使用同一个下标的组合。那是另一道扩展题part01阶段只需要掌握标准解法即可。5.6 为什么是HashMap而不是HashSet因为题目要返回下标HashSet只能判断某个数字是否存在取不出它的索引。HashMap的key存数字value存下标把“存在性判断”和“位置访问”两件事一次搞定。这个区分非常重要以后做题只要发现“判断完还要拿到关联信息”第一反应就应该是HashMap。训练营里有同学问能不能用数组排序加二分法做两数之和当然能但排序会打乱原数组的下标必须额外记录原始位置复杂度也不占优。哈希表几乎是这道题的最优解。6. 常见问题与实战心得6.1 数组、Set、Map速查表训练营到这期大家已经开始接触好几道不同结构的题目了我整理了一张速查表后面做题时可以直接对着选题目需求推荐结构常用操作元素值域有限26个字母、0~1000数组下标访问O(1)只判断存在、结果需要去重HashSetcontains / add需要键值对应关系HashMapget / put / containsKey统计字符频次HashMap或数组getOrDefault / merge需要顺序又需要去重LinkedHashSet额外维护插入顺序记住一个原则能用数组就别开Map能用HashSet就别开HashMap。结构和需求越匹配代码越短越不容易出错。6.2 五个容易踩的坑第一个坑字母异位词只遍历s做统计忘了遍历t做抵消最后拿两张表比较也能做但容易在长度判断上遗漏。建议直接用加减法一步到位。第二个坑数组交集只用一个Set结果数组出现重复元素。这是因为忘记了nums2本身可能有重复正确做法是再用一个Set存结果。第三个坑快乐数while循环没有终止条件一直算到超时。记住“重复出现就是退出信号”。第四个坑两数之和先全存后查找同一元素被使用两次。解决方法是边查边放别偷懒。第五个坑混淆HashMap和HashSet的用途。比如返回下标用HashSet结果取不到位置或者统计次数用了Set导致丢失频次。这个坑听起来低级但我在带训练营时几乎每期都能见到。6.3 一个值得背下来的模板哈希表part01学完之后其实可以提炼出一个万能模板。判断是否存在用Set需要存储关联数据用Map数据范围固定优先开数组。模板不是死代码而是“看到题目后自动化产生选型”的思维路径。做题时先问自己需要存什么需要查什么返回什么三个问题回答完结构就定了。6.4 训练营式复盘流程每天20分钟巩固我个人的习惯是每天晚上用20分钟做复盘训练营所有题都可以套这个流程第一步不看代码把题目翻译成数据结构需求第二步写出暴力解并分析复杂度第三步想清楚哈希优化的点在哪里第四步对照自己的代码和标准模板找差异。四道题花费20分钟是够的但收获往往比闷头刷十道新题更大。算法训练营的速度很快不复盘容易忘特别是哈希表的“选型思维”很多同学隔两天就又退回到“拿到题就遍历”的老路上了。最后再分享一个我自己带训练营的心得哈希表part01这四道题价值不在题本身而在于建立一种条件反射。看到“查找”“去重”“统计次数”“记录状态”这些关键词脑子里立刻蹦出哈希结构。这种感觉不是看出来的是写出来的。我上一期带学员复盘时有个同学A跟我说前五天总觉得题目之间是孤立的Day6把四个题刷完突然发现所有题都在做同一件事把遍历过的信息存下来供后面的查询使用。这个顿悟比任何模板都值钱。后续再学哈希表的进阶用法比如分组统计、滑动窗口配合HashMap、设计LRU缓存其实都是在这个基础上做加法。