HybridMap

HybridMap是一个Rust™混合映射实现，它使用内存堆栈上的向量来实现小型映射，而在其他情况下使用哈希映射。

与大多数混合技术一样，包括两个组件而不是一个组件是多余的。然而，混合解决方案可以针对特定用例提供一些价值。

对于小型映射，特别是那些存在于内存堆栈上且生命周期较短的映射，HybridMap可能略快一些，通常不超过16个条目，并且查找次数不多。

示例

HybridMap的使用方式与大多数其他映射类似。

use hybridmap::HybridMap;

let mut map = HybridMap::<i32, &str>::new();
map.insert(1, "one");
map.insert(2, "two");

assert_eq!(map.get(&1), Some(&"one"));
assert_eq!(map.len(), 2);

基准测试

基准测试可能无法代表您的用例。如果您创建了多个短暂的小型映射，您可能会看到以下显示的一些收益。您也可能比标准哈希映射的性能更差。

您可以将基准测试适应到您的用例中。如果您不确定是否应该使用这个混合映射还是哈希映射，您应该选择哈希映射。如数字所示，性能提升并不大。

Macbook Pro M1上的结果

在这个基准测试中，HybridMap在拥有超过16个条目时会内部切换到HashMap。这不是一个非常稳健的基准测试。正确基准测试HybridMap很难，并且需要比实现crate更多的努力。如许可证所述，自行承担风险。

然而，对于短暂的小型映射，性能提升可能更有趣

# Run the benchmarks
cargo bench --bench=hybridmap_bench -- --quick --quiet

# Run this command instead if you have more patience
cargo bench --bench=hybridmap_bench

# Open the results in a browser
open target/criterion/report/index.html
# or
xdg-open target/criterion/report/index.html

内存使用

HybridMap具有小的内存开销，向量与哈希映射之间的枚举变体以及堆栈上预分配的向量。

堆栈上的默认向量大小为 8 个条目。您可以通过将向量大小调整为预期存储在映射中的条目数量来节省一点内存。但大向量很快就会浪费资源。考虑保持在 20 以下。

对于包含非常少条目（一到两个）的映射，内存使用量可以比哈希表小一个数量级。否则，内存使用量与正常哈希表相似。

您可以将 benches/hybridmap_memory.rs 文件调整到您的用例中。

# Run the memory benchmark
# You will probably have to run it many times without things in the background
# to get a coherent result.
cargo bench --bench=hybridmap_memory

为什么？

我开始对小型映射进行基准测试，以检查我是否应该将 HashMap 切换为 BTreeMap 以适应我的用例。我还有一个原始的 Vec 实现，尽管对于小型映射来说更快。因此，我出于乐趣制作了这个包。

这个包可能带来的能源节约可能无法弥补我在实现这个包时为泡茶而烧水的能源消耗。但很有趣。

许可证

本项目采用 Apache License，版本 2.0 - 有关详细信息，请参阅 LICENSE 文件。

致谢

• 受到 robjtede/tinymap/ 的启发。
• 使用 smallvec。