commit | 1cd825fd13f8bd69ae9f16625ffd9194f214ea45 | [log] [tgz] |
---|---|---|
author | Xin Li <delphij@google.com> | Sat Feb 20 10:08:46 2021 +0000 |
committer | Automerger Merge Worker <android-build-automerger-merge-worker@system.gserviceaccount.com> | Sat Feb 20 10:08:46 2021 +0000 |
tree | 452c67e64530ff36e2e4c09951b7fcb01201f08a | |
parent | fea2da4735b4ae4e416d2862e3ebc8ebe353f4c5 [diff] | |
parent | 6276f158e3a63830aa1697dee6350b292d9c98b3 [diff] |
[automerger skipped] Mark ab/7061308 as merged in stage. am: 73b9b9a6c7 -s ours am: 6276f158e3 -s ours am skip reason: Change-Id I4e534925f90d6995c9873ef92e3f1f278bbc1505 with SHA-1 986801bc60 is in history Original change: undetermined MUST ONLY BE SUBMITTED BY AUTOMERGER Change-Id: I2a76ff480a2409230b4159ba8d4a4618913e6e72
This crate is a Rust port of Google‘s high-performance SwissTable hash map, adapted to make it a drop-in replacement for Rust’s standard HashMap
and HashSet
types.
The original C++ version of SwissTable can be found here, and this CppCon talk gives an overview of how the algorithm works.
Since Rust 1.36, this is now the HashMap
implementation for the Rust standard library. However you may still want to use this crate instead since it works in environments without std
, such as embedded systems and kernels.
HashMap
and HashSet
types.AHash
as the default hasher, which is much faster than SipHash.HashMap
.#[no_std]
(but requires a global allocator with the alloc
crate).Compared to the previous implementation of std::collections::HashMap
(Rust 1.35).
With the hashbrown default AHash hasher (not HashDoS-resistant):
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
With the libstd default SipHash hasher (HashDoS-resistant):
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
Add this to your Cargo.toml
:
[dependencies] hashbrown = "0.9"
Then:
use hashbrown::HashMap; let mut map = HashMap::new(); map.insert(1, "one");
This crate has the following Cargo features:
nightly
: Enables nightly-only features: #[may_dangle]
.serde
: Enables serde serialization support.rayon
: Enables rayon parallel iterator support.raw
: Enables access to the experimental and unsafe RawTable
API.inline-more
: Adds inline hints to most functions, improving run-time performance at the cost of compilation time. (enabled by default)ahash
: Compiles with ahash as default hasher. (enabled by default)ahash-compile-time-rng
: Activates the compile-time-rng
feature of ahash, to increase the DOS-resistance, but can result in issues for no_std
builds. More details in issue#124. (enabled by default)Licensed under either of:
at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.