Skip to content

哈希表

哈希函数、冲突处理与字符串哈希,以及 unordered_map 的用法。

Updated View as Markdown

如果数据范围不大,比如要统计每个学生的成绩,直接开一个数组 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> 记录「每个单词出现了几次」。

三个关键点:

  1. 统一大小写。题目要求忽略大小写,所以在计数之前就把单词全部转成小写:for (auto &c : s) c = tolower(c);。注意必须转换后再存进 map,否则 Apple 和 apple 会被当成两个不同的键。
  2. 输出小写形式。因为建表时已经转成小写,键本身就是小写,直接输出即可。
  3. 找最大值。遍历 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,键有序能让并列、排序类逻辑自动简化。
Navigation

Type to search…

↑↓ navigate↵ selectEsc close