---
title: "哈希表"
description: "哈希函数、冲突处理与字符串哈希，以及 unordered_map 的用法。"
---

> Documentation Index
> Fetch the complete documentation index at: https://cppguide.xyz/llms.txt
> Use this file to discover all available pages before exploring further.

# 哈希表

如果数据范围不大，比如要统计每个学生的成绩，直接开一个数组 `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 进制数。

```cpp
// 把字符串映射成一个整数，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}$$

```cpp
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：

```cpp
#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 词频统计](https://dailyup.run/tasks/173)

#### 题目描述

给定 $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` + 手写比较。** 遍历时显式处理并列：

```cpp
for (auto &pr : cnt) {
    if (pr.second > bestCnt ||
        (pr.second == bestCnt && pr.first < bestName)) {
        bestCnt = pr.second;
        bestName = pr.first;
    }
}

两种写法都要会，因为题目条件一变（要不要并列、要不要有序输出）就得换。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/ds/hash/index.md

### 练习 2：出现最多的单词（并列取字典序最小）

在线评测练习：[P1419 出现最多的单词](https://dailyup.run/tasks/503)

#### 题目描述

输入 $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 那样「只保留第一个最大值」——必须**显式比较**：

```cpp
if (pr.second > bestCnt ||
    (pr.second == bestCnt && pr.first < bestName)) {
    // 次数更多；或次数相同但字典序更小 → 更新
}

**把这个条件读三遍**：第二个分支 `pr.second == bestCnt && pr.first < bestName` 就是「次数打平时，选字典序小的」。漏掉它，答案会随哈希桶的顺序变化，**同一份代码在不同编译器/不同数据下可能给出不同结果**——这类 bug 最难查，因为本地测试可能永远是对的。

> 如果改用 `map`，键按字典序有序遍历，那么「次数相同时什么都不做」就自动保留了字典序最小的那个（因为小的先被遍历到，后来的相等次数不会覆盖）。**这就是「数据结构选对了，逻辑就简单了」的典型例子。** 代价是 $O(\log n)$。

#### 参考代码

> 🔒 参考代码已隐藏。请在网页版输入解锁密码查看：https://cppguide.xyz/ds/hash/index.md

## 小结

- 哈希把键映射成整数下标，理想情况下查找是 $O(1)$。
- 冲突可以用开放定址或链地址法处理，装填因子太高要扩容。
- 字符串哈希配合前缀数组，可以 $O(1)$ 判断两个子串是否相同。
- `map` 有序、$O(\log n)$；`unordered_map` 无序、平均 $O(1)$ 但可能被卡。
- 哈希表最适合判重和计数这类「看一眼就完事」的操作。
- 词频统计类题目的固定套路：先统一格式（大小写）→ 哈希计数 → 遍历找最大值。
- **并列处理必须显式比较**。`unordered_map` 遍历无序，只「保留第一个最大值」会得到不确定的结果。
- 需要的输出「有序」时优先用 `map`，键有序能让并列、排序类逻辑自动简化。

Source: https://cppguide.xyz/ds/hash/index.mdx
