rustc-hash 性能基准实测:单整数哈希速度为何碾压 SipHash,编译器加速的真相
rustc-hash 性能基准实测:单整数哈希速度为何碾压 SipHash,编译器加速的真相
rustc-hash 是 Rust 编译器 rustc 内部使用的极速非加密哈希库,提供 FxHashMap/FxHashSet 集合别名。本文通过性能基准实测思路对比它与标准库默认的 SipHash,拆解单整数哈希为何只需一次加法+一次乘法就能大幅领先加密级哈希,并揭开编译器加速背后的取舍真相。
rustc-hash 是什么:编译器同款快速哈希库
Rust 标准库的 HashMap 默认使用 SipHash——一种抗 HashDoS 攻击的加密级哈希。但对编译器这类"输入可控"的工具来说,这种安全冗余是纯粹的 CPU 开销。
rustc-hash 正是为此而生:一个快速、确定性(非加密)的哈希算法库,核心构件包括:
| 构件 | 作用 |
|---|---|
FxHasher |
核心哈希器,多项式哈希 + 单次位旋转收尾 |
FxBuildHasher |
构建 FxHasher 的工厂,默认种子为 0 |
FxHashMap / FxHashSet |
标准库 HashMap/HashSet 的别名,换用 Fx 哈希 |
FxSeededState |
自定义种子的构建器,结果可复现 |
FxRandomState |
随机种子(需 rand feature),抗迭代顺序枚举 |
📌 历史沿革:库最初的算法来自 Firefox 的 "FxHasher",2.0 版本被 Orson Peters 设计的全新多项式哈希替换,实测在
rustc上性能更好、理论性质更强(见 CHANGELOG.md)。
性能基准实测:单整数哈希为何碾压 SipHash
基准测试中最经典的场景就是单整数哈希——这正是 rustc 的痛点:编译器要反复对大量 u32/u64 类型的枚举索引、符号编号做哈希。
看核心实现 src/lib.rs,把整数混入哈希的全部计算只有这一行:
fn add_to_hash(&mut self, i: usize) {
self.hash = self.hash.wrapping_add(i).wrapping_mul(K);
}
一次加法 + 一次乘法,仅此而已。K 是一个经过精心挑选的多项式乘法常数(64 位平台为 0xf1357aea2e62a9c5,取自经典文献中"频谱优良"的 MCG 乘数),定义见 src/lib.rs。
收尾函数 finish() 也只是把结果左移 26 位(32 位平台为 15 位),见 src/lib.rs——位旋转是 x86-64 上 1 个时钟周期的廉价指令。
对比 SipHash-1-3:它需要多轮"加-旋-异或-乘"循环来抵抗碰撞攻击,处理一个整数往往需要十几条指令级别的混合运算。而 FxHasher 全程只有 3 条简单 ALU 指令。
这就是基准实测中单整数场景 FxHashMap 大幅领先的原因:指令数差距是数量级的。官方在 README.md 中也明确写道:
"Hashing speed is critical, especially for single integers. Spending more CPU cycles on a higher quality hash does not reduce hash collisions enough to make the compiler faster on real-world benchmarks."
(哈希速度至关重要,尤其是单整数。在真实基准测试中,花更多 CPU 周期做更高质量的哈希,并不能减少足够多的碰撞来让编译器变快。)
编译器加速的真相:取舍全在"碰撞率不值钱"
编译器场景有三个特点,决定了它的选型逻辑:
- 输入不可信程度低:被哈希的是编译器自己生成的标识符和内部索引,不存在恶意构造的 HashDoS 攻击者;
- 哈希次数极多:一次编译产生数百万次整数/字符串哈希,省下的每个周期都被放大;
- 碰撞代价可承受:哈希表遇到碰撞退化为链表查找,少量碰撞对总编译时间影响甚微。
因此结论很直接:用更慢的加密哈希去换"更少的碰撞",在编译器工作负载下是负收益。这套"快而不安全"的取舍,就是 rustc 内部用 FxHasher 而非 SipHash 的全部真相。
字符串哈希也不慢:wyhash 启发的压缩函数
如果只优化整数,这个库就不算完整。rustc-hash 对字节串使用了受 wyhash 启发的压缩函数 hash_bytes:
- 短串(≤16 字节):直接把首/尾几个字节异或进两个状态寄存器,再做一次乘法混合;
- 长串:以 16 字节为步长分块,两个独立寄存器交替处理,方便编译器循环展开成双流水;
- 核心混合函数 multiply_mix 计算完整的
u64 × u64 → u128乘积,用低 64 位异或高 64 位——中间位对输入变化最敏感,从而让输出充分"雪崩"。
64 位版本还通过了 SMHasher3 全部测试套件(完整输出零失败),说明它在快的同时分布质量也站得住脚。
快速上手:3 步把 FxHashMap 接入你的 Rust 项目
第 1 步:添加依赖,在 Cargo.toml 中加一行:
[dependencies]
rustc-hash = "2.1"
第 2 步:替换集合类型。FxHashMap/FxHashSet 就是换用 Fx 哈希的 HashMap/HashSet 类型别名(定义见 src/lib.rs),API 完全兼容,迁移零成本:
use rustc_hash::FxHashMap;
let mut map: FxHashMap<u32, u32> = FxHashMap::default();
map.insert(22, 44);
第 3 步(可选):关闭 std 用于嵌入式。no_std 环境只需 Cargo.toml 中的 std feature 置空:
rustc-hash = { version = "2.1", default-features = false }
💡 提示:库本身是 #![no_std] 编写的,纯算法部分在任何环境都能跑。
进阶选项:FxSeededState 与 FxRandomState 怎么选
默认 FxBuildHasher 种子固定为 0——快速但确定性的。如果你的场景需要,还有两个替代构建器:
FxSeededState(src/seeded_state.rs):with_seed(n)指定固定种子,同种子必然产生相同哈希,适合测试可复现、序列化等需要确定性行为的场景;FxRandomState(src/random_state.rs,需开启randfeature):每个线程持有一个线程本地随机种子,模仿标准库RandomState的行为——同一线程连续创建的 map 迭代顺序不同,可阻止攻击者预测你的哈希桶布局,但哈希本身依然是非加密的。
rustc-hash 与 SipHash 选型对比表
| 维度 | rustc-hash(FxHasher) | SipHash(std 默认) |
|---|---|---|
| 单整数哈希开销 | 加+乘+旋转,约 3 条指令 | 多轮混合运算,慢一个量级 |
| 抗 HashDoS | ❌ 无 | ✅ 有 |
| 结果确定性 | ✅ 同输入同输出(固定种子) | ❌ 每次进程运行随机种子 |
| 字符串哈希 | wyhash 风格压缩,短串特化 | 逐块 ARX 混合 |
| 适用场景 | 编译器、内部工具、离线处理、游戏 | 暴露于不可信输入的公开服务 |
⚠️ 一句话选型:输入来自你控制的环境 → rustc-hash 更快;输入来自外部不可信来源 → 保留 SipHash 的 RandomState,别拿 Fx 哈希裸奔。
总结
rustc-hash 用最小的算法开销回答了编译器工程里最实际的优化问题:
- 单整数哈希 = 一次加法、一次乘法、一次位旋转,这正是基准实测中碾压 SipHash 的根本原因;
- 编译器"加速的真相"不是碰撞率优化,而是在安全冗余不产生价值的场景里彻底省掉它;
FxHashMap/FxHashSet与标准库完全同构,一行依赖即可完成迁移;- 记住它的定位:fast, deterministic, not secure——快、确定、不加密,三者缺一不可地构成它的选型边界。