哈希表是工具箱里性价比最高的"超能力"：每个元素只多花一点点内存，就能让"这个值我之前见过吗？“这种查询变成几乎一条指令的开销。一整类暴力 $O(n^2)$ 的解法，只要换上哈希表，就能直接坍缩成 $O(n)$ 的一次遍历。

这是 LeetCode 算法精讲系列 的第一篇。我们会从零搭起对哈希表的直觉，再用四道模板题——两数之和、字母异位词分组、无重复字符的最长子串、前 K 个高频元素——把可以反复套用的思维范式讲透。

系列导航

LeetCode 算法精讲系列（共 10 篇）：

哈希表 —— 两数之和、字母异位词分组、无重复字符的最长子串、前 K 个高频元素 ← 当前文章
双指针 —— 对撞指针、快慢指针、分区
链表 —— 反转、环检测、合并
滑动窗口 —— 定长窗口与变长窗口
二分查找 —— 在下标上、在答案上、在实数上
二叉树遍历 —— 递归、BFS、最近公共祖先
动态规划 —— 一维 DP、二维 DP、背包家族
回溯 —— 排列、组合、剪枝
贪心 —— 交换论证、调度问题
栈与队列 —— 单调栈、双端队列

一、哈希表究竟是什么

哈希表把若干 (key, value) 键值对存进一个底层数组，关键在于一个叫 哈希函数 的东西：它把任意类型的 key 算成一个整数下标，告诉你这个键值对应该放在数组的哪一格。

由此带来三条性质：

确定性：同一个 key 永远算到同一个槽——这是查找能成立的根本前提。
平均 $O(1)$：在哈希函数还算正常的前提下，插入、查找、删除的耗时不随 $n$ 增长。
最坏 $O(n)$：如果太多 key 挤进同一个槽，性能会退化成线性扫描。这通常只发生在恶意输入或哈希函数很糟的情况下，正常工程里几乎遇不到。

冲突无法避免

两个不同的 key 可能算出同一个下标——这就是冲突（collision）。两种主流的解决策略：

链式法（Separate Chaining）：每个槽里挂一个小链表（或平衡树），冲突的元素就直接追加进去。Java 的 HashMap、C++ 的 std::unordered_map 走这条路。
开放寻址（Open Addressing）：每个槽只放一个元素。冲突时往后探测（slot+1、slot+2……），直到找到空槽。Python 的 dict、Go 的 map 走这条路。

平时你几乎不会自己实现冲突处理，但搞懂背后的机制能解释一件事：哈希表为什么偶尔会比 $O(1)$ 慢，以及为什么"哈希函数好不好"很重要。

哈希表 vs 其他选择

为什么要用哈希表，而不是排序数组或者裸数组？

查找代价：哈希 $O(1)$ vs 二分 $O(\log n)$ vs 线性 $O(n)$

差距随 $n$ 急剧放大。当 $n = 1000$ 时，无序数组的线性扫描每次查找要做约 1000 次比较，二分查找约 10 次，哈希查找约 1 次。代价是内存：Python 的 dict 大约要花裸数组 8–16 倍的字节，因为它得存哈希值、键、值，还要保留足够的空槽来抑制冲突。

选哪种结构

写代码之前，先想清楚自己到底需要什么：

经验法则：数组 > set > map（按内存开销从小到大）。能用更轻的结构就别上更重的。具体对照如下：

你需要的能力	用什么
用 `[0, N)` 的整数下标取值	普通 `list` / 数组
“这个东西我见过吗？”	`set`
“这个 key 对应的 value 是什么？”	`dict`
计数	`collections.Counter`
自动初始化空桶	`collections.defaultdict(list)`

Python 的 set 和 dict 共用同一套哈希底层，所以选哪个主要看可读性——能直白表达意图的代码，调试起来也最容易。

二、两数之和：互补搜索模式

LeetCode 1. 给定数组 nums 和目标值 target，返回数组中和为 target 的两个数的下标。题目保证恰好有一个解，且同一个元素不能用两次。

输入：nums = [2, 7, 11, 15], target = 9
输出：[0, 1]      # 因为 2 + 7 == 9

