6 哈希

译文 · 基于 The Rust Performance Book

哈希

原文链接: https://nnethercote.github.io/perf-book/hashing.html

HashSet 和 HashMap 是两种广泛使用的类型，有办法使它们更快。

替代哈希算法

默认哈希算法未作规定，但截至撰写时，默认算法是称为 SipHash 1-3 的算法。该算法质量高——提供强大的防碰撞保护——但相对较慢，尤其是对整数等短键而言。

如果性能分析显示哈希是热点，且 HashDoS 攻击对你的应用不构成威胁，使用具有更快哈希算法的哈希表可以带来显著的速度提升。

• rustc-hash 提供 FxHashSet 和 FxHashMap 类型，可作为 HashSet 和 HashMap 的直接替代。其哈希算法质量较低但非常快，尤其对整数键而言，在 rustc 内部的表现优于所有其他哈希算法。（fxhash 是同一算法和类型的较旧、维护较少的实现。）
• fnv 提供 FnvHashSet 和 FnvHashMap 类型。其哈希算法质量高于 rustc-hash，但稍慢一些。
• ahash 提供 AHashSet 和 AHashMap。其哈希算法可利用部分处理器上可用的 AES 指令支持。

如果哈希性能对你的程序很重要，值得尝试多种替代方案。例如，在 rustc 中观察到以下结果。

• 从 fnv 切换到 fxhash 带来了最高 6% 的加速。
• 尝试从 fxhash 切换到 ahash 导致了 1–4% 的减速。
• 尝试从 fxhash 切换回默认哈希器导致了 4–84% 的减速！

如果你决定普遍使用某种替代方案，例如 FxHashSet/FxHashMap，很容易在某些地方误用 HashSet/HashMap。你可以使用 Clippy来避免此问题。

有些类型不需要哈希。例如，你可能有一个包装整数的新类型，且整数值是随机的或接近随机的。对于此类类型，哈希值的分布与值本身的分布不会有太大差异。在这种情况下，nohash_hasher crate 可能很有用。

哈希函数设计是一个复杂的话题，超出了本书的范围。ahash 文档中有很好的讨论。

按字节哈希

当你用 #[derive(Hash)] 标注类型时，生成的 hash 方法会分别哈希每个字段。对于某些哈希函数，将类型转换为原始字节并将字节作为流进行哈希可能更快。这对于满足某些属性（例如没有填充字节）的类型是可行的。

zerocopy 和 bytemuck crate 都提供 #[derive(ByteHash)] 宏，生成执行此类按字节哈希的 hash 方法。derive_hash_fast crate 的 README 对此技术有更多细节。

这是一项高级技术，性能影响高度依赖于哈希函数和被哈希类型的确切结构。请仔细测量。