哈希函数
自动关联目录:哈希函数
哈希函数把任意长度数据映射成固定长度的值。它不是一个东西,而是两类需求——用错类别是最常见的问题。
两类哈希
| 类别 | 要求 | 代表 | 用途 |
|---|---|---|---|
| 非密码学哈希 | 快、分布均匀 | FNV、MurmurHash、CityHash、xxHash、CRC32 | 哈希表、缓存键、去重 |
| 密码学哈希 | 抗碰撞、抗原像、雪崩 | SHA-256、BLAKE3、SM3 | 完整性校验、签名、口令存储 |
核心区别:非密码学哈希只保证随机输入下分布好,构造碰撞很容易;密码学哈希要求即使刻意构造也找不到碰撞。
常见算法对比
| 算法 | 输出 | 速度 | 用途 | 备注 |
|---|---|---|---|---|
| CRC32 | 32 bit | 极快 | 校验传输误码 | 不是哈希用途,易构造碰撞 |
| FNV-1a | 32/64 bit | 很快 | 字符串键、编译期哈希 | 实现简单,质量一般 |
| MurmurHash3 | 32/128 bit | 很快 | 哈希表 | 质量好,通用首选 |
| xxHash | 32/64/128 | 极快 | 大数据校验和、缓存 | 非密码学里最快的之一 |
| MD5 | 128 bit | 快 | —— | 已攻破,禁止用于安全 |
| SHA-1 | 160 bit | 中 | —— | 已攻破,禁止用于安全 |
| SHA-256 | 256 bit | 中 | 签名、校验 | 当前主流 |
| BLAKE3 | 可变 | 很快 | 校验、完整性 | 并行友好,新项目可考虑 |
在游戏项目里的典型用法
| 场景 | 用什么 | 为什么 |
|---|---|---|
| 字符串 ID → 整数(如 GameplayTag、Name) | FNV / Murmur | 快,比较整数比字符串快得多 |
| 资源内容校验 | 密码学哈希(SHA-256/BLAKE3) | 要防止被构造出相同摘要 |
| 缓存 key | xxHash / Murmur | 量大,要快 |
| 热更新包校验 | 密码学哈希 + 签名 | 篡改即发现 |
| 网络包校验和 | CRC32 | 只检传输误码,不防攻击 |
注意:把字符串转成整数做比较时,必须意识到碰撞是存在的。工程上的做法通常是保留原始字符串,只在 debug 下校验"哈希冲突"。
陷阱
| 陷阱 | 说明 |
|---|---|
| 用 MD5/SHA-1 做安全校验 | 已被实际攻破 |
用 std::hash 的结果跨进程持久化 | 标准不保证稳定,实现可能变 |
| 把 CRC32 当去重键 | 32 位空间,碰撞概率很高(生日悖论) |
| 哈希不等于加密 | 哈希不可逆,但也不保密——加盐只对口令有意义 |
| 口令用快哈希 | 应该用慢的专用算法(bcrypt/Argon2/scrypt) |
生日悖论速算
位输出、 个输入时,期望碰撞数约为。
| 输出位数 | 大约多少条后碰撞概率 50% |
|---|---|
| 32 bit | 约 7.7 万条 |
| 64 bit | 约 50 亿条 |
| 128 bit | 约 条 |
这就是为什么"32 位哈希当唯一 ID"在小数据集上也迟早出问题。
许可协议:CC BY
作者:Davids
本文链接:https://hustjjd.github.io/e4aff432.html
更新于:2026年11月16日