哈希表从理论到实战：数组、Set与字典的O(1)查找技巧

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三者的适用边界捋了一遍也用三道题把“统计、存在、判环”三大场景逐层拆开了。我自己刷完这一组题最深的体会是哈希表这个数据结构看似简单但“什么时候用哪个实现”“什么时候用数组反而更好”才是真正拉开差距的地方。如果你能把这三道题的解法彻底吃透再遇到“判断重复”“统计频率”“快速查找”之类的题目基本都会有种豁然开朗的感觉。下一步建议你按同样的思路去刷“两数之和”和“三数之和”你会发现在哈希表基础上叠加双指针又是不一样的世界。