Hash
自动关联目录:Hash
哈希(Hash)回答的是:如何用 的代价,判断"我见过这个东西吗"。
它的代价是放弃有序性——哈希表里取不出"最小的元素",也做不了范围查询。
需要范围查询 / 有序遍历 → 平衡树(set/map) O(log n)
只需要精确查找 / 计数 → 哈希表(unordered_*)O(1)哈希表
结构
┌───┐
key ──► │ h │ hash function ──► index ──► bucket
└───┘buckets: [ ][ x ][ ][y→z][ ]
0 1 2 3 4
↑ 冲突:y 和 z 都映射到 3两个必要组件:
- 哈希函数:key → 数组下标,尽量均匀
- 冲突处理:不同 key 映射到同一位置怎么办
冲突处理
拉链法(Chaining)
每个桶是一个链表(或更快的容器)。
vector<vector<pair<int,int>>> table(SIZE);
void insert(int k, int v) {
int h = k % SIZE;
for (auto& [kk, vv] : table[h])
if (kk == k) { vv = v; return; }
table[h].push_back({k, v});
}
int* find(int k) {
int h = k % SIZE;
for (auto& [kk, vv] : table[h])
if (kk == k) return &vv;
return nullptr;
}负载因子(元素数 / 桶数)。 越大,链表越长。
扩容:(典型阈值)时,桶数翻倍并重新散列(rehash)。均摊。
开放寻址(Open Addressing)
冲突就往后找空位。
探测序列: h(k), h(k)+1, h(k)+2, ... (线性探测)
h(k), h(k)+1², h(k)+2², ... (平方探测)// 线性探测
int find_slot(int k) {
int h = hash(k) % SIZE;
while (table[h].used && table[h].key != k)
h = (h + 1) % SIZE;
return h;
}| 拉链法 | 开放寻址 | |
|---|---|---|
| 缓存友好 | 差(链表指针跳转) | 好(数组连续) |
| 装载率容忍 | 可以 > 1 | 必须 < 1(满了就没处放) |
| 删除 | 简单 | 麻烦(要加"墓碑"标记) |
| 实现 | 简单 | 稍复杂 |
C++ 的 unordered_map 用拉链法(标准规定);很多高性能实现(如 Google 的 flat_hash_map、Rust 的 HashMap)用开放寻址,因为缓存友好得多。
复杂度
| 操作 | 平均 | 最坏 |
|---|---|---|
| 查找 / 插入 / 删除 |
最坏情况:所有 key 都映射到同一个桶(哈希函数太差或被恶意构造)。
这就是 Hash DoS 攻击:攻击者构造大量碰撞的 key,把 退化成,耗尽服务器 CPU。
防护:
- 用带随机种子的哈希函数(每次运行种子不同,攻击者无法预知)
- 冲突过多时把链表转成平衡树(Java 8 的 HashMap:链表 > 8 转红黑树)
哈希函数的要求
- 确定性:同样的 key 必须得到同样的值
- 均匀性:输出尽量均匀分布
- 快速:不能比遍历还慢
常见哈希函数
// 1. 整数:直接用(但要处理负数)
size_t h = (size_t)x;
// 2. 字符串:多项式哈希
size_t hash(const string& s) {
size_t h = 0;
for (char c : s) h = h * 131 + c; // 131、13331 等质数效果好
return h;
}
// 3. 组合多个字段
size_t hash(int a, int b) {
return hash<int>{}(a) ^ (hash<int>{}(b) << 1);
}
// 4. 常用:把 key 打散(防聚集)
size_t h = x * 0x9E3779B97F4A7C15ULL; // 黄金比例常数
h ^= h >> 32;为什么用质数做基数:减少规律性碰撞(如 "abc" 和 "acb" 在小基数下容易撞)。
字符串哈希(竞赛常用)
用于快速比较两个子串是否相等。
const long long B = 911382323; // 基数(大质数)
const long long M = 972663749;
// 预处理前缀哈希
vector<long long> h(n + 1, 0), pw(n + 1, 1);
for (int i = 0; i < n; i++) {
h[i + 1] = (h[i] * B + s[i]) % M;
pw[i + 1] = pw[i] * B % M;
}
// 子串 s[l..r) 的哈希(0-indexed)
long long get(int l, int r) {
return (h[r] - h[l] * pw[r - l] % M + M) % M;
}原理:把字符串看作 进制的大数。子串哈希 = 两个前缀哈希的差(再对齐位权)。
碰撞风险:单哈希有可能碰撞。用双哈希(两个不同的)可以把碰撞概率降到极低。或者用无符号整数自然溢出(unsigned long long,模)——也仍有理论碰撞风险。
注意:如果题目要卡你,构造碰撞是可能的。能不用哈希就不要用(用 KMP / Z 算法 / 后缀数组更稳妥),这是竞赛里的共识。
哈希的其他用途
1. 快速查找 / 去重
unordered_set<int> seen;
for (int x : a) { if (seen.count(x)) /* 重复 */; seen.insert(x); }2. 计数
unordered_map<int, int> freq;
for (int x : a) freq[x]++;3. 状态记忆化
把复杂状态(如棋盘局面)哈希成一个整数,用于记忆化搜索 / 判重。
4. 前缀和 + 哈希(见前缀和章节)
和为 k 的子数组个数:。
5. 集合的表示
用哈希值代表一个集合。判断两个集合是否相同 → 比较哈希值(有碰撞风险)。
6. 一致性哈希(分布式)
节点增减时,只迁移 的数据(而不是全部重分布)。分布式缓存的核心。
C++ 里的选择
| 容器 | 底层 | 复杂度 | 有序 |
|---|---|---|---|
unordered_map/set | 哈希表 | 均摊 | ✗ |
map/set | 红黑树 | ✓ |
选择依据:
需要 lower_bound / 前驱后继 / 有序遍历 → map/set
只需要 find / insert / 计数 → unordered_map/set(更快)
元素数量很小(< 100) → 用 vector 线性查找可能还更快(常数小)性能提示:
unordered_map的默认哈希对整数是恒等的 → 连续整数没问题,但有规律的 key 容易聚集- 预先
reserve(n)避免多次 rehash - 自定义类型要提供
std::hash特化或传入哈希函数对象
unordered_map<int, int> m;
m.reserve(1000000); // 避免扩容
m.max_load_factor(0.7); // 降低负载因子,用空间换时间常见坑
unordered_map的最坏复杂度:被卡数据时退化到,竞赛中可能被故意卡。可以用自定义哈希加随机种子- 自定义 key 没有
std::hash:编译错误。要么特化std::hash,要么传函数对象 operator[]会插入默认元素:if (m[k])会把k插进去。用m.count(k)或m.find(k)检查- 迭代器失效:
rehash后所有迭代器失效。插入过程中不要持有迭代器 reserve忘了调用:大量插入时反复 rehash,慢很多- 字符串哈希的碰撞:单哈希不可靠,用双哈希或改确定性算法
- 负数的模:
(-1) % 7在 C++ 里是-1,要(x % M + M) % M - 哈希值溢出:用
unsigned long long时溢出是定义良好的(模),但用int是 UB - 把哈希当加密:哈希不是加密,不可逆但可暴力碰撞。密码要用 bcrypt/Argon2 这类慢哈希,不能用 MD5/SHA1 直接存
许可协议:CC BY
作者:Davids
本文链接:https://hustjjd.github.io/718acd86.html
更新于:2026年11月16日