哈希函数

自动关联目录:哈希函数

哈希函数把任意长度数据映射成固定长度的值。它不是一个东西,而是两类需求——用错类别是最常见的问题。

两类哈希

类别要求代表用途
非密码学哈希快、分布均匀FNV、MurmurHash、CityHash、xxHash、CRC32哈希表、缓存键、去重
密码学哈希抗碰撞、抗原像、雪崩SHA-256、BLAKE3、SM3完整性校验、签名、口令存储

核心区别:非密码学哈希只保证随机输入下分布好,构造碰撞很容易;密码学哈希要求即使刻意构造也找不到碰撞。

常见算法对比

算法输出速度用途备注
CRC3232 bit极快校验传输误码不是哈希用途,易构造碰撞
FNV-1a32/64 bit很快字符串键、编译期哈希实现简单,质量一般
MurmurHash332/128 bit很快哈希表质量好,通用首选
xxHash32/64/128极快大数据校验和、缓存非密码学里最快的之一
MD5128 bit快——已攻破,禁止用于安全
SHA-1160 bit中——已攻破,禁止用于安全
SHA-256256 bit中签名、校验当前主流
BLAKE3可变很快校验、完整性并行友好,新项目可考虑

在游戏项目里的典型用法

场景用什么为什么
字符串 ID → 整数(如 GameplayTag、Name)FNV / Murmur快,比较整数比字符串快得多
资源内容校验密码学哈希(SHA-256/BLAKE3)要防止被构造出相同摘要
缓存 keyxxHash / Murmur量大,要快
热更新包校验密码学哈希 + 签名篡改即发现
网络包校验和CRC32只检传输误码,不防攻击

注意:把字符串转成整数做比较时,必须意识到碰撞是存在的。工程上的做法通常是保留原始字符串,只在 debug 下校验"哈希冲突"。

陷阱

陷阱说明
用 MD5/SHA-1 做安全校验已被实际攻破
用 std::hash 的结果跨进程持久化标准不保证稳定,实现可能变
把 CRC32 当去重键32 位空间,碰撞概率很高(生日悖论)
哈希不等于加密哈希不可逆,但也不保密——加盐只对口令有意义
口令用快哈希应该用慢的专用算法(bcrypt/Argon2/scrypt)

生日悖论速算

nn 位输出、kk 个输入时,期望碰撞数约为k2/2n+1k^2 / 2^{n+1}。

输出位数大约多少条后碰撞概率 50%
32 bit约 7.7 万条
64 bit约 50 亿条
128 bit约2×10192 \times 10^{19} 条

这就是为什么"32 位哈希当唯一 ID"在小数据集上也迟早出问题。