用于顺序键的更快的 HashMap

Question

最初，我非常惊讶地发现HashMap，即使使用FNV哈希器，Rust 的速度也比 Java、.NET、PHP 中的等效项慢得多。我说的是优化的Release模式，而不是Debug模式。我做了一些计算，发现 Java/.NET/PHP 中的计时值低得令人怀疑。然后它击中了我 - 尽管我正在使用一个大哈希表（数百万个条目）进行测试，但我读取的主要是顺序键值（如14, 15, 16, ...），这显然导致了大量CPU 缓存命中，这是由于标准哈希表的方式（以及整数和短字符串的哈希码函数）在这些语言中被实现，因此具有附近键的条目通常位于附近的内存位置。

HashMap另一方面，Rust使用所谓的SwissTable实现，它显然以不同的方式分配值。当我测试随机键的阅读时，一切都井然有序——“竞争对手”的得分落后于 Rust。

因此，如果我们处于需要按顺序执行大量获取的情况，例如迭代一些有序且大部分是连续的（没有太多间隙）的 DB ID，是否有一个好的 Rust 哈希映射实现可以与 Java 竞争HashMap或者.NET 的Dictionary？

---

PS 根据评论中的要求，我在这里粘贴一个示例。我运行了大量测试，但这里有一个简单的示例，在 Rust（发布模式）中需要 75 毫秒，在 Java 中需要 20 毫秒：

在铁锈中：

let hm: FnvHashMap<i32, i32> = ...;  
// Start timer here
let mut sum: i64 = 0;
for i in 0..1_000_000 {
    if let Some(x) = hm.get(&i) {
        sum += *x as i64;
    }
}
println!("The sum is: {}", sum);

在爪哇中：

Map<Integer, Integer> hm = ...;
// Start timer here
long sum = 0;
for (int i = 0; i < 1_000_000; i++) {
    sum += hm.get(i);
}

使用HashMap<i32, i32>其默认SipHash哈希器需要 190 毫秒。我知道为什么它比 慢FnvHashMap。我只是为了完整性而提及这一点。

Answer 1

首先，这是一些可运行的代码，用于衡量不同实现的效率：

use std::{collections::HashMap, time::Instant};

fn main() {
    let hm: HashMap<i32, i32> = (0..1_000_000).map(|i| (i, i)).collect();
    let t0 = Instant::now();
    let mut sum = 0;
    for i in 0..1_000_000 {
        if let Some(x) = hm.get(&i) {
            sum += x;
        }
    }
    let elapsed = t0.elapsed().as_secs_f64();
    println!("{} - The sum is: {}", elapsed, sum);
}

在我写这篇文章的旧台式机上，它报告运行时间为 76 毫秒。由于机器已有 10 多年的历史，我发现令人困惑的是您的硬件需要 190 毫秒才能运行相同的代码，所以我想知道您实际测量的方式和内容。但让我们忽略这一点并专注于相对数字。

当您关心 Rust 中的哈希映射效率时，并且当密钥不是来自不受信任的来源时，首先要尝试的应该始终是切换到不抗 DOS 的哈希函数。一种可能性是来自板条箱的 FNV 哈希函数fnv，您可以通过切换HashMap到 来获取它fnv::FnvHashMap。这将性能提升至 34 毫秒，即加速 2.2 倍。

如果这还不够，您可以尝试rustc-hashcrate 中的哈希值（与 几乎相同fxhash，但据说维护得更好），它使用与 Rust 编译器相同的函数，改编自 Firefox 使用的哈希值。它没有基于任何正式分析，在哈希函数测试套件上表现不佳，但据报道其表现始终优于 FNV。这在上面的示例中得到了证实，其中从 切换FnvHashMap到rustc_hash::FxHashMap会将时间缩短至 28 毫秒，即比初始计时加速 2.7 倍。

最后，如果您只想模仿 C# 和 Java 的做法，并且不太关心导致性能下降的插入数字的某些模式，那么您可以使用名称恰当的 crate，nohash_hasher它为您提供身份哈希。更改HashMap<i32, i32>为将HashMap<i32, i32, nohash_hasher::BuildNoHashHasher<i32>>时间缩短至略低于 4 毫秒，即比初始计时提高了 19 倍。

由于您报告 Java 示例比 Rust 快 9.5 倍，因此 19 倍的加速应该使您的代码速度大约是 Java 的两倍。

Answer 2

Rust默认情况下使用SipHashHashMap的实现作为哈希函数。SipHash 旨在基于预测哈希冲突来避免拒绝服务攻击，这是哈希映射中使用的哈希函数的重要安全属性。

如果不需要这种保证，可以使用更简单的哈希函数。一种选择是使用fxhashcrate，它应该可以将 a 中的整数读取速度加快HashMap<i32, i32>大约 3 倍。

其他选项是实现您自己的简单哈希函数（例如，通过简单地使用恒等函数，对于大多数连续键来说，这是一个不错的哈希函数），或者使用向量而不是哈希映射。

Int32.NET默认使用 的哈希值的身份函数，因此它不能抵抗哈希洪泛攻击。当然，这更快，但是的文档Dictionary中甚至没有提到其缺点。无论如何，我更喜欢 Rust 的“默认安全”方法，而不是 .NET 的任何一天，因为许多开发人员甚至没有意识到可预测的哈希函数可能导致的问题。如果不需要哈希洪泛保护，Rust 仍然允许您使用性能更高的哈希函数，因此对我个人而言，至少与 .NET 相比，这似乎是 Rust 的优势而不是劣势。