刷完数组和链表之后，我第一次真正感受到“数据结构”四个字的分量，就是在哈希表这一天。Day5这个专题安排得很实在：242题看起来是字符串题，实际上在教你用数组手写哈希表；349题直接把Set推到台前；202题表面是数学游戏，核心却是循环检测；1题更是各大厂笔试里翻来覆去考的经典模板。这篇就把这四道题一次性讲透，顺便把数组、Set、Map三者到底怎么选这件事说明白。适合刚开始学哈希表的同学，也适合刷了不少题但总在“用不用哈希、用哪种哈希”上纠结的老手。
1. 哈希表基础：先搞清楚数组、Set、Map怎么选
1.1 什么时候该想到用哈希表
哈希表的本质是一个“映射关系”：给我一个键，我能在接近O(1)的时间里找到对应的值。你不需要关心这个键存不存在一个有序的结构里，也不需要去遍历整个集合。日常最典型的场景，就是“判断某个元素是否出现过”和“统计某个元素出现的次数”。
拿生活打比方，你找一本书不需要从书架第一本翻到最后一本，而是先去检索系统查索书号，再直奔那个位置。哈希表干的就是这个事。刷题的时候，只要题干里出现“是否出现过”“是否重复”“统计次数”“找到匹配项”这类字眼，第一反应就应该是：能不能用哈希表把复杂度降下来。
我自己的经验是：当你发现自己写了两层循环，并且外层循环每个元素都去内层循环“找”什么东西，大概率就可以考虑哈希表了。一层遍历负责读数据，哈希表负责记忆，另一层查找就变成了O(1)级别，整体从O(n²)降到O(n)。
1.2 数组、Set、Map三种结构的适用场景
很多人一听到哈希表，就默认等于HashMap。其实在算法题里，有三种“哈希思想”的工具，合理选择能让时间和空间都省不少。
数组是最容易被忽略的哈希表。它本质上就是一个键为“连续下标”的映射表，访问任意下标都是O(1)。当你的键是有限范围内的整数或字符，用数组做哈希是最快的选择。比如统计26个小写字母的出现次数，直接开 int[26]。
Set适合“去重”和“判断是否出现过”，只用键，不需要存值。判断一个元素在不在集合里，就是它的主场。Map则不仅需要判断，还要把值和键一起存下来，比如“元素值→下标”“字符串→出现次数”。
三者本质都是哈希结构，差别在于：数组的下标范围固定且紧凑，Set只存键，Map存键值对。选择顺序也很清楚：如果键能映射成较短的连续下标，优先数组；如果只关心存在性，用Set；如果要同时记录额外信息，用Map。
1.3 哈希冲突和“平均O(1)”的真实含义
哈希表能实现O(1)查找，前提是哈希函数把不同键均匀映射到不同桶。但不可避免会出现两个键映射到同一个桶，这就是哈希冲突。工程上处理冲突常见两种方式：拉链法和开放寻址法。标准库里的实现早就把这些封装好了，刷算法题时几乎不需要自己写冲突处理。
但理解冲突很有用，因为它解释了为什么哈希表的O(1)是“平均情况”。极端情况下所有键都冲突，查找会退化成O(n)。这也是为什么实际工程里，哈希函数的设计和负载因子的控制很重要。刷题时你不用过度担心退化问题，但心里要清楚：哈希表的强大来自概率平均，不是严格保证。
2. 242. 有效的字母异位词：数组版哈希表入门
2.1 题意分析与“异位”的本质
题目要求判断两个字符串是否是字母异位词，也就是两个字符串中每个字符出现的次数是否完全相同。比如“anagram”和“nagaram”，字母种类一样，每种字母的个数也一样，只是排列顺序不同。
这道题最直观的误区是先排序再比较：return sorted(s) == sorted(t)。代码确实简单，但时间复杂度是O(n log n)，而且没有体现任何哈希思想。实际上“异位词”的本质是频次统计，字符的取值范围又是确定的（题目通常限定小写字母），这就是典型的数组哈希题。
我在第一次做这道题时，下意识用了Map统计两个字符串的次数再比较。后来发现用两个Map虽然能过，但数组方案明显更干净。键是26个小写字母，本身就是连续整数下标，根本没有必要引入Map的哈希函数计算和冲突处理成本。
2.2 完整解法与代码实现
核心思路：维护一个长度为26的数组，下标对应字母的偏移量。遍历第一个字符串时，对应位置加1；遍历第二个字符串时，对应位置减1。如果最终数组所有位置都是0，说明两个字符串的频次完全相同。
def isAnagram(s: str, t: str) -> bool: if len(s) != len(t): return False count = [0] * 26 for ch in s: count[ord(ch) - ord('a')] += 1 for ch in t: count[ord(ch) - ord('a')] -= 1 return all(x == 0 for x in count)为什么用ord(ch) - ord('a')而不是直接用ord(ch)？因为字母a的ASCII码是97，如果直接用它当下标，数组需要开到122以上，中间97个位置全是浪费。做索引时先减掉基准值，让下标从0开始，既节省空间，也让数组长度和字母表长度一一对应。
2.3 几个容易忽略的实现细节
第一，很多题解会先判断两个字符串长度是否相等。这个剪枝很重要：长度不等直接返回False，省去后面所有遍历。虽然不判断也不会出错（最终数组不会归零），但这是一个好的编码习惯。
第二，如果题目扩展到包含大写字母、数字甚至Unicode字符，数组长度就不再是26，可能需要扩展到128或256，或者干脆改成Map。判断依据还是看键的范围是否紧凑。这也是为什么面试时，面试官经常会追问“如果字符集很大怎么办”。
第三，all(x == 0 for x in count)这一步虽然优雅，但会额外遍历一次数组。如果追求极致性能，可以再加一个计数变量，在遍历t的过程中记录“当前非零位置的数量”，但数组长度只有26，这点性能差异可以忽略。我建议以代码可读性优先。
3. 349. 两个数组的交集：Set天然自带去重
3.1 题目要求与边界条件
题目给两个数组，要求返回它们的交集，且结果中的每个元素必须是唯一的，不考虑输出顺序。难点不在“求交集”，而在“去重”。比如nums1=[1,2,2,1]，nums2=[2,2]，应该返回[2]，而不是[2,2]。
这道题第一反应是用两层循环判断每个元素是否同时出现在两个数组里，然后把匹配到的元素放入结果前再“查重”。这样不仅慢，而且逻辑绕：你既要判断交集，又要判断结果是否已存在，代码很容易盘成一团乱麻。
其实“去重”这件事，Set在结构上就帮你做完了。你不需要额外写条件，只要把元素放进Set，相同的键只会存一次。整个解法从“两层循环+去重判断”降维成“两个Set取交集”。
3.2 双Set解法与复杂度分析
思路是：先把nums1转成Set，再去重掉nums1自身的重复元素。然后遍历nums2，如果当前元素在Set里出现过，说明是交集元素，放入结果Set。最后把结果Set转成列表返回。
def intersection(nums1, nums2): set1 = set(nums1) res_set = set() for num in nums2: if num in set1: res_set.add(num) return list(res_set)这里有个关键点：遍历的是nums2，而不是nums1。因为set1已经从nums1构建好了，如果反过来遍历nums1，每个元素都需要去set2里查，代码相似，但逻辑上多了一次set2的构建。差别不大，但先构建其中一个集合，再用另一个数组做匹配，是这类题的通用模板。
时间复杂度是O(n+m)，构建Set是O(n)，遍历nums2并查询是O(m)。空间复杂度是O(n)，主要消耗在set1上。对于常规题目，这个效率已经达标。如果两个数组都很大，但内存受限，可以改为先排序再用双指针，把空间降到O(1)，代价是时间升到O(n log n + m log m)。这是典型的空间换时间与时间换空间的权衡。
3.3 别忽略数据范围的限制
有些题解会告诉你，因为题目有“数组长度不超过1000，元素值范围有限”之类的条件，所以可以用数组模拟哈希。但这类“脑筋急转弯”式的优化，我建议只在理解原理时做，比赛或面试时优先写清晰的双Set版本，然后再根据追问优化。
我踩过一个坑：直接调用语言内建的集合交集方法set(nums1) & set(nums2)，代码短到离谱。平时刷题这么写没问题，但如果是手写代码或者面试，最好还是展示出“遍历+查询”的过程，因为面试官想考察的是你懂不懂哈希表的逻辑，而不是你熟不熟悉库函数。当然，如果只是自己刷题验证思路，内建交集当然可以。
4. 202. 快乐数：哈希表的另一个用法是判圈
4.1 题面里的“数学陷阱”
快乐数的定义：给定一个正整数，每次替换为它各位数字的平方和，重复这个过程，如果最终能变为1，就是快乐数；否则会陷入一个不包含1的循环。比如19是快乐数，因为19→82→68→100→1。而2不是快乐数，因为2→4→16→37→58→89→145→42→20→4，开始循环。
这道题看起来是数学题，实际上考的依然是哈希表。你需要判断的是：在变换过程中，某个数字是否出现过。如果出现过的数字再次出现，说明已经进入循环，永远到不了1。
这个“出现过的数字再次出现”的判断，恰好就是哈希表最擅长的事。我第一次想这道题时，试图找数学规律，结果发现证明一个数是不是快乐数并不容易。后来意识到，根本不需要证明，只要检测循环就够了。计算机擅长的是“模拟”，而哈希表负责“记住历史”。
4.2 set做循环检测的完整代码
核心是两步：第一步写一个取平方和的辅助函数；第二步在主循环里用Set记录所有出现过的数。
def get_sum(n): total = 0 while n > 0: digit = n % 10 total += digit * digit n //= 10 return total def isHappy(n: int) -> bool: seen = set() while n != 1 and n not in seen: seen.add(n) n = get_sum(n) return n == 1get_sum的核心是“取出每一位数”，用n % 10拿末位，用n //= 10去掉末位，反复执行直到n变成0。注意这里用整数除法，而不是浮点除法，否则会出现无限制循环或者类型错误。
主循环的终止条件有两个：n变成1，直接返回True；n已经在seen里出现过，说明进入循环，返回False。注意循环里先seen.add(n)再更新n，顺序不能反。如果把更新放在add之前，当前n没有被记录，后续循环就检测不到重复。
4.3 不用哈希表：快慢指针解法
哈希表解法已经够用，但这里还有一个经典的扩展思路：快慢指针，也就是弗洛伊德判圈算法。如果数字变化进入了循环，那就像在一个环形跑道上跑步，快指针迟早会和慢指针相遇。慢指针每次走一步，快指针每次走两步，如果相遇了且不等于1，就说明有循环。
def isHappy2(n: int) -> bool: slow = n fast = get_sum(n) while fast != 1 and slow != fast: slow = get_sum(slow) fast = get_sum(get_sum(fast)) return fast == 1这个解法的空间复杂度是O(1)，不需要Set。它非常优雅，但我个人建议初学者先用Set版本，因为它更直白地体现了“记录历史→发现重复”的过程。快慢指针本质上是通过不同速度来检测环，需要额外理解一层抽象，但面试时如果主动说出来，会是很大的加分项。
5. 1. 两数之和：一遍遍历Map的经典套路
5.1 暴力法的瓶颈在哪
两数之和应该是所有刷题人遇到的第一道“知名”题目。给定一个数组和一个目标值，返回两个下标，使得对应元素之和等于目标值。最直接的解法是两层循环枚举所有数对，判断和是否为目标值。
暴力法没有问题，但在数组长度很大的时候，O(n²)的代价不可接受。假设数组有10万个元素，两层循环就是10亿次操作，哪怕每步都是常数时间，也会明显卡顿。优化的核心就是：能不能只遍历一遍，就把“我已经见过的数”记下来，让后续匹配变成O(1)。
这就是经典的“空间换时间”场景。我们需要一个容器，保存“元素值→下标”的映射。遍历到当前元素时，只需要查一下target - nums[i]在不在这个容器里，如果在，就找到了答案。这个容器用Map实现。
5.2 边查边存的一次遍历解法
def twoSum(nums, target): record = {} for i, num in enumerate(nums): complement = target - num if complement in record: return [record[complement], i] record[num] = i return []这里最值得讲的细节是“边查边存”。先查complement是否已在Map里，如果不在，再把自己存进去。这样设计有一个很重要的原因：避免“同一个元素被使用两次”。
举个例子，nums=[3,3]，target=6。如果先把所有元素插入Map，Map中键3对应的下标会被后面的3覆盖成1。遍历到第一个下标0时，查6-3=3，会查到下标1，结果是对的。但你依赖了“覆盖”这个行为，代码的可读性和正确性就变得隐晦。如果用的是不覆盖的写法，就可能在i=0时查到下标0自己，返回[0,0]，这是个错误答案。边查边存从逻辑上杜绝了这类问题：遍历到下标i时，Map里只有下标小于i的元素，当前元素还没放进去。
这个“先查询，后插入”的顺序，是这道题最重要的编码习惯。我第一次做的时候，先构建了完整的Map再遍历查询，虽然也能通过，但分析边界情况时特别容易被自己绕晕。改成边查边存后，逻辑一目了然。
5.3 为什么不存在“更优解”，以及变体问题
两数之和的O(n)时间复杂度已经是线性下界，因为至少要遍历一次数组才能知道有哪些元素。空间上消耗了O(n)，用来存储“见过的数”。很多同学会问：能不能像有序数组那样用双指针把空间也省了？
前提是数组要有序。如果先排序，时间复杂度是O(n log n)，然后双指针可以在O(n)内找到元素，但因为排序会改变元素位置，返回下标时需要额外记录原始下标，反而更麻烦。如果题目要求返回的是元素值而不是下标，那排序+双指针确实是一个非常优秀的选择，空间O(1)。这也是为什么面试官总爱问变体：把“返回下标”改成“判断是否存在”，解法就完全不同。理解这一点，比背模板有用得多。
这道题的另一个变体是“两数之和”变成“三数之和”。三数之和不能直接靠一层Map解决，因为需要去重和组合多个元素，通常用排序+双指针。从一数到三，难度跳跃不是一点半点，但底层逻辑还是“如何高效找出匹配对”。
6. 刷题避坑手册：哈希表的常见误区与经验
6.1 五问五答：刷题时的高频纠结点
问：什么时候一定用数组，什么时候一定用Map？
答：没有“一定”，只有一个判断标准——键的取值范围是否紧凑且已知。字母异位词的键是26个字母，紧密且有限，用数组。两数之和的键是数组里的任意整数，范围不可控，用Map。如果硬用数组，你无法用int[-1000000000]这种下标。
问：Python里in对列表和元组也是O(1)吗？
答：不是。列表和元组用in是线性扫描，时间复杂度O(n)。只有Set和Dict的in才是平均O(1)。很多同学代码能跑通，但复杂度完全是错的，因为不自觉地用了list in list这种写法。判断元素是否在集合里，一定要用Set或Dict。
问：哈希表的键有什么限制？
答：键必须是不可变类型。整数、字符串、元组都可以；列表、字典不行。刷题时我经常需要把数组元素组合当键，这时要把它转成元组再放进Map。
问：负数和哈希函数有关系吗？
答：没关系，负数作为键很常见。但要注意，如果键是负数且你用数组下标模拟，就需要做偏移处理，比如把所有键加一个偏移量。用Map就不需要关心这个问题。
问：哈希表查询明明是O(1)，为什么感觉有时候比我写两层循环还慢？
答：因为O(1)是平均复杂度，常数项不一定小。Map内部要计算哈希值、定位桶、处理冲突，每一步都有开销。如果数据量很小，比如只有几个元素，两层循环反而可能更快。算法分析看的是规模增长趋势，不是小数据下的绝对时间。这个认知能帮你避免“为了优化而优化”。
6.2 几个提升编码效率的实操习惯
第一，先想清楚“哈希表的键是什么、值是什么”，再动笔。很多人在两数之和里犯迷糊，就是因为没想清楚Map存的是值到下标，而不是下标到值。先定义好键值关系，代码自然就顺了。
第二，善用辅助函数。快乐数里的get_sum，如果直接写在主循环里，代码会变得很难读。单独拆一个函数，逻辑清晰，也方便单测。刷题时经常要反复验证辅助函数对不对，拆开后就能快速测试。
第三，在本地调试时打印中间状态。我第一次做快乐数时，调试就是打印n和seen的实时内容，很快就能看到循环是怎么形成的。刷题不是在考场上一个字一个字憋代码，调试也是一种学习。
第四，写完代码后走一遍边界测试。空数组、只有一个元素、最大最小值、全重复元素、目标值由前两个元素组成……这些边界能帮你抓住90%的隐藏bug。哈希表相关题目尤其要检查重复元素和键的边界。
第五，理解内建方法背后的语义，但不过度依赖。set(nums1) & set(nums2)可以一行搞定349题，但你自己手动写一遍“遍历+查询”，才能真正掌握哈希表在算法里的角色。两件事都做，效果最好。
我在实际刷哈希表专题时，最大的体会是：不要死记“这是Set题”“这是Map题”，而是问自己三个问题——我要查什么东西？查一次要花多少时间？能不能用已经读到的数据减少后续查询的成本？想通这三个问题，哈希表基本就出师了。Day5这四道题，从数组哈希到Set去重，再到循环检测和Map配对，正好覆盖了哈希表的全部典型用法。把它们吃透，后面做滑动窗口、前缀和、频率统计这些题时，你会发现自己已经多了一层“条件反射”。
)
