如果数据范围不大,比如要统计每个学生的成绩,直接开一个数组 cnt[score] 就行,O(1) 完成。但如果数据是字符串、是 10^9 范围的大整数呢?数组下标放不下。
哈希表的思路是:设计一个函数,把任意类型的「键」映射成一个不太大的整数,再用这个整数当下标去访问数组。理想情况下,查找、插入、删除都能接近 O(1)。
本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。
| 考试 | 大纲要求 | 本章位置 |
|---|---|---|
| GESP C++ 七级 | 考点 4:哈希表的概念、知识及其应用 | 全章 |
| CSP-J/S 提高级 | 2.3.5 哈希表:数值哈希函数构造、字符串哈希函数构造、哈希冲突的常用处理方法 | 全章 |
哈希函数
哈希函数负责把键变成下标。两个常见例子:
- 数值:
h(x) = x % MOD,其中MOD一般取一个接近表长的质数。 - 字符串:把字符串当成一个 base 进制数。
// 把字符串映射成一个整数,base 取质数,MOD 取大质数
int hashString(const string &s) {
long long h = 0;
for (char c : s) {
h = (h * 131 + c) % 1000000007;
}
return h;
}base 取 131 或 13331、MOD 取一个大质数,是竞赛里的常用搭配。取质数是为了让分布更均匀。
哈希冲突
不同的键可能映射到同一个下标,这叫哈希冲突。它无法完全避免,只能处理。两种主流方法:
| 方法 | 做法 | 特点 |
|---|---|---|
| 开放定址 | 位置被占了就往后找下一个空位(线性探测) | 不用额外空间,删除麻烦 |
| 链地址法 | 每个位置挂一条链表,冲突的都挂在链上 | 实现简单,删除方便 |
装填因子是已存元素数与表长的比值。它越大,冲突越多,性能越差。一般控制在 0.7 以下,超过了就扩容并重新哈希。
字符串哈希与滚动哈希
字符串哈希的威力在于,预处理之后可以在 O(1) 时间内求出任意子串的哈希值,从而快速判断两个子串是否相同。
思路是预处理前缀哈希和幂次:
H[i] = H[i-1] \times base + s[i]
子串 s[l..r] 的哈希值是:
H[r] - H[l-1] \times base^{r-l+1}
const int BASE = 131;
const long long MOD = 1000000007;
long long h[100005], p[100005];
void init(const string &s) {
int n = s.size();
p[0] = 1;
h[0] = 0;
for (int i = 1; i <= n; i++) {
h[i] = (h[i-1] * BASE + s[i-1]) % MOD;
p[i] = p[i-1] * BASE % MOD;
}
}
long long getHash(int l, int r) { // 1-based 下标
return ((h[r] - h[l-1] * p[r-l+1]) % MOD + MOD) % MOD;
}注意最后那个 + MOD) % MOD,因为减法可能出负数,而 C++ 的负数取模结果也是负的。
单个哈希有机会被刻意构造的数据「卡掉」(两个不同字符串得到相同哈希值)。稳妥做法是用两个不同的模数,或者直接用 C++ 的 string 比较。
竞赛里更常见的写法
大多数情况不需要手写哈希表,直接用 STL:
#include <bits/stdc++.h>
using namespace std;
int main() {
unordered_map<string, int> cnt; // 哈希实现,平均 O(1)
cnt["apple"]++;
cnt["banana"]++;
cout << cnt["apple"] << endl; // 1
map<string, int> mp; // 红黑树实现,O(log n),但键有序
mp["b"] = 2;
mp["a"] = 1;
for (auto &pr : mp) cout << pr.first << " " << pr.second << endl; // a 1, b 2
return 0;
}两者的区别必须记住:
| 容器 | 底层 | 单次操作 | 是否有序 |
|---|---|---|---|
map / set |
红黑树 | O(\log n) |
有序 |
unordered_map / unordered_set |
哈希表 | 平均 O(1),最坏 O(n) |
无序 |
需要按键排序、求前驱后继时用 map / set;只做查找和计数,用 unordered_map / unordered_set。
unordered_map的默认哈希函数可以被卡。有些比赛的数据会专门构造冲突,让单次操作退化到O(n)。CSP-S 提高级就出现过卡unordered_map的题。防卡的方法是自己写随机种子哈希,或者老老实实用map。
典型应用
- 判重。判断一个元素之前是否出现过,比如统计不同字符串的个数。
- 计数。统计每种元素出现多少次。
- 映射。把字符串、大整数映射成数组下标或其他编号。
- 字符串匹配。用滚动哈希在
O(n + m)时间内找模式串。 - 记忆化搜索。把状态哈希成整数作为下标。
复杂度
| 操作 | 哈希表(平均) | 哈希表(最坏) | map/set |
|---|---|---|---|
| 查找 | O(1) |
O(n) |
O(\log n) |
| 插入 | O(1) |
O(n) |
O(\log n) |
| 删除 | O(1) |
O(n) |
O(\log n) |
常见易错点
- 哈希表的最坏情况是
O(n),不是所有时候都快。 unordered_map可能被卡,重要比赛里谨慎使用。- 字符串哈希要处理负数取模,用
((x % MOD) + MOD) % MOD。 - 模数取质数,base 也要取质数,分布才均匀。
map的mp[key]在键不存在时会自动插入一个默认值,只想查询用mp.find(key)。unordered_map不支持随机访问,也不能按下标遍历。- 忽略大小写时忘了转换。题目说「忽略大小写」,就必须在计数之前统一转换,否则
Apple和apple是两个键。 - 并列时只保留第一个最大值。
unordered_map遍历无序,这样写结果不确定,必须显式比较字典序。 tolower的返回值没赋回去。tolower(c)只是返回转换后的字符,不会修改c本身。
练习
练习 1:词频统计
在线评测练习:P1089 词频统计
题目描述
给定 n 个单词,找出其中出现次数最多的单词。忽略字母大小写(Apple、apple、APPLE 视为同一个单词)。
输入格式
第一行一个整数 n;接下来 n 行,每行一个由大小写英文字母组成的单词。
输出格式
输出一行,包含出现次数最多的单词(输出小写形式)。
输入输出样例
输入
6
Apple
banana
apple
Orange
banana
apple输出
apple数据范围
1 \le n \le 100,每个单词长度不超过 30。- 保证出现次数最多的单词只有一个。
题目分析
这是哈希表最典型的使用场景:用一个 map<string, int> 记录「每个单词出现了几次」。
三个关键点:
- 统一大小写。题目要求忽略大小写,所以在计数之前就把单词全部转成小写:
for (auto &c : s) c = tolower(c);。注意必须转换后再存进 map,否则Apple和apple会被当成两个不同的键。 - 输出小写形式。因为建表时已经转成小写,键本身就是小写,直接输出即可。
- 找最大值。遍历 map 找计数最大的那个。题目保证「最多的只有一个」,所以不需要处理并列。
为什么用 map 而不是 unordered_map? 本题 n \le 100,两者都没问题。但如果想输出「并列时字典序最小的」,map 的键天然有序,遍历顺序就是字典序,取最大值时用 > 就能保证并列时留下的是字典序更小的那个;而 unordered_map 遍历无序,必须额外比较字符串。这就是「有序」在实战中的价值。
另一种思路:unordered_map + 手写比较。 遍历时显式处理并列:
for (auto &pr : cnt) {
if (pr.second > bestCnt ||
(pr.second == bestCnt && pr.first < bestName)) {
bestCnt = pr.second;
bestName = pr.first;
}
}两种写法都要会,因为题目条件一变(要不要并列、要不要有序输出)就得换。
参考代码
练习 2:出现最多的单词(并列取字典序最小)
在线评测练习:P1419 出现最多的单词
题目描述
输入 n 个只含小写字母的单词,输出出现次数最多的单词及其次数。若有多个单词出现次数相同且最多,输出字典序最小的那个。
输入格式
第一行一个正整数 n;接下来 n 行,每行一个只含小写字母的单词,长度不超过 20。
输出格式
输出一行,包含一个单词和一个整数,中间用一个空格隔开。
输入输出样例
输入
6
apple
banana
apple
cherry
banana
apple输出
apple 3数据范围
1 \le n \le 10^5,每个单词长度不超过 20。
题目分析
和练习 1 的区别有两点:规模大了(n 到 10^5)×、要处理并列(取字典序最小)。
规模变大意味着 unordered_map 更合适:n = 10^5 时,map 的每次插入是 O(\log n) 且常数较大(红黑树 + 字符串比较),unordered_map 平均 O(1)。本题数据不会专门卡哈希,用 unordered_map 是安全的。
并列处理是这题的核心。 unordered_map 的遍历顺序是不确定的,所以不能像练习 1 那样「只保留第一个最大值」——必须显式比较:
if (pr.second > bestCnt ||
(pr.second == bestCnt && pr.first < bestName)) {
// 次数更多;或次数相同但字典序更小 → 更新
}把这个条件读三遍:第二个分支 pr.second == bestCnt && pr.first < bestName 就是「次数打平时,选字典序小的」。漏掉它,答案会随哈希桶的顺序变化,同一份代码在不同编译器/不同数据下可能给出不同结果——这类 bug 最难查,因为本地测试可能永远是对的。
如果改用
map,键按字典序有序遍历,那么「次数相同时什么都不做」就自动保留了字典序最小的那个(因为小的先被遍历到,后来的相等次数不会覆盖)。这就是「数据结构选对了,逻辑就简单了」的典型例子。 代价是O(\log n)。
参考代码
小结
- 哈希把键映射成整数下标,理想情况下查找是
O(1)。 - 冲突可以用开放定址或链地址法处理,装填因子太高要扩容。
- 字符串哈希配合前缀数组,可以
O(1)判断两个子串是否相同。 map有序、O(\log n);unordered_map无序、平均O(1)但可能被卡。- 哈希表最适合判重和计数这类「看一眼就完事」的操作。
- 词频统计类题目的固定套路:先统一格式(大小写)→ 哈希计数 → 遍历找最大值。
- 并列处理必须显式比较。
unordered_map遍历无序,只「保留第一个最大值」会得到不确定的结果。 - 需要的输出「有序」时优先用
map,键有序能让并列、排序类逻辑自动简化。