本课时有配套视频讲解，购买后即可观看（永久有效）
数值哈希函数的构造
一、课上练习
编程练习
二、知识总结
✨ 核心思想
哈希函数的核心目标是将任意范围的键映射到固定范围的整数（即数组下标），同时让映射尽可能均匀分布，减少冲突。
对于数值类型的键（整数），常见的哈希函数构造方法包括：
- 除余法（取模法）：最常用，简单高效
- 乘法哈希：理论性质更好，对表大小无特殊要求
- 全域哈希（Universal Hashing）：随机化选择哈希函数，期望冲突最少
选择合适的哈希函数对哈希表的性能至关重要。一个好的哈希函数能将冲突率降到最低，使操作接近 $O(1)$。
✨ 算法原理
方法一：除余法（Division Method）
$$h(k) = k \bmod m$$
将键 $k$ 对表大小 $m$ 取模。
$m$ 的选取原则：
- $m$ 应为质数，且不接近 2 的幂
- 若 $m = 2^p$，则 $h(k)$ 只取决于 $k$ 的低 $p$ 位，信息损失严重
- 推荐选择远离 2 的幂次的质数，如 $10007$、$999983$、$1000003$
方法二：乘法哈希（Multiplicative Hashing）
$$h(k) = \lfloor m \cdot (k \cdot A \bmod 1) \rfloor$$
其中 $A$ 是一个 $(0, 1)$ 之间的无理数常量，$k \cdot A \bmod 1$ 表示取小数部分。
Knuth 推荐：$A = \frac{\sqrt{5} - 1}{2} \approx 0.6180339887$（黄金比例的倒数）
优点：对 $m$ 的选择不敏感，$m$ 可以是 2 的幂（方便位运算）
整数实现技巧： $$h(k) = (k \times A') \gg (w - p)$$ 其中 $w$ 是机器字长，$A' = \lfloor A \times 2^w \rfloor$，$m = 2^p$。
方法三：全域哈希（Universal Hashing）
从一族哈希函数中随机选择一个：
$$h_{a,b}(k) = ((a \cdot k + b) \bmod p) \bmod m$$
其中：
- $p$ 是一个大于所有可能键值的质数
- $a \in {1, 2, ..., p-1}$，$b \in {0, 1, ..., p-1}$，均随机选取
性质：对于任意两个不同的键 $k1 \neq k2$，冲突概率 $\leq \frac{1}{m}$。
这意味着无论输入数据如何分布，期望的冲突次数都很少。在竞赛中可以有效防止出题人构造的恶意数据。
方法四：斐波那契哈希（Fibonacci Hashing）
这是乘法哈希的一种特殊实现：
$$h(k) = (k \times 2654435769) \gg (32 - p)$$
其中 $2654435769 = \lfloor 2^{32} \cdot \frac{\sqrt{5}-1}{2} \rfloor$，$m = 2^p$。
用整数乘法和位移代替浮点运算，速度极快。
✨ 代码实现
除余法
hash_division.cpp
1#include <iostream>
2using namespace std;
3
4const int MOD = 999983; // 大质数
5
6int hashDiv(int key) {
7 return ((key % MOD) + MOD) % MOD; // 处理负数
8}
9
10int main() {
11 // 测试不同键的哈希值分布
12 int keys[] = {42, 1000000, -7, 123456789, 0};
13 for (int k : keys) {
14 cout << "h(" << k << ") = " << hashDiv(k) << endl;
15 }
16 return 0;
17}乘法哈希（浮点版）
hash_multiplicative_float.cpp
1#include <iostream>
2#include <cmath>
3using namespace std;
4
5const int TABLE_SIZE = 1024; // 可以是2的幂
6const double A = (sqrt(5.0) - 1.0) / 2.0; // 黄金比例
7
8int hashMul(int key) {
9 double val = key * A;
10 val = val - floor(val); // 取小数部分
11 return (int)(TABLE_SIZE * val);
12}
13
14int main() {
15 int keys[] = {1, 2, 3, 100, 200, 300, 12345};
16 for (int k : keys) {
17 cout << "h(" << k << ") = " << hashMul(k) << endl;
18 }
19 return 0;
20}乘法哈希（整数位运算版，推荐）
hash_multiplicative_int.cpp
1#include <iostream>
2using namespace std;
3
4// 表大小为 2^p
5const int P = 10; // 2^10 = 1024
6const unsigned int A_PRIME = 2654435769u; // floor(2^32 * (sqrt(5)-1)/2)
7
8int hashMulInt(int key) {
9 // 利用无符号整数溢出自动取模 2^32
10 unsigned int val = (unsigned int)key * A_PRIME;
11 return val >> (32 - P); // 取高 P 位
12}
13
14int main() {
15 int keys[] = {1, 2, 3, 100, 200, 300, 12345};
16 for (int k : keys) {
17 cout << "h(" << k << ") = " << hashMulInt(k) << endl;
18 }
19 return 0;
20}全域哈希
hash_universal.cpp
1#include <iostream>
2#include <cstdlib>
3#include <ctime>
4using namespace std;
5
6const int TABLE_SIZE = 10007;
7const long long PRIME = 1000000007LL; // 大质数
8
9long long a, b; // 随机选取的参数
10
11// 初始化：随机选取 a, b
12void initHash() {
13 srand(time(0));
14 a = rand() % (PRIME - 1) + 1; // a ∈ [1, p-1]
15 b = rand() % PRIME; // b ∈ [0, p-1]
16}
17
18int hashUniversal(int key) {
19 long long k = key;
20 // 处理负数
21 k = ((k % PRIME) + PRIME) % PRIME;
22 long long h = ((a * k + b) % PRIME) % TABLE_SIZE;
23 return (int)h;
24}
25
26int main() {
27 initHash();
28 cout << "随机参数: a=" << a << ", b=" << b << endl;
29
30 int keys[] = {42, 100, 200, 300, 1000000};
31 for (int k : keys) {
32 cout << "h(" << k << ") = " << hashUniversal(k) << endl;
33 }
34
35 return 0;
36}竞赛中防 hack 的自定义哈希
hash_anti_hack.cpp
1#include <iostream>
2#include <unordered_map>
3#include <chrono>
4using namespace std;
5
6// 自定义哈希函数，防止被恶意数据卡掉
7struct SafeHash {
8 static uint64_t splitmix64(uint64_t x) {
9 x += 0x9e3779b97f4a7c15;
10 x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
11 x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
12 return x ^ (x >> 31);
13 }
14
15 size_t operator()(uint64_t x) const {
16 // 使用程序启动时间作为随机种子
17 static const uint64_t FIXED_RANDOM =
18 chrono::steady_clock::now().time_since_epoch().count();
19 return splitmix64(x + FIXED_RANDOM);
20 }
21};
22
23int main() {
24 // 使用自定义哈希的 unordered_map
25 unordered_map<int, int, SafeHash> mp;
26
27 mp[42] = 100;
28 mp[17] = 200;
29
30 for (auto& [k, v] : mp) {
31 cout << k << " -> " << v << endl;
32 }
33
34 return 0;
35}✨ 执行示例
除余法分布测试
1表大小 m = 7，键: 10, 22, 31, 4, 15, 28, 17
2
3h(10) = 10 % 7 = 3
4h(22) = 22 % 7 = 1
5h(31) = 31 % 7 = 3 ← 与 10 冲突
6h(4) = 4 % 7 = 4
7h(15) = 15 % 7 = 1 ← 与 22 冲突
8h(28) = 28 % 7 = 0
9h(17) = 17 % 7 = 3 ← 与 10, 31 冲突
10
11冲突率: 7个键中有4个发生冲突（因为 m 太小）乘法哈希分布测试
1表大小 m = 16, A = 0.618034...
2
3h(1) = floor(16 × (1 × 0.618034... mod 1)) = floor(16 × 0.618034) = 9
4h(2) = floor(16 × (2 × 0.618034... mod 1)) = floor(16 × 0.236068) = 3
5h(3) = floor(16 × (3 × 0.618034... mod 1)) = floor(16 × 0.854102) = 13
6h(4) = floor(16 × (4 × 0.618034... mod 1)) = floor(16 × 0.472136) = 7
7h(5) = floor(16 × (5 × 0.618034... mod 1)) = floor(16 × 0.090170) = 1
8
9分布: 9, 3, 13, 7, 1 → 非常均匀，无冲突！✨ 解题步骤详解
如何选择哈希函数
- 一般竞赛题：除余法取大质数（如 $999983$）即可
- 防 hack / 交互题：使用全域哈希或 splitmix64 + 随机种子
- 需要极致速度：斐波那契哈希（整数乘法 + 位移）
- 数据范围在 $[0, 10^6]$：直接数组映射，不需要哈希
质数表（常用）
| 用途 | 推荐质数 |
|---|---|
| 小表 ($10^3$ 级) | 1009, 2003, 5003 |
| 中表 ($10^4$ 级) | 10007, 20011, 50021 |
| 大表 ($10^5$ 级) | 100003, 200003, 500009 |
| 特大表 ($10^6$ 级) | 999983, 1000003 |
多重哈希
对于需要极低冲突率的场景（如字符串哈希判等），可以同时使用多个不同的哈希函数，只有所有哈希值都相同才判定为相等。
✨ 常见错误
- 表大小选了 2 的幂用除余法：$k \bmod 2^p$ 只保留低 $p$ 位，分布极差
- 忘记处理负数：C++ 中
-7 % 5可能等于-2，需要加上模数再取模 - 乘法哈希用了 float：精度不够，应该用 double 或整数实现
- 全域哈希的 $a$ 选了 0：$a$ 必须在 $[1, p-1]$ 范围内，$a=0$ 会使所有键映射到同一位置
- 质数选得太小：导致冲突严重，表大小应与数据规模匹配
- 使用
unordered_map时忽略被卡的风险：在 Codeforces 等平台，默认哈希可能被构造数据卡掉
✨ 算法评价
各方法对比
| 方法 | 计算速度 | 分布均匀性 | 对 m 的要求 | 抗攻击性 |
|---|---|---|---|---|
| 除余法 | 快 | 一般 | 须为质数 | 差 |
| 乘法哈希 | 中等 | 好 | 无 | 差 |
| 斐波那契哈希 | 极快 | 好 | 须为 2 的幂 | 差 |
| 全域哈希 | 中等 | 理论最优 | 无 | 强 |
| splitmix64 | 快 | 极好 | 无 | 强 |
理论保证
- 除余法：若 $m$ 为质数，简单均匀哈希假设下冲突率为 $\frac{1}{m}$
- 全域哈希：对任意两个不同键，冲突概率 $\leq \frac{1}{m}$（无需假设输入分布）
- 乘法哈希：Knuth 证明黄金比例常数能使哈希值在 $[0, m)$ 上近似均匀分布
实践建议
竞赛中推荐的默认选择：
- 手写哈希表：除余法 + 大质数
- STL unordered_map：自定义 splitmix64 哈希 + 随机种子