选哈希算法时常有两个问题绑在一起：碰撞概率有多小、算得有多快。这篇把碰撞概率背后的数学（生日界）讲清楚，再用它算一算 256-bit 的 SHA-256/BLAKE3 与 128-bit 的 XXH128 各自的碰撞概率，最后附上一组本机实测速度数据。
本文所有实测数据均来自随机生成的字节串，不含任何业务或私有数据。
一、背景：碰撞概率的两种含义
对固定长度输出的哈希，“碰撞概率"必须分两种场景谈，否则会得出互相矛盾的结论：
- 随机碰撞：没有攻击者，数据是正常/随机的。这时只要输出在取值空间里均匀分布，碰撞概率就纯粹由输出位数决定，与具体算法无关。
- 抗恶意碰撞：有攻击者知道算法、故意构造两个哈希相同的输入。这里才真正区分加密哈希（SHA-256、BLAKE3、BLAKE2）和非加密哈希（xxHash、CityHash、Murmur）。
第一种是数学问题，用生日界就能算。第二种是密码学性质，非加密哈希直接不提供保证。
二、生日问题：直觉的陷阱
一个房间里要多少人，才有超过 50% 的概率存在两人同一天生日？答案是 23 人——远比直觉小。原因在于碰撞看的不是"某人和我同天”，而是"任意两人之间"的配对数：n 个人有 n(n-1)/2 ≈ n²/2 对，概率随 n² 增长。
哈希碰撞是同一个问题：把"人"换成"哈希输入"，把"365 天"换成"哈希空间大小 N"。对 128-bit 哈希，N = 2^128。
三、生日界公式的推导
设哈希空间大小为 N，独立均匀地放入 n 个值。直接算"至少一次碰撞"要用容斥，很麻烦，所以反过来算"全部不同"的概率：
第 1 个：随便放 → N/N
第 2 个：不能撞前 1 个 → (N-1)/N
...
第 n 个：不能撞前 n-1 个 → (N-n+1)/N
全部不同的概率是连乘：
P(无碰撞) = ∏_{k=0}^{n-1} (1 - k/N)
于是至少一次碰撞：
P(碰撞) = 1 - ∏_{k=0}^{n-1} (1 - k/N)
这是精确解，但连乘不好用。用近似 1 - x ≈ e^(-x)（x 很小时成立）把每一项换掉：
∏ (1 - k/N) ≈ ∏ e^(-k/N) = exp( -(1/N) · Σ_{k=0}^{n-1} k )
指数上是等差数列求和 Σ k = n(n-1)/2 ≈ n²/2，代回得到最常用的生日界公式：
P(碰撞) ≈ 1 - exp( -n² / (2N) )
当 n²/(2N) ≪ 1 时再简化一次（e^(-x) ≈ 1 - x）：
P(碰撞) ≈ n² / (2N)
这个形式最好用：碰撞概率随输入条数的平方增长——n 翻倍，概率变 4 倍。
50% 碰撞点为什么是 √N
令 P = 0.5：
exp(-n²/(2N)) = 0.5
n²/(2N) = ln 2
n = √(2 ln2 · N) ≈ 1.177 · √N
所以 50% 碰撞点 ≈ √N = 2^(位数/2)。
- 生日问题：
N=365 → n ≈ 1.177·√365 ≈ 23，对上了。 - 128-bit：
N=2^128 → n ≈ 2^64 ≈ 1.8×10^19。 - 256-bit：
N=2^256 → n ≈ 2^128。
这就是密码学里"n-bit 哈希的抗碰撞强度只有 2^(n/2)“的由来——不是 2^n，因为生日攻击把开销从 N 降到了 √N。
四、SHA-256（256-bit）的随机碰撞概率
N = 2^256 ≈ 1.16×10^77，代入 P ≈ n²/(2N)：
| 哈希条数 n | 至少一次碰撞概率(约) |
|---|---|
| 1×10^9 (十亿) | ~4×10^-60 |
| 1×10^12 (万亿) | ~4×10^-54 |
| 1×10^15 | ~4×10^-48 |
| 1×10^18 | ~4×10^-42 |
| 2^128 ≈ 3.4×10^38 | ~50% |
要哈希约 2^128 ≈ 3.4×10^38 个不同值才有 50% 概率撞一次。这个数字超出任何现实规模——即便调动全球算力持续运行，也无法接近。所以 256-bit 的随机碰撞可以当作永远不会发生。
五、XXH128（128-bit）的随机碰撞概率
N = 2^128 ≈ 3.4×10^38，代入 P ≈ n²/(2N)：
| 哈希条数 n | 至少一次碰撞概率(约) |
|---|---|
| 1×10^6 (百万) | ~1.5×10^-27 |
| 1×10^9 (十亿) | ~1.5×10^-21 |
| 1×10^12 (万亿) | ~1.5×10^-15 |
| 1×10^15 | ~1.5×10^-9 |
| 2^64 ≈ 1.8×10^19 | ~50% |
要哈希约 2^64 ≈ 1.8×10^19 个不同值才有 50% 概率撞一次。换个体感：每秒哈希 10 亿条、不停跑 100 年（约 3×10^18 条），碰撞概率仍在 ~10^-3 以下。对去重、分片、缓存 key 这类场景，128-bit 的随机碰撞实际可以忽略。
xxHash 官方用 SMHasher 测试套件验证过其分布质量（雪崩效应、无明显偏置），所以"均匀分布"这个前提在实践中站得住。
但 XXH128 不抗恶意碰撞
这是它与位数无关的根本短板：XXH128 是非加密哈希，不提供密码学抗碰撞保证。攻击者若知道算法（开源、种子公开），能以远低于 2^64 的代价主动构造出哈希相同的两个输入。因此：
- 不能用于数字签名、内容寻址防伪、完整性校验、防 hash-flooding 的 DoS 防护等安全用途；
- 这些场景必须用加密哈希（SHA-256 / BLAKE3 / BLAKE2），它们的抗碰撞代价是
2^(n/2)且没有已知捷径。
六、实测速度对比
在同一台机器上测了一组，数据集为随机字节串、按不同长度分档，每档 200 万次调用取中位数。测试环境：Intel Xeon Silver 4310（支持 sha_ni / avx2 / avx512f），加密哈希用 Rust（release + LTO + target-cpu=native），XXH128 用官方 C 版 xxHash v0.8.2（-O3，AVX2 路径）。
单次哈希耗时中位数（纳秒），值越小越快：
| 长度 | SHA-256 | BLAKE3 | BLAKE2b-256 | SHA3-256 | XXH128(AVX2) |
|---|---|---|---|---|---|
| 16 B | 113 | 118 | 234 | 567 | 28 |
| 64 B | 177 | 111 | 232 | 556 | 32 |
| 256 B | 341 | 321 | 430 | 1058 | 52 |
| 1024 B | 1024 | 1121 | 1591 | 4071 | 76 |
| 4096 B | 3761 | 1370 | 6234 | 15660 | 220 |
吞吐量（MB/s），值越大越快（4096 B 档）：
| 算法 | 吞吐 |
|---|---|
| XXH128 (AVX2) | ~14600 |
| BLAKE3 | ~2700 |
| SHA-256 | ~1026 |
| BLAKE2b-256 | ~621 |
| SHA3-256 | ~247 |
XXH128 的 SIMD 路径差异（AVX2 vs SSE2）
用 XXH_VECTOR 宏强制钉死向量路径，单次耗时中位数（ns）：
| 长度 | scalar | SSE2 | AVX2 | AVX512 |
|---|---|---|---|---|
| 16 B | 28 | 28 | 28 | 28 |
| 64 B | 32 | 32 | 32 | 32 |
| 256 B | 66 | 54 | 52 | 56 |
| 1024 B | 140 | 94 | 76 | 78 |
| 4096 B | 474 | 288 | 220 | 204 |
要点：小输入（≤64 B）走的是标量短路径，四条路径完全一样，SIMD 加速无效；分水岭在 ~256 B 以上，数据越大 AVX2 相对 SSE2/scalar 优势越明显；AVX2 与 AVX512 基本打平，而 AVX512 在部分型号上会触发降频，通常 AVX2 更划算。
七、结论
- 随机碰撞概率只看位数：256-bit 需
2^128条、128-bit 需2^64条才有 50% 概率碰撞，两者在现实规模下都可视为不发生。 - 是否抗恶意碰撞才是选型关键：加密哈希（SHA-256/BLAKE3/BLAKE2）抗攻击，非加密哈希（XXH128）不抗。
- 选型建议：
- 需要 32 B 输出 + 抗攻击 + 快 → BLAKE3（大块数据吞吐领先，且支持多线程）。
- 要生态最稳、机器有 SHA-NI → SHA-256。
- 纯内部散列（哈希表、分片、去重），不怕攻击、只求极致速度 → XXH128，但绝不可用于安全场景。
核心记忆：碰撞概率 ≈ n²/(2N)，50% 碰撞点 ≈ √N = 2^(位数/2)。看的是两两配对数，所以概率随 n² 涨，撞上只需 √N 而非 N。