hashbrown

本库是 Google 高性能 SwissTable 哈希表的 Rust 版本，已适配作为 Rust 标准库中的 HashMap 和 HashSet 类型的直接替代品。

SwissTable 的原始 C++ 版本可在 此处 找到，此 CppCon 演讲 概述了该算法的工作原理。

自 Rust 1.36 以来，这现在是 Rust 标准库中的 HashMap 实现。然而，您可能仍然希望使用此库，因为它可以在没有 std 的环境中工作，例如嵌入式系统和内核。

变更日志

功能

• 标准库 HashMap 和 HashSet 类型的直接替代品。
• 使用 AHash 作为默认哈希器，比 SipHash 快得多。
• 比之前的标准库 HashMap 快约 2 倍。
• 内存使用更低：每个条目只有 1 字节的开销，而不是 8。
• 与 #[no_std] 兼容（但需要带有 alloc 库的全局分配器）。
• 空哈希表不分配任何内存。
• 使用 SIMD 进行查找以并行扫描多个哈希条目。

性能

与 Rust 1.35 之前 std::collections::HashMap 的先前实现相比。

使用哈希brown 默认的 AHash 哈希器（不是 HashDoS 防御性）

 name                       oldstdhash ns/iter  hashbrown ns/iter  diff ns/iter   diff %  speedup 
 insert_ahash_highbits        20,846              7,397                   -13,449  -64.52%   x 2.82 
 insert_ahash_random          20,515              7,796                   -12,719  -62.00%   x 2.63 
 insert_ahash_serial          21,668              7,264                   -14,404  -66.48%   x 2.98 
 insert_erase_ahash_highbits  29,570              17,498                  -12,072  -40.83%   x 1.69 
 insert_erase_ahash_random    39,569              17,474                  -22,095  -55.84%   x 2.26 
 insert_erase_ahash_serial    32,073              17,332                  -14,741  -45.96%   x 1.85 
 iter_ahash_highbits          1,572               2,087                       515   32.76%   x 0.75 
 iter_ahash_random            1,609               2,074                       465   28.90%   x 0.78 
 iter_ahash_serial            2,293               2,120                      -173   -7.54%   x 1.08 
 lookup_ahash_highbits        3,460               4,403                       943   27.25%   x 0.79 
 lookup_ahash_random          6,377               3,911                    -2,466  -38.67%   x 1.63 
 lookup_ahash_serial          3,629               3,586                       -43   -1.18%   x 1.01 
 lookup_fail_ahash_highbits   5,286               3,411                    -1,875  -35.47%   x 1.55 
 lookup_fail_ahash_random     12,365              4,171                    -8,194  -66.27%   x 2.96 
 lookup_fail_ahash_serial     4,902               3,240                    -1,662  -33.90%   x 1.51 

使用 libstd 默认的 SipHash 哈希器（HashDoS 防御性）

 name                       oldstdhash ns/iter  hashbrown ns/iter  diff ns/iter   diff %  speedup 
 insert_std_highbits        32,598              20,199                  -12,399  -38.04%   x 1.61 
 insert_std_random          29,824              20,760                   -9,064  -30.39%   x 1.44 
 insert_std_serial          33,151              17,256                  -15,895  -47.95%   x 1.92 
 insert_erase_std_highbits  74,731              48,735                  -25,996  -34.79%   x 1.53 
 insert_erase_std_random    73,828              47,649                  -26,179  -35.46%   x 1.55 
 insert_erase_std_serial    73,864              40,147                  -33,717  -45.65%   x 1.84 
 iter_std_highbits          1,518               2,264                       746   49.14%   x 0.67 
 iter_std_random            1,502               2,414                       912   60.72%   x 0.62 
 iter_std_serial            6,361               2,118                    -4,243  -66.70%   x 3.00 
 lookup_std_highbits        21,705              16,962                   -4,743  -21.85%   x 1.28 
 lookup_std_random          21,654              17,158                   -4,496  -20.76%   x 1.26 
 lookup_std_serial          18,726              14,509                   -4,217  -22.52%   x 1.29 
 lookup_fail_std_highbits   25,852              17,323                   -8,529  -32.99%   x 1.49 
 lookup_fail_std_random     25,913              17,760                   -8,153  -31.46%   x 1.46 
 lookup_fail_std_serial     22,648              14,839                   -7,809  -34.48%   x 1.53 

使用方法

将其添加到您的 Cargo.toml

[dependencies]
hashbrown = "0.6"

然后

use hashbrown::HashMap;

let mut map = HashMap::new();
map.insert(1, "one");

此库具有以下 Cargo 功能

• nightly：启用夜间功能：#[may_dangle]。
• serde：启用 serde 序列化支持。
• rayon：启用 rayon 并行迭代器支持。
• raw：启用对实验性和不安全的 RawTable API 的访问。

许可证

根据以下任一许可证授权

• Apache License, Version 2.0, (LICENSE-APACHE 或 http://www.apache.org/licenses/LICENSE-2.0)
• MIT 许可证 (LICENSE-MIT 或 http://opensource.org/licenses/MIT)

任选其一。

贡献

除非您明确说明，否则根据 Apache-2.0 许可证定义的，您有意提交以包含在作品中的任何贡献，将按照上述方式双授权，不附加任何额外条款或条件。