先写暴力解

最朴素的做法是双重循环——$O(n^2)$ 时间，$O(1)$ 空间：

1
2
3
4
5
6
7
def two_sum_brute(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

当 $n = 10^4$ 时大约要做 5000 万次比较。可以做得更好。

哈希表的思维转换

从左往右扫描时，每看到一个 num，要问的不是”num 在不在数组里"，而是 “我之前是不是已经见过 target − num？” 如果见过，配对就齐了。我们维护一个 value → index 的映射，记录"目前为止看过的所有数"。

两数之和单次遍历过程：nums = [2, 7, 11, 15], target = 9

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
from typing import List

def two_sum(nums: List[int], target: int) -> List[int]:
    """单次遍历的哈希表解法。时间 O(n)，空间 O(n)。"""
    seen: dict[int, int] = {}          # value -> 最早出现的下标

    for i, num in enumerate(nums):
        complement = target - num
        # 先查再插：避免把 num 和它自己配成一对。
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

    return []   # 题目保证有解，理论上走不到这里

两个细节值得记住：

先查后插。如果先 seen[num] = i 再查，遇到 nums = [3, 0, 0]、target = 6 这种输入就可能让某个元素和自己配对。
返回顺序。seen[complement] 是更早的下标，所以要放在前面：[seen[complement], i]。

为什么是 $O(n)$

外层循环跑 $n$ 次，每次内部只做一次字典查找加上可能的一次插入——两者都是平均 $O(1)$。总时间 $O(n)$，空间 $O(n)$（字典最多存 $n$ 个条目）。

对未排序的输入，时间和空间不可能再同时变得更优。如果数组本身已经排好序，第二篇要讲的双指针可以做到 $O(n)$ 时间 + $O(1)$ 空间——但前提是肯先排序，那本身就要 $O(n \log n)$。

模式：互补搜索

只要题目让你 “找满足某种关系的数对”，就先问一句：能不能改写成"对每个 x，是否存在之前见过的 y 使得 f(x, y) 成立"？能，那就基本上是哈希表的活：

问题	存什么	问什么
两数之和	已见过的数	`target − num` 在 `seen` 里吗？
数对差为 K（LeetCode 532）	已见过的数	`num + k`、`num − k` 在 `seen` 里吗？
和为 K 的子数组（LeetCode 560）	前缀和	`prefix − k` 在 `seen` 里吗？
连续子数组和（LeetCode 523）	前缀和 % k	同余的前缀和之前出现过吗？

三、字母异位词分组：规范化键模式

LeetCode 49. 给一个字符串数组，把字母异位词分到一组里。

输入：["eat", "tea", "tan", "ate", "nat", "bat"]
输出：[["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

字母异位词的本质是 字符的多重集相同、顺序不同。整道题的关键在于设计一个"键"，让所有异位词都映射到同一个桶里。

方案一：用排序后的字符串当键

最直接的规范化方式：把字符排个序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
from collections import defaultdict
from typing import List

def group_anagrams(strs: List[str]) -> List[List[str]]:
    """时间 O(n · k log k)，n = len(strs)，k = 最长字符串长度。"""
    groups: dict[str, list[str]] = defaultdict(list)
    for s in strs:
        key = "".join(sorted(s))   # "eat", "tea", "ate" 都排成 "aet"
        groups[key].append(s)
    return list(groups.values())

简单、通用，对任何字符集都能用。开销主要在排序：每个字符串 $O(k \log k)$。

方案二：用字符计数当键

如果字符集很小（比如全是小写英文字母，只有 26 个），统计每个字母的出现次数只要 $O(k)$，省掉排序：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
from collections import defaultdict
from typing import List

def group_anagrams(strs: List[str]) -> List[List[str]]:
    """用 26 维计数数组当键，时间 O(n · k)。"""
    groups: dict[tuple[int, ...], list[str]] = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord("a")] += 1
        # list 不可哈希，转成 tuple 才能当键。
        groups[tuple(count)].append(s)
    return list(groups.values())

这里有个常踩的坑：字典的键必须 不可变且可哈希。list 不能当键，但它的 tuple 版本可以。

模式：规范化键

只要题目说"把某种意义下相等的东西分组 / 找出 / 计数"，就先问 “这个等价类里所有元素共享的最小表示是什么？” 把它当哈希键就对了。

问题	等价关系	规范化键
字母异位词分组	字符多重集相同	排序后的字符串，或 26 维计数 tuple
移位字符串分组（LeetCode 249）	相邻字母差一致	相邻差的 tuple
同构字符串（LeetCode 205）	字母模式相同	“首次出现位置"归一化后的字符串
按长度分组	长度相同	长度本身

四、无重复字符的最长子串：滑动窗口 + 哈希表

LeetCode 3. 给字符串 s，求其中不含重复字符的最长子串的长度。

输入：s = "abcabcbb"
输出：3            # "abc"

这是哈希表与滑动窗口配合的经典场景。我们维护一个窗口 [left, right]，让 right 一格一格往右走；只要新字符会让窗口出现重复，就从左侧收缩窗口直到合法为止。

哈希表在这里干的活是：记下每个字符 最近一次出现的下标。这样遇到重复时可以让 left 一步跳到重复字符之后，而不是一格一格挪过去——节省的就是这一步。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def length_of_longest_substring(s: str) -> int:
    """记录每个字符的最近下标。时间 O(n)，空间 O(min(n, |Σ|))。"""
    last_seen: dict[str, int] = {}
    left = 0
    best = 0

    for right, ch in enumerate(s):
        # 当且仅当 ch 在「当前窗口内」出现过时才需要收缩。
        # 加 max 是为了忽略已经被甩在窗口左侧的旧记录。
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1

        last_seen[ch] = right
        best = max(best, right - left + 1)

    return best

"abcabcbb" 的执行轨迹：

`right`	`ch`	更新后的 `last_seen`	`left`	当前窗口	`best`
0	`a`	`{a:0}`	0	`a`	1
1	`b`	`{a:0, b:1}`	0	`ab`	2
2	`c`	`{a:0, b:1, c:2}`	0	`abc`	3
3	`a`	`{a:3, b:1, c:2}`	1	`bca`	3
4	`b`	`{a:3, b:4, c:2}`	2	`cab`	3
5	`c`	`{a:3, b:4, c:5}`	3	`abc`	3
6	`b`	`{a:3, b:6, c:5}`	5	`cb`	3
7	`b`	`{a:3, b:7, c:5}`	7	`b`	3

模式：变长窗口 + 哈希状态

只要题目要求"满足某条件的 最长 / 最短 子串/子数组”，并且加入或删除一个元素能在 $O(1)$ 内更新窗口状态，就可以套这个模板：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
left = 0
state = {}                       # 用来描述窗口当前状态的任何东西

for right, x in enumerate(arr):
    add(x, state)                # 扩张窗口

    while not valid(state):      # 窗口非法就一直收缩
        remove(arr[left], state)
        left += 1

    update_answer(left, right)

后面会遇到的变种：最小覆盖子串（LeetCode 76）、至多含 K 个不同字符的最长子串（LeetCode 340）、字符串的排列（LeetCode 567）。

五、前 K 个高频元素：频率统计 + 桶排序

LeetCode 347. 给整数数组 nums 和整数 k，返回出现频率前 k 高的元素。

输入：nums = [1, 1, 1, 2, 2, 3], k = 2
输出：[1, 2]

第一步显然是用哈希表（或 Counter）统计频率。第二步才是设计的关键：怎么挑出 top k？

方案一：堆（$O(n \log k)$）

把每个 (count, value) 推进一个大小为 k 的小顶堆：

1
2
3
4
5
6
7
8
9
import heapq
from collections import Counter
from typing import List

def top_k_frequent(nums: List[int], k: int) -> List[int]:
    """时间 O(n log k)，空间 O(n)。"""
    freq = Counter(nums)
    # most_common 内部就是用堆实现的。
    return [val for val, _ in freq.most_common(k)]

Counter.most_common 内部就在做这件事。简洁、地道，多数场合够用。

方案二：桶排序（$O(n)$）

频率最大不会超过 $n$。所以可以反过来——用频率当桶下标，把每个值塞到对应桶里，再从高频往低频读：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import Counter
from typing import List

def top_k_frequent(nums: List[int], k: int) -> List[int]:
    """按频率桶排序。时间 O(n)，空间 O(n)。"""
    freq = Counter(nums)

    # buckets[f] 存储所有出现 f 次的值。
    # 一个值最多出现 n 次，所以需要 n+1 个槽（0..n）。
    buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
    for value, count in freq.items():
        buckets[count].append(value)

    # 从最高频的桶往下扫。
    result: list[int] = []
    for f in range(len(buckets) - 1, 0, -1):
        for value in buckets[f]:
            result.append(value)
            if len(result) == k:
                return result
    return result

这是经典的"值有界，就拿值当下标“的小技巧。它的时间是真正的 $O(n)$，没有 $\log$ 因子；同样的思路在"按频率排序字符”（LeetCode 451）等题里还会再见。

模式：频率统计

三个 Python 惯用法，写多了基本就成肌肉记忆：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
from collections import Counter, defaultdict

# 1. 一行计数。
freq = Counter(nums)                       # {1: 3, 2: 2, 3: 1}

# 2. 分组时自动初始化桶。
groups = defaultdict(list)
for x in items:
    groups[key_of(x)].append(x)

# 3. 一行判断两个多重集相等。
def is_anagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

频率映射可以解决一大票问题：异位词判定、多数元素、第一个唯一字符、按频率排序、Top-K，以及任何"X 出现了几次"类的题目。

六、常见陷阱

下面这几条几乎覆盖了面试里所有的哈希表 bug：

先插再查。两数之和必须先查后插，否则可能把元素和自己配成一对。
不可哈希的键。list、set、dict 不能当字典键，需要先 tuple(...) 或 frozenset(...)。
插进去之后再修改键。如果用作键的对象内部内容改了，它的哈希值就过期了，原条目可能再也查不出来。键要当成不可变对象对待。
只需要 set 时却用 dict。seen[x] = True 这种写法比 seen.add(x) 多花约 30%–40% 的内存。
遍历时同时修改。在迭代 dict 时增删键可能抛 RuntimeError。要改就先 list(d.items()) 拷一份再迭代。
依赖键的顺序。Python 3.7+ 保留插入顺序，但不要把算法正确性建立在 key 顺序上。

七、面试自检清单

判断一道题适合用哈希表时，下笔之前在脑子里过一遍：

键是什么？ 原值、排序后的形式、计数 tuple，还是前缀和？
值是什么？ 下标、计数、下标列表，还是布尔标志？
set 还是 map？ 只关心存在性就用 set，更轻。
答案从哪冒出来？ 在扫描过程中"撞上"，还是在最后再扫一遍哈希表？
边界情况。 空输入、单个元素、全部重复、全部唯一、含负数。

口头表达的脚本大概是这样：

“暴力解是 $O(n^2)$，因为每个元素都要和其他元素比一遍。我可以一边扫一边维护一个 <key> → <value> 的哈希表，把每次查找压到 $O(1)$。总时间 $O(n)$，空间 $O(n)$。”

八、接下来练什么

把这四道模板题练到下意识就能想起对应模式后，可以按下面这个梯度继续：

简单。 存在重复元素（217）、有效的字母异位词（242）、两个数组的交集（349）。
中等。 和为 K 的子数组（560）、最长连续序列（128）、四数相加 II（454）、常数时间插入删除取随机（380）。
困难。 缺失的第一个正数（41——巧妙地把输入数组本身当哈希表用）、串联所有单词的子串（30）、至多含 K 个不同字符的最长子串（340）。

下一篇 双指针 我们会看到天平的另一端：当输入是有序的（或者愿意排序），双指针能在 $O(n)$ 时间内做到只用 $O(1)$ 额外空间，和哈希表打个平手。真正有趣的问题是 什么时候该选哪个——下一篇见。

LeetCode（一）—— 哈希表