42个版本
| 0.14.5 | 2024年4月28日 |
|---|---|
| 0.14.4 |
|
| 0.14.3 | 2023年11月26日 |
| 0.14.0 | 2023年6月5日 |
| 0.1.6 | 2018年11月16日 |
#1 in 数据结构
21,239,858 个月下载量
用于 41,750 个crate（直接使用976个）
775KB
11K SLoC
hashbrown
此crate是Google的SwissTable哈希表的高性能Rust端口，经过修改后可作为Rust标准库中的HashMap和HashSet类型的直接替换。
SwissTable的原始C++版本可以在这里找到，而此CppCon演讲概述了算法的工作原理。
自Rust 1.36起，这现在是Rust标准库中的HashMap实现。然而，您可能仍然想使用此crate，因为它在无std的环境中也能工作，例如嵌入式系统和内核。
变更日志
功能
- 标准库中的
HashMap和HashSet类型的直接替换。 - 使用AHash作为默认的哈希器，比SipHash快得多。然而，AHash并不提供与SipHash相同的HashDoS抵抗级别，因此如果您认为这很重要，您可能需要考虑使用不同的哈希器。
- 比之前的标准库
HashMap快约2倍。 - 更低的内存使用：每个条目只有1个字节的开销，而不是8个。
- 与
#[no_std]兼容（但需要带有alloccrate的全局分配器）。 - 空的哈希表不分配任何内存。
- 使用SIMD并行扫描多个哈希条目。
性能
与Rust 1.35中std::collections::HashMap的先前实现进行比较。
使用hashbrown默认的AHash哈希器
| 名称 | oldstdhash ns/iter | hashbrown ns/iter | diff ns/iter | diff % | 加速 |
|---|---|---|---|---|---|
| insert_ahash_highbits | 18,865 | 8,020 | -10,845 | -57.49% | x 2.35 |
| 插入_ahash随机 | 19,711 | 8,019 | -11,692 | -59.32% | x 2.46 |
| 插入_ahash序列 | 19,365 | 6,463 | -12,902 | -66.63% | x 3.00 |
| 插入_删除_ahash高比特 | 51,136 | 17,916 | -33,220 | -64.96% | x 2.85 |
| 插入_删除_ahash随机 | 51,157 | 17,688 | -33,469 | -65.42% | x 2.89 |
| 插入_删除_ahash序列 | 45,479 | 14,895 | -30,584 | -67.25% | x 3.05 |
| 迭代_ahash高比特 | 1,399 | 1,092 | -307 | -21.94% | x 1.28 |
| 迭代_ahash随机 | 1,586 | 1,059 | -527 | -33.23% | x 1.50 |
| 迭代_ahash序列 | 3,168 | 1,079 | -2,089 | -65.94% | x 2.94 |
| 查找_ahash高比特 | 32,351 | 4,792 | -27,559 | -85.19% | x 6.75 |
| 查找_ahash随机 | 17,419 | 4,817 | -12,602 | -72.35% | x 3.62 |
| 查找_ahash序列 | 15,254 | 3,606 | -11,648 | -76.36% | x 4.23 |
| 查找失败_ahash高比特 | 21,187 | 4,369 | -16,818 | -79.38% | x 4.85 |
| 查找失败_ahash随机 | 21,550 | 4,395 | -17,155 | -79.61% | x 4.90 |
| 查找失败_ahash序列 | 19,450 | 3,176 | -16,274 | -83.67% | x 6.12 |
使用libstd默认的SipHash散列器
| 名称 | oldstdhash ns/iter | hashbrown ns/iter | diff ns/iter | diff % | 加速 |
|---|---|---|---|---|---|
| 插入_std高比特 | 19,216 | 16,885 | -2,331 | -12.13% | x 1.14 |
| 插入_std随机 | 19,179 | 17,034 | -2,145 | -11.18% | x 1.13 |
| 插入_std序列 | 19,462 | 17,493 | -1,969 | -10.12% | x 1.11 |
| 插入_删除_std高比特 | 50,825 | 35,847 | -14,978 | -29.47% | x 1.42 |
| 插入_删除_std随机 | 51,448 | 35,392 | -16,056 | -31.21% | x 1.45 |
| 插入_删除_std序列 | 87,711 | 38,091 | -49,620 | -56.57% | x 2.30 |
| 迭代_std高比特 | 1,378 | 1,159 | -219 | -15.89% | x 1.19 |
| 迭代_std随机 | 1,395 | 1,132 | -263 | -18.85% | x 1.23 |
| 迭代_std序列 | 1,704 | 1,105 | -599 | -35.15% | x 1.54 |
| 查找_std高比特 | 17,195 | 13,642 | -3,553 | -20.66% | x 1.26 |
| 查找_std随机 | 17,181 | 13,773 | -3,408 | -19.84% | x 1.25 |
| 查找_std序列 | 15,483 | 13,651 | -1,832 | -11.83% | x 1.13 |
| 查找失败_std高比特 | 20,926 | 13,474 | -7,452 | -35.61% | x 1.55 |
| 查找失败_std随机 | 21,766 | 13,505 | -8,261 | -37.95% | x 1.61 |
| 查找失败_std序列 | 19,336 | 13,519 | -5,817 | -30.08% | x 1.43 |
用法
将其添加到您的Cargo.toml
[dependencies]
hashbrown = "0.14"
然后
use hashbrown::HashMap;
let mut map = HashMap::new();
map.insert(1, "one");
标志
此crate具有以下Cargo功能
nightly：启用夜间仅有的功能，包括：#[may_dangle]。serde：启用serde序列化支持。rkyv：启用rkyv序列化支持。rayon：启用rayon并行迭代器支持。raw：启用对实验性和不安全的RawTableAPI的访问。inline-more：向大多数函数添加内联提示，以提高运行时性能，但会牺牲编译时间。（默认启用）ahash：使用ahash作为默认散列器进行编译。（默认启用）allocator-api2：启用对支持allocator-api2的分配器的支持。（默认启用）
许可
根据您的要求，许可如下
- Apache License，版本2.0，（LICENSE-APACHE或https://www.apache.org/licenses/LICENSE-2.0）
- MIT许可（LICENSE-MIT或https://opensource.org/licenses/MIT）
任选其一。
贡献
除非您明确声明，否则根据Apache-2.0许可定义的，您有意提交以包含在作品中的任何贡献，均应按上述方式双重许可，不附加任何额外条款或条件。
依赖关系
~0.9–2.3MB
~40K SLoC