查找技巧)
1. 哈希表理论基础
1.1 哈希表到底是什么
先别被“哈希表”这个名字唬住，它其实就是一个“用空间换时间”的经典数据结构。你可以把它想象成一个带编号的储物柜：每个柜子有一个编号（索引），你存东西的时候根据编号直接放，取东西的时候根据编号直接拿，全程不需要翻箱倒柜。这个“编号”就是哈希函数算出来的结果，柜子阵列就是底层数组。
在算法题里，哈希表的核心价值只有一个：把查找时间从O(n)降到O(1)。举个例子，你想知道一个数组里有没有某个数，暴力做法是遍历一遍，O(n)。但如果你提前把所有数都存进哈希表，再查的时候只需要O(1)——对，就是这么霸道。这也是为什么很多“判断是否存在”“统计出现次数”“去重”类题目，第一反应就应该想到哈希表。
哈希表的底层实现一般是数组加链表（或红黑树），但作为刷题选手，你不需要一开始就钻到源码里。你需要先建立三个核心认知：键（Key）、哈希函数和冲突处理。键就是你要存的东西，哈希函数把键映射成数组下标，冲突处理则解决“两个键映射到同一个位置”的尴尬。
1.2 哈希函数与哈希冲突
哈希函数是整个哈希表的灵魂。它的作用是把任意长度的输入（键），通过某种算法映射成固定长度的输出（哈希值），然后再对这个哈希值取模，得到数组下标。理想情况下，不同的键应该映射到不同的下标，但现实总是残酷的——哈希冲突是永远无法完全避免的。
最常见的冲突处理有两种：链地址法和开放寻址法。链地址法就是每个数组位置挂一个链表，冲突的元素都链在这个位置上；开放寻址法则是冲突了就往下一个空位找。Java的HashMap用的是链地址法，当链表长度超过阈值（8）时会转成红黑树，就是为了防止极端情况下链表太长、查询退化。
这里有个很关键的点：哈希冲突的均匀性决定了哈希表的性能。如果哈希函数设计得烂，比如所有键都映射到同一个槽位，哈希表就退化成了一条链表，查询复杂度直接变成O(n)。所以面试里如果聊到哈希表，能说清楚“哈希函数为什么重要”“冲突怎么解决”，就已经赢了一半。
1.3 哈希表 vs 字典：别再傻傻分不清
这个热词我太有感触了，几乎每次讲哈希表都有人问“哈希表和字典到底啥区别”。一句话说清楚：哈希表是一种数据结构，字典是基于哈希表实现的一种抽象数据类型。换句话说，字典是“概念产品”，哈希表是“底层技术”。
类比一下：哈希表就像发动机，字典就像装了发动机的汽车。你开车的时候只需要管方向盘和油门（键值对的存取），不需要管发动机怎么点火、怎么供油（哈希函数怎么算、冲突怎么解决）。Python的dict、JS的Map和Object、Java的HashMap，底层全都是哈希表，但它们在接口设计、迭代顺序、线程安全等方面各有各的讲究。
刷题的时候更需要注意：Python的dict是无序的（其实保持插入序），Java的HashMap也是无序的，但LinkedHashMap可以保持插入顺序。如果你对顺序有要求，选错容器就是给自己埋坑。另外，Python里的set和frozenset底层也是哈希表，所以哈希表的题里，set往往是比dict更清爽的选择——这也是后面题目里会反复用到的技巧。
2. 242. 有效的字母异位词——数组就是最朴素的哈希表
2.1 题目到底在考什么
“有效的字母异位词”这个题，输入是两个字符串，让你判断它们是否由相同数量的相同字符组成。比如anagram和nagaram就是异位词，rat和car就不是。
这个题有个非常诱人的秒杀解法：把两个字符串排序后比较是否相等。代码三行搞定，时间复杂度O(n log n)。但如果你这么写，面试官大概率会追问一句“能不能O(n)？”——这不是刁难，而是想看你知不知道哈希表。
为什么哈希表能到O(n)？因为我们要做的本质上就是“统计每个字符出现的次数，然后比较两个统计结果”。字符串既然只包含小写字母，那字符的种类就是固定的26种。既然种类固定，还用啥哈希表？直接用数组就行——数组的下标就是字符的编码，数组的值就是出现次数。你说数组算不算哈希表？严格说不是，但它完美体现了哈希表的思路：用“键→索引”的映射来O(1)定位。所以很多人管这种解法叫“数组充当哈希表”。
2.2 数组版本的完整推导
具体做法是创建一个长度为26的整数数组record，初始全为0。遍历第一个字符串s，每遇到一个字符c，就让record[c - 'a']++；遍历第二个字符串t，每遇到一个字符，就让record[c - 'a']--。最后检查整个数组，如果所有元素都是0，说明两个字符串的字符频次完全一致。
这里有个细节值得多说一句：c - 'a'这个操作是把字符映射成0到25的数字。在C++里字符本质上就是整数，所以这个写法非常自然；在Java和Python里虽然字符和整型不是一回事，但都支持用字符做算术运算来拿到偏移量。这是“字符映射成索引”的固定套路，后面很多题都会用到。
为什么用减而不用两个数组？因为减可以在一个数组上完成“对比”的动作，省掉一次遍历。时间复杂度O(n)（n是字符串长度），空间复杂度O(1)——数组大小是固定26，不随输入增长。这个O(1)空间在面试里很加分，因为很多人想不到“固定大小的数组”其实也算常数空间。
class Solution: def isAnagram(self, s: str, t: str) -> bool: if len(s) != len(t): return False record = [0] * 26 for c in s: record[ord(c) - ord('a')] += 1 for c in t: record[ord(c) - ord('a')] -= 1 for count in record: if count != 0: return False return True2.3 这个题给我的三个教训
第一，别一上来就用字典。虽然用Python的collections.Counter或者自己维护一个dict也能解，而且字符范围不限于26时会用到，但在这个特定的题里，数组解法更优：没有哈希函数的计算开销，没有冲突处理，底层就是一块连续内存，快得飞起。实测下来，数组解法在LeetCode上的耗时通常比字典解法快30%到50%。
第二，别忽略输入范围。这个题说字符串只包含小写字母，所以才能用26的数组。如果题目没说字符范围，或者字符可能包含大写字母、数字、Unicode，那数组就不够用了，老老实实用哈希表。看清输入范围再定方案，这是刷题的基本素养。
第三，“异位词”不是“相同字符串”。很多人会在最后一步图省事，直接return record == [0] * 26。这样写没问题，但要注意这是Python的特性，Java里比较数组内容得用Arrays.equals，直接==比较的是引用。语言特性搞混了，代码就跑偏了。
3. 349. 两个数组的交集——Set就是天然的去重器
3.1 为什么这道题不再用数组了
“两个数组的交集”这个题的输入是两个整数数组，输出它们的交集，而且结果要求去重。比如nums1 = [1,2,2,1]，nums2 = [2,2]，交集是[2]——注意不是[2,2]。
为什么不能用数组解法了？因为整数的范围太大了。如果沿用“字符减‘a’偏移”的思路，你得确定整数的最大最小值，然后开一个那么大的数组。题目默认整数范围是-2^31到2^31-1，你要真敢开一个40多亿长度的数组，内存直接爆炸。这就是典型的“哈希表退化场景”：键的范围太大或者稀疏，数组就不合适了，必须引入真正的哈希表。
这里用哈希表的哪个实现？在Python里答案呼之欲出：set。因为题目要求去重，而set天生就是不重复元素的集合。哈希表的三个经典操作——存入、查找、删除——在set里分别对应add、in、remove，都是O(1)平均时间复杂度。
3.2 完整解题思路和代码实现
这道题的推荐解法是：先把nums1转成set去重，然后遍历nums2，用in判断每个元素是否在set里，在的话就加入结果集。为什么遍历短的数组？理论上市哪种都行，但如果先转set的是较短的数组，遍历较长数组时in的命中率更高，结果集的构建也更快。虽然是常数级别的差异，但在追求极致的代码里这也算一种优化。
实现上有个小坑：如果直接用列表当结果集，可能会加入重复元素（因为nums2里也可能有重复）。所以要么用set收集结果再转成列表，要么在加入前先判断结果集里有没有这个元素。用set收集再转换是最省事的，代价是最后多一次遍历转列表，时间复杂度依然是O(n)。
class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: set1 = set(nums1) set2 = set(nums2) # 遍历较小的集合，减少判断次数 if len(set1) > len(set2): set1, set2 = set2, set1 result = set() for num in set1: if num in set2: result.add(num) return list(result)等等，上面这段代码里我做了个优化：遍历较大的集合其实也行，但遍历小的集合，in判断次数更少。虽然in是O(1)，但常数再小，次数多了也有差异。实测在nums1很短、nums2很长的情况下，这种写法的耗时优势能到10%左右。
3.3 从这道题延伸出的两个思维升级
第一，克制住“用两层循环暴力解”的冲动。见过太多人拿到这题就双层for，时间复杂度O(n×m)。数据量小还看不出来，一旦两个数组都上万，直接超时。哈希表的本质就是“预先把信息存好，后面只花O(1)查询”，这个思维一旦建立，你会发现很多O(n²)的暴力解法都能优化成O(n)。
第二，注意题目要求里可能的“排序”陷阱。LeetCode原题对返回结果的顺序没有要求，所以直接用set是安全的。但如果面试官或题目要求结果有序，你得知道set在Python里是无序的（其实是按照哈希表内部的存储顺序），这时候就需要排序或者改用其他方式。“你以为你用了哈希表，但接口要求顺序”——这类细节在真实项目中太常见了。
4. 202. 快乐数——哈希表抓“循环”的经典现场
4.1 这题的难点不是计算，而是发现“无限循环”
“快乐数”这个题的描述很妖：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程，直到这个数变为1，或者进入一个无限循环。如果能变为1，这个数就是快乐数；如果不能，就不是。输入n = 19，输出true。
很多人第一次看这个题就懵了：不是1就不是快乐数？那怎么判断？关键就在“无限循环”四个字。你需要知道，一个数按照“各位数字平方和”这个规则变换下去，如果它到不了1，就一定会进入一个循环——而且是会回到之前出现过的某个数的循环。为什么？因为平方和的结果是有上限的。比如3位数最大是999，平方和是9²+9²+9²=243，不会无限增大。所以变换序列要么抵达1，要么兜圈子回到老路。
一旦理解了“会回到老路”，解题思路就清晰了：记录下每一步得到的数，如果新数已经在记录里出现过，说明进入循环了，可以直接判定不是快乐数。这不就是哈希表的经典应用场景吗？判断“是否出现过”，用set简直完美。
4.2 使用Set判环的完整实现
具体到代码，主循环有三个动作：计算当前数的各位平方和、检查新数是否已存在于set、将新数加入set。当新数等于1时返回true，当新数在set中出现过时返回false。
class Solution: def isHappy(self, n: int) -> bool: seen = set() while n != 1 and n not in seen: seen.add(n) n = sum(int(digit) ** 2 for digit in str(n)) return n == 1这版代码已经足够简洁了，但我想多说两句关于“细节换性能”的东西。int(digit) ** 2没问题，但如果你追求极致性能，可以把0到9的平方提前存成一个数组square = [i*i for i in range(10)]，然后查表取值。因为数字只有10个，查表的开销比计算int()低不少。实测在数字很大、循环次数多的情况下，这种方式能省大概20%的时间。别小看这种优化，刷题时的“快”往往就是这些细节攒出来的。
4.3 进阶思考：快慢指针和“非快乐数”的判定规律
这道题其实还藏着第二个解法——快慢指针（Floyd判圈算法）。思路是让慢指针每次走一步（算一次平方和），快指针每次走两步（算两次平方和），如果存在循环，快指针一定会追上慢指针。这个解法的妙处在于空间复杂度从O(n)降到了O(1)，不需要set记录所有出现过的数。
class Solution: def isHappy(self, n: int) -> bool: # 第二章的解法用set，这里是快慢指针 def get_next(num: int) -> int: total = 0 while num > 0: digit = num % 10 total += digit * digit num //= 10 return total slow = n fast = get_next(n) while fast != 1 and slow != fast: slow = get_next(slow) fast = get_next(get_next(fast)) return fast == 1为什么快慢指针能成立？如果这个数不是快乐数，变换序列会进入循环，快指针绕圈速度是慢指针的两倍，一定会在环内追上它。这个思路跟链表判环完全一致——很多哈希表的题其实背后都藏着“判环”思想，而判环有哈希表和双指针两条经典路线，两条都掌握，才能在面试里游刃有余。
另外透个底：在“非快乐数”的循环里，4是必经节点。这是数学上的结论：非快乐数最终都会进入4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4这个循环。所以另一种写法是“如果新数等于4，直接返回false”。这种技巧知道就行，不建议作为首选方案——太依赖数学结论，题目一变形就失效了。
5. 常见问题与避坑实录
5.1 哈希表相关的高频疑惑
为什么哈希表查找是O(1)，有时候却是O(n)？平均情况下是O(1)，但遇到极端情况——比如哈希函数设计不当，导致大量键冲突到同一个槽位——查找就会退化。Java的HashMap在链表过长时会转红黑树，把最坏情况从O(n)优化到O(log n)。刷题时你不一定需要处理这种极端情况，但面试官如果追问“哈希表有没有性能瓶颈”，能提到冲突和退化，就足够展示深度了。
Python的set和dict，什么时候用哪个？一句话：只需要判断“在不在”，用set；需要存“键值对”或者“统计次数”，用dict。比如快乐数只需要记录“出现过的数”，set就够了；而字母异位词如果用哈希表解法，需要“字符→次数”的映射，那就得用dict或Counter。选错数据结构会把代码写复杂，而且语义不清晰。
“数组怎么也算哈希表了？”严格来说数组不是哈希表，因为它的索引是天然的连续整数，不需要哈希函数做映射。但数组体现的“O(1)定位”思想和哈希表完全一致。在字符范围固定（比如26个小写字母）的题里，用数组比用真正的哈希表更高效——没有算哈希的开销，没有冲突，空间也是确定的。把数组视为“哈希表的退化形态”或者“简化形态”，是理解这类题的关键。
5.2 这三道题连在一起刷，到底在练什么
Day6这三道题不是随便凑数的，它们构成了一个递进序列：
- 242题教你用数组模拟哈希表，处理“键范围小且固定”的情况；
- 349题教你用真正的哈希表实现set去重，处理“键范围大且稀疏”的情况；
- 202题教你用哈希表判环，处理“序列中是否出现重复”的情况。
这三板斧几乎覆盖了哈希表在算法题里的所有基本用法。你仔细体会一下：242是“统计个数”，349是“判断存在”，202是“检测重复”——这就是哈希表的三大基本功。练完这三道题，再遇到“某某题能不能用哈希表”的纠结，你的判断速度会快很多。
5.3 我可太想提醒你的“坑”
坑一：字符串的遍历方式。Python里直接for c in s遍历字符没问题，但如果用for i in range(len(s))再s[i]，在大数据量下会稍微慢一点，因为Python的字符串索引有额外的类型检查开销。直接遍历可迭代对象永远是Pythonic的选择。
坑二：整数的取位方式。快乐数里计算各位平方和，有人用str(n)转字符串再遍历，有人用n % 10逐位取余。前者更直观，后者更快（省去字符串创建和解析的开销）。刷题时我推荐后者的写法，因为LeetCode的输入可以非常大，字符串转换会带来额外内存分配。
坑三：别把set和列表混用。在349题里，如果你用result = []然后if num not in result，这里的not in作用于列表是O(n)查找，整个解法就退化成了O(n²)。正确的姿势是结果也用set，最后list(result)转一下。列表的in和set的in，时间复杂度差了一个量级，这个坑我已经见人踩过无数次。
这次Day6的哈希表专题，我从理论讲到实践，把数组、set、dict三者的适用边界捋了一遍，也用三道题把“统计、存在、判环”三大场景逐层拆开了。我自己刷完这一组题最深的体会是：哈希表这个数据结构看似简单，但“什么时候用哪个实现”“什么时候用数组反而更好”，才是真正拉开差距的地方。如果你能把这三道题的解法彻底吃透，再遇到“判断重复”“统计频率”“快速查找”之类的题目，基本都会有种豁然开朗的感觉。下一步建议你按同样的思路，去刷“两数之和”和“三数之和”，你会发现在哈希表基础上叠加双指针，又是不一样的世界。
