Hash

自动关联目录:Hash

哈希(Hash)回答的是:如何用O(1)O(1) 的代价,判断"我见过这个东西吗"。

它的代价是放弃有序性——哈希表里取不出"最小的元素",也做不了范围查询。

需要范围查询 / 有序遍历  → 平衡树(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

两个必要组件:

  1. 哈希函数:key → 数组下标,尽量均匀
  2. 冲突处理:不同 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;
}

负载因子α=n/m\alpha = n / m(元素数 / 桶数)。α\alpha 越大,链表越长。

扩容:α>0.75\alpha > 0.75(典型阈值)时,桶数翻倍并重新散列(rehash)。均摊O(1)O(1)。

开放寻址(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)用开放寻址,因为缓存友好得多。

复杂度

操作平均最坏
查找 / 插入 / 删除O(1)O(1)O(n)O(n)

最坏情况:所有 key 都映射到同一个桶(哈希函数太差或被恶意构造)。

这就是 Hash DoS 攻击:攻击者构造大量碰撞的 key,把O(1)O(1) 退化成O(n)O(n),耗尽服务器 CPU。

防护:

  • 用带随机种子的哈希函数(每次运行种子不同,攻击者无法预知)
  • 冲突过多时把链表转成平衡树(Java 8 的 HashMap:链表 > 8 转红黑树)

哈希函数的要求

  1. 确定性:同样的 key 必须得到同样的值
  2. 均匀性:输出尽量均匀分布
  3. 快速:不能比遍历还慢

常见哈希函数

// 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" 在小基数下容易撞)。

字符串哈希(竞赛常用)

用于快速比较两个子串是否相等。

H(s)=∑i=0n−1s[i]⋅Bn−1−i(modM)H(s) = \sum_{i=0}^{n-1} s[i] \cdot B^{n-1-i} \pmod M

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;
}

原理:把字符串看作BB 进制的大数。子串哈希 = 两个前缀哈希的差(再对齐位权)。

碰撞风险:单哈希有可能碰撞。用双哈希(两个不同的(B,M)(B, M))可以把碰撞概率降到极低。或者用无符号整数自然溢出(unsigned long long,模2642^{64})——也仍有理论碰撞风险。

注意:如果题目要卡你,构造碰撞是可能的。能不用哈希就不要用(用 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 的子数组个数:O(n2)→O(n)O(n^2) \to O(n)。

5. 集合的表示

用哈希值代表一个集合。判断两个集合是否相同 → 比较哈希值(有碰撞风险)。

6. 一致性哈希(分布式)

节点增减时,只迁移1/n1/n 的数据(而不是全部重分布)。分布式缓存的核心。

C++ 里的选择

容器底层复杂度有序
unordered_map/set哈希表O(1)O(1) 均摊✗
map/set红黑树O(log⁡n)O(\log n)✓

选择依据:

需要 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 的最坏复杂度:被卡数据时退化到O(n)O(n),竞赛中可能被故意卡。可以用自定义哈希加随机种子
  • 自定义 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 时溢出是定义良好的(模2642^{64}),但用 int 是 UB
  • 把哈希当加密:哈希不是加密,不可逆但可暴力碰撞。密码要用 bcrypt/Argon2 这类慢哈希,不能用 MD5/SHA1 直接存