DAY6这一天的安排我盯着看了很久哈希表理论基础然后三道题全部围绕哈希表展开——有效的字母异位词、两个数组的交集、快乐数。说实话这三道题单看都不难但放到一起恰好把哈希表的三种典型用法串了一遍数组模拟哈希、哈希集合去重、哈希表判循环。后面和群友聊的时候发现很多人卡在“到底什么时候用数组、什么时候用set、什么时候用dict”再加上“哈希表和字典的区别”这个话题被反复拿出来问干脆把这一天的笔记整理成一篇完整的复盘。你说哈希表重要吧它确实是很多题解的“灵魂道具”你说它简单吧真上手写的时候又容易在边界条件上翻车。这一篇我不打算只贴代码我想把“为什么这么写”“为什么用这个结构”也一并捋清楚尽量让没系统学过哈希表的人也能直接看懂、抄走、用起来。1. 为什么刷题到第六天所有题解都开始说“用哈希表”1.1 哈希表解决的核心问题判断“某个东西出现过没有”算法题里有一类问题出现频率极高给你两个集合让你找交集、找差集、查某个元素是否存在于某个集合。如果每次都用遍历去查时间复杂度就是O(N*M)数据量一大立刻超时。哈希表存在的意义就是把这个“查询是否存在”的操作从O(N)降到平均O(1)。哈希表的底层逻辑可以这样理解我们有一排桶每个桶上挂着一个编号。存数据的时候先用一个哈希函数把“键”换算成桶的编号然后直接把值丢进对应桶里。查数据的时候同样的键用同样的哈希函数一算直接去对应桶里找。这就像图书馆按书号分架你不需要翻遍整个图书馆按编号去找那一排架子就行。刷题的时候看到“判断是否存在”“找重复”“数频率”“检查出现过没有”这些字眼第一反应就应该是能不能用哈希表。DAY6这三道题本质上全是在考这个点。字母异位词要判断字母出现次数是否一致数组交集要判断某个元素是否同时出现在两个数组里快乐数要判断计算过程中是否出现了重复结果——全都是“存在性”问题。1.2 哈希表的三种实现形态对应三类使用场景很多人以为哈希表就只是“字典”这是个大误区。在不同的场景下哈希表有三种完全不同的“打开方式”刷题时必须区分清楚数组当键的范围很小且连续时直接用数组下标当键速度最快、空间可控。哈希集合set / unordered_set只关心“有没有”不关心“有几个”用于去重和判断存在。哈希映射map / dict / unordered_map既关心“有没有”还关心“对应什么值”用于存储键值对。DAY6的三道题正好对应这三种形态字母异位词用数组两个数组的交集用哈希集合快乐数用哈希集合记录历史状态。把这一层想清楚了做题就不是背代码而是“看到题目就知道该套哪种容器”。另外补充几个哈希表理论里绕不开的概念面试也爱问哈希函数负责把键映射到桶位可能出现不同键映射到同一个桶的情况叫哈希碰撞。常见解决碰撞的方法有链地址法同一个桶挂一条链表和开放寻址法桶满了往后找空位。当哈希表里元素太多、桶不够用时会触发扩容扩容时需要把所有元素重新哈希一遍这是O(N)的操作。所以哈希表的O(1)是“平均情况”极端情况下或者扩容瞬间性能会退化。2. 242. 有效的字母异位词数组才是这题的最佳哈希结构2.1 题意和第一反应排序比较法其实能过题目给你两个字符串s和t让你判断t是不是s的字母异位词也就是“组成两个字符串的字母相同只是排列顺序不同”。最简单的思路是直接把两个字符串排序排序后相同就返回True。def isAnagram(self, s: str, t: str) - bool: return sorted(s) sorted(t)这行代码确实能AC时间复杂度O(NlogN)空间复杂度取决于排序的实现。但问题在于这个解法没有用到字符串只包含小写字母这个关键条件。排序本质上是在“比较整体内容”而我们真正需要比较的是“每个字母出现的次数是否相等”。如果字符串特别长排序的开销不值得。2.2 数组模拟哈希下标当键出现次数当值题目明确说了s和t只包含小写字母小写字母一共就26个。这是最典型的“键范围有限且连续”场景直接用数组当哈希表是最优解。定义一个长度为26的数组下标0代表a下标1代表b以此类推。遍历s时让对应位置的计数加1遍历t时让对应位置的计数减1。最后检查数组是否全部为0如果是说明两个字符串的字母出现次数完全一致。def isAnagram(self, s: str, t: str) - bool: record [0] * 26 for ch in s: record[ord(ch) - ord(a)] 1 for ch in t: record[ord(ch) - ord(a)] - 1 for count in record: if count ! 0: return False return True为什么下标要减去ord(a)因为ord(a)的ASCII码是97ord(z)是122减去97之后正好映射到0到25和数组下标一一对应。这个方法的时间复杂度是O(N)只需要遍历两遍字符串空间复杂度O(1)因为不管字符串多长数组长度永远是26。2.3 为什么不直接用字典可能有朋友会问用字典记录字母次数不也行吗确实行对于这题用collections.Counter(s) collections.Counter(t)也能AC。但要注意两点第一字典的常数比数组大。数组查下标是一次内存访问字典要先算哈希、处理可能的碰撞、再访问节点虽然都是O(1)实际耗时差好几倍。第二字典需要动态创建键、维护哈希表结构当键范围已知时属于“杀鸡用牛刀”。反过来想如果题目改成“字符串包含所有ASCII字符”甚至“Unicode字符”那数组空间就不够用了这时候用字典才是正解。判断用数组还是哈希表的依据就是键的取值范围是否已知、是否有限。这也是DAY6第一题想训练的核心意识——不是所有哈希表都长成字典的样子。2.4 这题容易忽略的边界细节如果两个字符串长度不同可以直接返回False省一次遍历。我在写代码时先加了这个判断防御性编程能省不少无谓操作。如果只遍历一个字符串做加法然后遍历另一个字符串做减法最后一定要检查整个数组不能只看某个下标。record用列表生成式[0] * 26最干净别写循环来初始化代码越简洁越不容易出错。3. 349. 两个数组的交集哈希集合是如何把去重和查找揉在一起的3.1 题目要求与暴力的弊病题目给两个数组nums1和nums2要求返回它们的交集结果中每个元素必须是唯一的也就是说要去重。最直接的暴力法是双层循环拿nums1的每个元素去nums2里找有没有相同的找到一个就加入结果。但这样做时间复杂度O(N*M)而且还要额外处理“结果去重”的问题代码会越写越乱。这题其实有两个层面的要求一是查找“某个元素是否在另一个数组里”二是“结果不能有重复元素”。哈希集合天然把这两件事同时解决了。3.2 哈希集合去重先用set存再用set查思路拆成四步把nums1转成一个哈希集合set1这一步自动去重。遍历nums2逐个检查元素num是否存在于set1中。如果存在说明num是交集元素把它加入另一个哈希集合result_set避免结果重复。最后把result_set转成列表返回。def intersection(self, nums1: List[int], nums2: List[int]) - List[int]: set1 set(nums1) result_set set() for num in nums2: if num in set1: result_set.add(num) return list(result_set)set1干的是“查询来源表”的活result_set干的是“结果去重表”的活。两个集合职责不同这不是冗余设计而是让代码逻辑分层清晰。第一次写的时候很多人会忘记结果去重直接用一个list来append然后发现[1,1]这种输入会输出重复的1再回来补一层去重逻辑。如果追求更简洁Python的集合运算一行就能完成def intersection(self, nums1: List[int], nums2: List[int]) - List[int]: return list(set(nums1) set(nums2))是两个集合的交集运算一行解决所有事。但我建议初学者还是先写展开版把“哈希集合”和“去重”的机制亲手走一遍对理解更有帮助。一行版适合二刷时优化代码风格。3.3 关于结果顺序和数据类型的小提醒题目对返回结果的顺序没有要求所以不管是遍历nums2还是nums1来查只要交集中的元素都在结果顺序不一致也能AC。但如果你在本地调试时发现输出顺序和题面示例不一样不用慌那是正常现象集合本身就是无序的。另外题目磁盘页面上看数据范围不大但如果数组很大用哈希集合的优势就非常明显时间复杂度O(NM)空间复杂度O(N)存set1对比暴力的O(N*M)提升是数量级的。这题还有一个变体值得留意如果要求交集结果按升序排列那最后加一行sorted(result_set)就行如果两个数组本身有序那还能用双指针法做空间复杂度降到O(1)这也是扩展学习的重点。4. 202. 快乐数哈希表检测循环的真正价值4.1 什么是快乐数难点在哪快乐数的定义不复杂对一个正整数每次把它替换为各个位上数字的平方和重复这个过程如果最终能变成1那么这个数就是快乐数如果无论如何都变不到1那它就是“不快乐”的。例如191² 9² 828² 2² 646² 4² 363² 6² 454² 5² 414² 1² 171² 7² 505² 0² 252² 5² 292² 9² 858² 5² 898² 9² 1451² 4² 5² 424² 2² 202² 0² 44² 161² 6² 373² 7² 585² 8² 89看走到89之后开始循环了。所以19不是快乐数。问题的核心不是“把平方和算出来”而是“如何判断这个过程会永远循环下去”。很多人第一反应是那就一直算什么时候等于1了返回True。问题是如果始终不等于1程序就会死循环。所以必须找到循环的标志。4.2 用哈希集合记录“出现过的数”这个思路非常直观只要某个平方和的结果之前已经出现过说明我们进入了循环。因为计算过程是确定的同一个数再算一遍后续结果一定和上次完全一样。只要检测到重复马上返回False。def isHappy(self, n: int) - bool: def get_sum(num: int) - int: total 0 while num 0: digit num % 10 total digit * digit num // 10 return total seen set() while n ! 1 and n not in seen: seen.add(n) n get_sum(n) return n 1这段代码的关键点在while循环的条件只要n不是1并且n还没出现过就继续算。一旦n出现在seen里说明重复了直接退出循环。最后判断n是否等于1即可。get_sum函数是这题的底层算术逻辑用num % 10取最低位数字用num // 10去掉最低位逐位取平方和。这里要特别注意digit num % 10取的是当前个位数字不是“每一位”。想当然地写成digit num是最常见的错误。4.3 进阶思路快慢指针检测循环这道题其实还有另一个经典解法就是链表判圈的Floyd快慢指针算法。把“每次计算的平方和”看成链表的下一个节点如果存在循环那么快慢指针一定会在环里相遇。def isHappy(self, n: int) - bool: def get_sum(num: int) - int: total 0 while num 0: digit num % 10 total digit * digit num // 10 return total 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(N)降到O(1)是一个很好的优化方向。我个人建议第一遍用哈希集合写逻辑更直白二刷的时候再练快慢指针体会两种思路在空间复杂度上的差异。4.4 一个容易被忽略的数学事实为什么哈希集合一定能判断出不快乐数因为“平方和”计算的结果是有限的。以三位数999为例9² 9² 9² 243。任意一个很大的数比如10位数每位最大9平方和最大也就是81乘以位数结果会迅速缩小到一个有限范围。有限的状态空间中如果不进入1必然进入循环。所以用哈希集合记录历史状态在逻辑上是完备的不会漏判。这个“状态有限、必有循环”的思维模式在算法题里经常用到比如判断链表是否有环、检测随机数生成器是否重复。DAY6把快乐数放在哈希表专题里本质就是教你利用哈希表的“唯一性约束”来识别重复状态。5. 哈希表与字典的区别刷题时如何选择最合适的结构5.1 哈希表是抽象概念字典是具体实现这个问题几乎每个刷题群都有人问“哈希表和字典到底有什么区别用的时候是不是随便换”我的回答是哈希表是一种数据结构的思想字典或者说map、映射是哈希表的一种实现形式。哈希表的核心是“通过哈希函数计算存储位置”只要符合这个机制数组、字典、集合都可以是哈希表。字典强调的是“键值对映射关系”它通常用哈希表实现但不一定必须用哈希表实现。比如C里的map底层是红黑树它也是字典但不是哈希表。C里的unordered_map底层才是哈希表。不少语言里“字典”这个词被直接拿来指代哈希表比如Python的dict就是典型的哈希表实现所以刷题时候“用字典”和“用哈希表”确实经常是一回事。但要较真起来“哈希表”讨论的是底层结构“字典”讨论的是接口语义。5.2 不同语言里的哈希表家族刷题时最容易混淆的是不同语言的容器选型我用一张表整理一下语言哈希集合哈希映射有序版本通常基于树Pythonsetdictsortedcontainers第三方Cunordered_setunordered_mapset / map红黑树JavaHashSetHashMapTreeSet / TreeMapGomap无set用map[键]struct{}模拟map标准库无有序映射RustHashSetHashMapBTreeSet / BTreeMap看到没有Python的dict默认就是哈希表而C的map是红黑树。如果你刷题习惯用C不小心用了map而不是unordered_map复杂度就从O(1)变成了O(logN)数据量大的时候表现完全不同。我自己刷题时默认组合是去重用set统计次数用dict需要有序遍历时才考虑sorted或TreeMap。这个选择顺序帮我避开了很多“AC不了但不知道为什么”的尴尬情况。5.3 哈希表的实际性能平均O(1)不等于一定快哈希表的时间复杂度是平均O(1)但这背后有几个前提哈希函数足够分散、哈希碰撞少、负载因子控制得好。Python的dict在底层做了很多优化日常刷题基本不用操心。但如果你自己实现一个哈希表就要注意哈希函数的设计和扩容阈值。还有一个刷题时容易忽略的细节频繁插入元素可能导致哈希表扩容扩容需要重新哈希所有已有元素这是O(N)的操作。所以在一些超大数据量场景下如果你的题目数据范围已知且不大直接用数组反而比哈希表更快、更省内存。这就是为什么242题我强烈推荐数组而不是字典——哈希表虽然也是O(1)但那个O(1)的常数比数组下标访问大得多。遇到以下情况优先考虑数组而不是哈希表键的范围是连续整数且范围很小比如字符频率统计、100以内的数字计数比如状态只有0和1布尔数组就够了遇到以下情况才考虑哈希集合或哈希映射键的分布稀疏无法预知键是字符串、自定义对象需要频繁查询“是否存在”但键范围非常大这个判断标准在DAY6之后的所有题里都用得上。我后来写哈希表相关的题基本都按这个逻辑来先问自己“键是什么类型范围可不可以枚举”再决定选哪种容器。想清楚了再动手代码错误率能下降一大截。6. 这些题刷完我实际复盘出的三点经验6.1 哈希表的“容器选型”要形成肌肉记忆DAY6表面上教了三道题实际上教的是一个决策流程。看到一道题先判断它是不是“存在性”问题如果是再判断键的范围是否有限如果有限且小用数组否则用set或dict。这个流程在后面的很多题里反复出现比如判断字符串是否同构、找第一个重复数字、统计子串出现次数。早期我经常凭感觉选结构后期我强制自己每次写代码前先标注“这题用了什么结构、为什么用”坚持了大概一周选型基本就不纠结了。6.2 哈希集合的两个作用别只记住一个很多人用set只知道去重忘了set也可以用来快速查找。349题里set1的核心价值是O(1)时间判断“某个数在不在这个集合里”result_set才是用来去重的。一个容器可以同时担任查询表和去重表两个角色这个意识要建立起来。刷题时遇到“统计不重复元素个数”“找出第一个出现两次的数字”“判断某个序列是否包含目标值”这类题set都能用上。6.3 调试哈希表相关代码先打印“历史状态”如果你在本地调试快乐数或判断循环的题建议在seen.add(n)之前打印一下n把整个序列打出来看一遍。肉眼看到重复出现的数字比单看代码逻辑直观得多。我在写快乐数的时候第一次把get_sum里的取位写错了打印之后立刻发现问题某一步出现了79后面全是纠缠在一起的循环而不是逐步变小。这种调试习惯比反复看代码更快也更适合算法学习阶段。DAY6这一天的收获对我来说不是背会了三道题的答案而是建立了一个“看到存在性问题就想哈希”的条件反射。哈希表本身不玄乎核心就是“用空间换时间”把查找从“扫一遍”变成“直接定位”。后面再刷哈希表的进阶题比如三数之和、滑动窗口、前缀和统计你会发现这个底子打得越扎实上层思路推导得越顺。