哈希表 Hash Table

2026-06-02

哈希表本质不是数据结构，是一种算法套路：用 O(1) 查询换 O(N) 遍历。看到”找两个元素满足某关系”就该条件反射。

直觉 — O(1) 查询换 O(N) 遍历

暴力解法的题大多长这样：枚举所有 (i, j) 对，看是否满足某关系。O(N²)。

哈希表做的事情非常单纯：边遍历边把”已见过的”丢进表，每来一个新元素，问表里有没有能跟我配对的。一次遍历 + 每步 O(1) 查询 = O(N)。

套路化成一句话：

把 O(N²) 的”配对枚举”，改成 O(N) 的”边走边查”。

什么时候用得上：

  • 题目要求两个元素满足 f(a, b) = target（两数之和、四数相加、HashMap 找差/和/积）
  • 题目问”前面是否出现过 X”（最长无重复子串、包含重复元素）
  • 题目要数”某种值出现了多少次”（计数、异位词分组）
  • 题目想把 O(N) 的范围查询压成 O(1)（前缀和 + hash，下面讲）

set vs dict 怎么选：只关心”见过没”用 set；要存附加信息（下标、计数、上次出现的位置）用 dict。两数之和要返回下标，所以是 dict；判重就是 set。别一上来就 dict 装样子。

动画：两数之和的”先查后存”

数组 [2, 7, 11, 15]，target = 9。重点看两件事：

  1. 每来一个新元素 x，先查表里有没有 target - x，没有再把 x 自己存进去。
  2. seen 字典从空慢慢长大，第 2 个元素 7 来的时候，表里已经有 2，立刻命中。

看完动画再回头读下面的模板，套路就刻进肌肉里了。

模板 — 两数之和、子数组和等于 k

套路一：两数之和（先查后存）

1
2
3
4
5
6
def twoSum(nums, target):
    seen = {}                              # 值 -> 下标
    for i, x in enumerate(nums):
        if target - x in seen:             # 1. 先查
            return [seen[target - x], i]
        seen[x] = i                        # 2. 后存

为什么必须先查后存？nums = [3, 3], target = 6：如果先存后查，第一个 3 存进去后立刻自己查到自己，返回 [0, 0]——同一个元素配自己。先查后存把”自己”挡在表外。

套路二：是否出现过 / 判重

1
2
3
4
5
6
7
def containsDuplicate(nums):
    seen = set()                           # 只关心见没见过 → set
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

注意这里换成了 set，因为不需要附加信息。

套路三：分组 / 计数（选好 key 是关键）

1
2
3
4
5
6
7
# 异位词分组：key 必须能唯一标识"同一组"
from collections import defaultdict
groups = defaultdict(list)
for word in words:
    key = tuple(sorted(word))              # 或字母频率元组
    groups[key].append(word)
return list(groups.values())

选 key 的标准：可哈希 + 能唯一代表”同类”。

前缀和 + hash 组合

这是 hash 在算法题里最容易拉开差距的一招。子数组和 = prefix[j] - prefix[i]，所以”子数组和等于 k”就等价于”找两个前缀和差等于 k”——又一次回到两数之和的形状。

1
2
3
4
5
6
7
8
def subarraySum(nums, k):
    prefix = {0: 1}                        # 空前缀，和为 0 出现 1 次
    curr_sum = count = 0
    for x in nums:
        curr_sum += x
        count += prefix.get(curr_sum - k, 0)   # 找 prev_sum = curr - k
        prefix[curr_sum] = prefix.get(curr_sum, 0) + 1
    return count

两个关键点：

  • {0: 1} 不能漏：代表”什么都不取”的空前缀。少了它，从下标 0 开始的合法子数组会被漏数。
  • 先查后存的顺序仍然成立：先用旧的 prefix 算 count，再把当前 curr_sum 写进表。否则会把当前位置自己算成”前一段”。

这个组合一旦学会，下面这些题就都是同一道：

变体 key 存什么
和等于 k prefix_sum
和能被 k 整除 prefix_sum % k
二叉树路径和（437） 沿路径维护 prefix
0/1 子数组数量相等 把 0 当 -1，再求和等于 0

经典题

