← ToolBox / 哈希碰撞概率

#️⃣ Hash Collision Probability

Estimate birthday-paradox collision probability from hash-space bits and stored item count; risk rises sharply as n approaches the square root of 2^bits.

哈希输出位数

条目数

📐 计算公式与说明

编码空间与碰撞概率：编码空间大小 = 2^bits；近似碰撞概率 P = (1 − exp(−n(n−1) ÷ (2×2^bits))) × 100（%，生日悖论近似，n 为取数个数）；安全阈值 n = √(2×2^bits)。校验：无强校验，空/非法值按 0 兜底。判据：无固定分级，位宽每 +1 编码空间翻倍，同规模取数下碰撞概率显著下降。

当 n 接近 √2^bits 时碰撞概率显著上升。

📚 深度解析：哈希碰撞概率

💡 常见使用场景

去重/分桶设计：评估哈希桶规模接近平方根时冲突陡增的风险。
唯一 ID 规划：为短 ID 选择足够位宽以控制业务内碰撞率。
安全边界：说明短哈希用于标识而非防碰撞的极限。

示例：32 位哈希、7.7 万条

约 5 万条时碰撞概率已近 1%，接近 √(2^32)≈6.5 万后快速上升，需升到 64 位。

❓ 常见问题（FAQ）

为何是平方根？: 生日悖论下碰撞概率在条目数约 √(2·2^bits) 量级开始显著，而非 2^bits。
碰撞了怎么办？: 业务去重应级联二次校验（如原值比对），不能只信哈希相等。
多大空间才安全？: 抗意外碰撞 64 位通常足够；抗故意碰撞需 128 位以上加密哈希。

Formula & Standard References

Item	Formula / Rule	Source / Standard
Collision probability	p ≈ 1 − exp(−n² / (2N)) with N = 2^b the output space	NIST SP 800-107 Rev.1 §4 hash function security
Fifty-percent point	p = 0.5 needs n ≈ 1.1774 × √N, roughly 2^b/2 trials	NIST SP 800-107 Rev.1 §4 birthday bound
Small-p approximation	For small p, p ≈ n² / (2N), growing with the square of the message count	Menezes et al., Handbook of Applied Cryptography, Ch. 2

哈希碰撞概率