哈希

选哈希算法时常有两个问题绑在一起：碰撞概率有多小、算得有多快。这篇把碰撞概率背后的数学（生日界）讲清楚，再用它算一算 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 很小时成立）把每一项换掉： ...