最近集中刷了一批 Hash 相关的 LeetCode 题三道题分别涉及表达式求值、区间重复检测和字符串分组正好把哈希表的几个典型用法都过了一遍。这篇记录不会把官方题解复读一遍只写我实际思考过程中踩过的坑和最后沉淀下来的通用套路适合正在刷 Hot 100、周赛或者准备面试的同学当个参考。先说结论Hash 之所以高频不是因为它难而是因为它能把“查找”这个动作从 O(n) 降到 O(1)代价只是多花一点内存。三道题分别对应了哈希表的三种常见用法——做映射、做标记、做分组键。理解了这三类场景后续再遇到“两数之和”“无重复字符的最长子串”“字母异位词”这些题基本都能快速定位到哈希解法。1. 先聊聊 Hash为什么算法题绕不开它1.1 Hash 到底在做什么哈希表本质上是一个“键到值的映射结构”。你给它一个 key它通过一个哈希函数算出存储位置然后直接去那个位置取值。这个过程的平均时间复杂度是 O(1)前提是哈希函数分布均匀冲突控制得当。我习惯用一个生活化类比来理解你去图书馆找一本书如果书是按书名拼音首字母分区的你不需要一本一本地翻直接去对应字母区域找就行。哈希函数就是“首字母分区规则”而冲突就是“同一个字母分区里有多本书”这时候需要再花一点时间在分区内逐个比对。这个类比能解释很多面试追问。面试官问“哈希表为什么快”不是让你背“因为用了哈希函数”而是希望你讲出“通过哈希函数直接定位桶再用链表或红黑树解决桶内冲突”的完整链条。1.2 冲突处理的两条路哈希冲突是绕不开的问题两道不同的 key 算到了同一个桶。常见的处理方式有两种链地址法同一个桶后面挂一条链表冲突元素依次追加。JDK 的 HashMap 在桶内元素超过阈值后会转红黑树本质就是优化链表的查找性能。开放寻址法冲突了就往下一个空闲位置放ThreadLocalMap 用的就是这种。它的缺点是删除元素麻烦需要标记而不是直接清空。写 LeetCode 的时候大多数语言的哈希表已经帮你封装好了冲突处理比如 Python 的 dict、C 的 unordered_map、Java 的 HashMap。但你得知道底层是什么否则没法解释为什么某些场景下自定义哈希函数能显著提升性能。1.3 什么时候“想到用 Hash”这是我刷题过程中最想分享的一点。很多人拿到题不知道什么时候该用哈希表我的判断标准很简单题目里出现了“查找”“是否存在”“统计次数”“分组归类”这些关键词而且数据规模在 O(n^2) 不可接受的范围优先考虑 Hash。判断流程是这样的先想暴力解法是什么复杂度多少。如果暴力是 O(n^2)看能不能用一次遍历 空间换时间。把“每次都要查找”的东西提前存进哈希表查找成本从 O(n) 降到 O(1)。这套思路放在后面三道题里每一道都适用。逆波兰表达式求值是“查找运算符对应的计算逻辑”存在重复元素是“查找之前是否出现过”字母异位词分组是“把相同特征的字符串归到同一组”。2. 第一道题150. 逆波兰表达式求值2.1 题目到底在考什么题目给了一个后缀表达式比如[2, 1, , 3, *]要求计算结果结果是 9。逆波兰表达式的特点是运算符写在两个操作数后面不需要括号来改变优先级。乍一看这题和哈希表没关系核心是用栈遇到数字入栈遇到运算符弹出两个操作数计算后把结果压回栈里。但我在实际做的时候发现 Hash 在这里的作用很容易被忽略——它映射的是“运算符字符串到具体计算行为”。很多官方解法会写一大堆 if/else 判断运算符代码长且容易漏。用哈希表存下运算符对应的执行函数代码会清晰很多。这个思路在工程里也很常见叫“策略模式”的简化版。2.2 解法核心栈 运算符映射我用的思路是维护一个操作数栈同时准备一个哈希映射运算符是 key处理逻辑是 value。在 C 里这个映射可以写成std::unordered_mapstd::string, std::functionint(int, int)在 Python 里可以直接用dict存lambda。大致的流程遍历 tokens 里的每个 token。如果 token 是数字直接转成整数压栈。如果 token 是运算符从栈里弹出两个数注意弹出来的顺序。调用映射里对应的计算逻辑把结果压回栈。最后栈顶元素就是答案。关键细节是弹出顺序。后缀表达式中先压栈的是左操作数后压栈的是右操作数。弹出的时候先拿到的是右操作数后拿到的是左操作数。减法和除法尤其容易在这里翻车顺序反了结果就错了。2.3 写代码的细节和容易翻车的点负数和多位数token 可能是-2或者123。不要用token[0]是不是数字来判断运算符因为负数开头也是-。稳妥的判断方式是先看长度如果长度大于 1 且不是运算符就按数字处理。整数溢出LeetCode 的测试用例里会出现中间结果超过 int 范围的情况。C 直接用int会溢出我建议用long long或者std::stol。Python 没有这个问题。除法的截断方向C 对负数的整数除法是向零截断Python 的//是向下取整。比如-3 / 2C 结果是-1Python 的(-3) // 2结果是-2。提交前要确认语言的取整规则否则可能挂在一个很不起眼的用例上。我第一版代码就是忘了处理负数判断-2被当成运算符解析直接报错。加了长度判断之后才通过。这个错误很小但排错花了我十分钟写在这里提醒大家。3. 第二道题219. 存在重复元素 II3.1 题目要求与思路题目给一个整数数组和一个整数 k判断是否存在两个不同的下标 i 和 j使得nums[i] nums[j]并且abs(i - j) k。暴力做法是两层循环枚举所有下标对复杂度 O(n^2)。数组长度上万的时候就吃不消了。用哈希表可以一次遍历解决遍历数组时把每个元素的值作为 key它的最新下标作为 value 存进哈希表。每遇到一个元素先查表里有没有出现过相同的值如果有就计算当前下标和已存下标的差值。这里必须注意一个关键点遇到重复时哈希表里存的是哪个下标应该存最近一次出现的下标而不是第一次出现的下标。因为我们需要的是“存在一对距离不超过 k”越近的下标越可能满足条件同时也能覆盖更多后续可能性。我举个例子数组[1, 0, 1, 1]k 1。遍历到第三个元素时哈希表里存的是下标 0 还是 1 其实无所谓因为都是同一个值。但遍历到第四个元素时如果哈希表里存的是下标 2最近一次那么当前下标 3 和上次下标 2 的差是 1满足条件直接返回 true。如果存的是第一次的下标 0差值是 3超过 k可能就漏掉了正确答案。3.2 哈希表版本和滑动窗口版本的对比这题还有另一种解法维护一个大小为 k 的滑动窗口用集合判断窗口内有没有重复元素。窗口滑动的过程中不断加入新元素、移除离开窗口的旧元素。哈希表版本空间复杂度最坏 O(n)因为每个不同元素都可能存一个下标。滑动窗口版本空间复杂度严格 O(k)因为集合里最多只有 k1 个元素。时间复杂度两者都是 O(n)。如果 k 很小滑动窗口更省内存如果 k 很大接近 n两者没有本质区别。实际工程里我倾向先写哈希表版本因为代码简单、逻辑更直观。但面试如果聊到空间优化能说出滑动窗口方案会加分不少。这也是为什么我建议两道解法都掌握不需要二选一。3.3 复杂度与边界检查边界一k 可能是负数吗题目默认不会但如果你用了滑动窗口窗口大小是负数时会出错。建议开始前做一次if (k 0)的兜底。边界二数字范围很大甚至可能是负数。哈希表不存在“索引偏移”问题直接用负值当 key 完全没问题这也是它比某些计数数组方案更优的地方。边界三数组长度为 1 时任何 k 都不可能产生重复直接返回 false。我提交的时候有一次就是因为窗口大小写成k而不是k1导致边界用例没过。滑动窗口判断去重时新元素加入前要先检查集合的大小否则窗口会超过合法范围。4. 第三道题49. 字母异位词分组4.1 异位词的本质题目是给一个字符串数组把由相同字母重新排列组成的字符串分到同一组比如[eat, tea, tan, ate, nat, bat]结果是[[bat], [nat, tan], [ate, eat, tea]]。这题的核心是找到一个判别函数让“字母异位词”映射到同一个键而不同的字母组合映射到不同的键。哈希表的 key 设计决定了这道题的成败。异位词的本质是字母构成相同只是排列顺序不同。所以判别逻辑必须摆脱“顺序”的影响。4.2 两种 key 设计排序法和计数法第一种排序法。把字符串按字母排序排序后的结果作为 key。eat排序后是aettea排序后也是aet两者自然归到一组。这种方案实现简单但每个字符串都要排序总复杂度是 O(n * m log m)m 是字符串平均长度。第二种计数法。统计每个字符串中每个字母出现的次数把次数序列作为 key。比如eat的计数序列是[1, 0, 0, ..., 1, ..., 1]按 26 个字母tea的序列完全一致。C 里可以把 26 个计数拼成一个字符串Python 里可以用tuple(counts)作为 dict 的 key。这种方案复杂度是 O(n * m)没有排序开销但 key 会稍微长一点。排序法适合字符串很短、题解速度要求快的场景计数法适合字符串很长、字母集合固定的场景。实际提交 LeetCode两种都能过计数法在极端用例下更快。4.3 实现细节和复杂度对比Python 中注意str可以作为 key但多字符计数用collections.Counter的items()转 tuple 有点慢。我实测下来直接用 26 长度的 tuple 更稳。C 中注意std::map和std::unordered_map的选择。key 是字符串时unordered_map需要额外的哈希函数标准库默认支持std::string直接用即可。key 的编码不要用分隔符连接计数否则可能被某些特殊字符干扰。直接用定长数组转字符串最稳妥。两种方案的复杂度对比如下方案时间复杂度空间复杂度适用场景排序法O(n * m log m)O(n * m)字符串短、编码简洁计数法O(n * m)O(n * m)字符串长、字母范围固定空间复杂度两者差不多主要差别在时间上。我一开始用排序法AC 之后改了计数法发现运行时间大概快了一倍。实战中遇到这题我建议直接写计数法顺手把“优化点”写在注释里面试官问起来还能多聊几句。5. 三道题放在一起看Hash 的变式与思维模式5.1 同一个 Hash三种用法刷完三道题再回头看Hash 不是一种单一技巧而是一类思维模式。三道题恰好是三种常见用法逆波兰表达式求值用 Hash 做“调度分发”把字符串运算符映射到可执行逻辑。这是哈希表在“策略查找”场景的应用。存在重复元素 II用 Hash 做“历史状态记录”记录元素上次出现的位置实现空间换时间。这是“标记去重”场景的应用。字母异位词分组用 Hash 做“归类依据”把有相同特征的物体映射到同一个桶。这是“分组聚合”场景的应用。这三种用法可以迁移到很多其他题目两数之和是“记录状态”无重复字符的最长子串是“滚动去重”单词规律是“双向映射”。你想通了这三个场景Hash 相关的题基本就通了一半。5.2 Hash 相关的常见坑这些坑不只是三道题里遇到的是刷了几十道 Hash 题之后总结出来的遍历过程中修改哈希表Python 里边遍历 dict 边删除元素会直接报错或者导致行为不确定。可以先收集要删的 key遍历结束后再统一删。key 的可变性Python 的 list 不能作为 dict 的 key因为不可哈希。遇到需要把数组当 key 的情况转成 tuple 或字符串。默认值问题dict.get()和defaultdict的行为要区分前者不会自动创建键后者会。该用get的时候别偷懒用defaultdict否则会往哈希表里塞一堆空键。自定义对象的哈希如果给自定义类写__hash__记得同时重写__eq__否则哈希值相同但相等性判断不一致会出现找不到 key 的情况。5.3 从刷题到工程Hash 键设计的实际映射刷题时我们关注怎么设计 key工程里同样有“哈希键设计”问题。比如前端打包工具里输出的 JS 文件名带一串 hash是为了实现“内容寻址”——内容不变则 hash 不变浏览器可以长缓存内容一变则 hash 变浏览器自然加载新文件。这个本质和字母异位词分组里的“特征映射”是同一种思路。再比如终端里校验文件完整性时用的hash命令是哈希函数在数据完整性校验场景的应用和哈希表是两个概念。很多初学者容易混淆其实哈希表使用的哈希函数更关注“分布均匀”而校验哈希更关注“雪崩效应”和“碰撞概率低”。严格来说工程中的文件 hash 是“摘要”LeetCode 里的哈希表是“索引结构”两者只是共享了“通过函数计算指纹”这个底层思想。这也是为什么我建议刷题的时候多想一层这题里的哈希到底是用来做“索引查找”还是“指纹归类”想清楚这个面试时讲解决方案会更有深度而不是只会背代码。6. 一些排查心得和刷题建议三道题里最容易卡住的是第一道题的负数判断最容易漏掉的是第二道题的“最近下标”最值得琢磨的是第三道题的 key 设计。我把它们整理成一个速查表方便大家复习问题现象原因解法负数 token 被误判报错无法解析运算符token[0] -覆盖了负数用token.size() 1排除负数减除法结果错误部分用例失败弹出顺序搞反先弹出的赋给 right后弹出的赋给 left窗口重复漏判边界用例失败窗口大小多算了 1控制集合大小为 k1异位词 key 不一致分组错误计数序列拼法有问题用定长数组转字符串Python 的 list 当 key运行报错list 不可哈希转成 tuple 或字符串关于刷题顺序我的建议是先做“存在重复元素 II”这类简单的标记题再做“逆波兰表达式求值”这类综合题最后啃“字母异位词分组”这种需要设计 key 的题。难度是阶梯递进的可以帮你把 Hash 的基础概念一层层夯实。不要上来就扎进难题容易产生挫败感。我特别喜欢在 LeetCode 里搜索“哈希表”标签把 easy 和 medium 的题按通过率降序刷一遍大概三四十题之后你会发现自己对“什么时候用 Hash”已经有了肌肉记忆。看到题目里出现“互不相同”“存在重复”“按特征分组”这些词第一反应就会想到用一个哈希表去解决。最后分享一下我的个人习惯每道题 AC 之后我会强迫自己再写一个不同解法的版本。比如存在重复元素 II 我写了哈希表和滑动窗口两个版本字母异位词分组我写了排序法和计数法两个版本。不是为了刷题量而是为了比对两种方案的复杂度差异这个习惯让我的算法基础扎实了很多。下一轮刷题我打算围绕“哈希 前缀和”这个组合多找几道题练练这类题目在周赛里出现频率很高复杂度比单考哈希表要高一个档次值得花时间研究。