热身（一遍写出来）：

    1. Two Sum — 模板题
    1. Contains Duplicate — set 判重
    1. Group Anagrams — 选 key
    1. Longest Consecutive — set + 跳过非起点，O(N)
    1. Subarray Sum Equals K — 前缀和模板

进阶：

    1. 4Sum II — 拆成 a+b 和 -(c+d) 两边，hash 把 O(N⁴) 砍成 O(N²)
    1. Subarray Sums Divisible by K — 前缀和模 K
    1. Path Sum III — 前缀和 + 回溯，下树前加、回溯前删
    1. LRU Cache — dict + 双链表
    1. Design Twitter — hash 套 heap

Python 速查

1
2
3
4
5
6
7
8
d.get(k, 0)                                # 不存在返回默认值
d.setdefault(k, []).append(v)              # 不存在先建空列表
from collections import defaultdict, Counter
d = defaultdict(int)                       # 自动初始化为 0
d = defaultdict(list)                      # 自动初始化为 []
c = Counter("hello")                       # Counter({'l':2,'h':1,'e':1,'o':1})
c.most_common(2)                           # 取频次前 2
c1 - c2                                    # 多重集合差，负数自动截断为 0

Counter 减法是滑动窗口比较字符频率、判断”能否拼成 X”的利器。

进阶：滚动哈希 Rabin-Karp

字符串匹配场景，把窗口看成 base 进制数，移动窗口时 O(1) 更新哈希：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def rabinKarp(text, pattern):
    base, mod = 31, 10**9 + 7
    m = len(pattern)
    pat_hash = 0
    for c in pattern:
        pat_hash = (pat_hash * base + ord(c)) % mod
    win_hash, power = 0, pow(base, m, mod)
    for i, c in enumerate(text):
        win_hash = (win_hash * base + ord(c)) % mod
        if i >= m:
            win_hash = (win_hash - ord(text[i - m]) * power) % mod
        if i >= m - 1 and win_hash == pat_hash:
            if text[i-m+1:i+1] == pattern: # 防碰撞验证
                return i - m + 1
    return -1

哈希相等还得用字符串再比一次，工程上是基本操作。

记忆法 / 易错点

  • 看到”配对”想 hash：题面出现”两个数满足…”、”是否存在…”、”前面有没有…”——条件反射伸手摸 hash。
  • 先查后存：永远别让当前元素配它自己。
  • set vs dict：只问见没见 → set；要存下标/计数/位置 → dict。
  • 前缀和 hash 一定要 {0: 1} 初始化：覆盖”从头开始”的子数组。
  • 遍历中改 dict 要小心：键变更可能影响后续逻辑，必要时拷贝或延后写。
  • 大数据担心碰撞：自定义对象做 key 要实现 __hash__ 和 __eq__，且两者必须一致。
  • 不可变才能当 key：list 不行、tuple 可以；set 不行、frozenset 可以。

思考题

为什么两数之和必须"先查后存"？给一个"先存后查"会出错的例子。

nums = [3, 3], target = 6。先存后查：第一个 3 先写入 seen[3]=0，立刻查 6-3=3 在表里，返回 [0, 0]——同一个元素自己配自己，错误。

先查后存：第一个 3 来时表空，查不到，再写入；第二个 3 来时查到表里的 3，返回 [0, 1]，正确。

前缀和 + hash 中，{0: 1} 初始化代表什么？不加会漏什么？

代表”什么都不取的空前缀，和为 0，出现过 1 次”。

当某个 curr_sum 恰好等于 k 时（即从下标 0 一路加到当前位置就是 k），代码会去查 prefix[curr_sum - k] = prefix[0]。没初始化就漏掉这种”从头开始”的子数组。

例：nums = [1, 2, 3], k = 3，子数组 [1, 2] 就是靠 prefix[0]=1 数到的。

Counter 减法 c1 - c2 为什么只保留正数？什么时候有用？

Counter 是”多重集合”，元素数不能负。减法即”移除”，移除超过持有量就归零。

用法：

  • 判断 word 能否由 available 的字母拼成：Counter(word) - Counter(available) 为空则可以。
  • 找缺什么字母：Counter(required) - Counter(have)。
  • 滑动窗口比较字符频率。