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.
- Drop-in replacement for the standard library
HashMapandHashSettypes. - Uses
FxHashas the default hasher, which is much faster than SipHash. - Around 2x faster than
FxHashMapand 8x faster than the standardHashMap. - Compatible with
#[no_std](currently requires nightly for thealloccrate). - Empty hash maps do not allocate any memory.
- SIMD lookups to scan multiple hash entries in parallel.
Compared to std::collections::HashMap:
name stdhash ns/iter hashbrown ns/iter diff ns/iter diff % speedup
find_existing 23,831 2,935 -20,896 -87.68% x 8.12
find_nonexisting 25,326 2,283 -23,043 -90.99% x 11.09
get_remove_insert 124 25 -99 -79.84% x 4.96
grow_by_insertion 197 177 -20 -10.15% x 1.11
hashmap_as_queue 72 18 -54 -75.00% x 4.00
new_drop 14 0 -14 -100.00% x inf
new_insert_drop 78 55 -23 -29.49% x 1.42
Compared to rustc_hash::FxHashMap (standard HashMap using FxHash instead of SipHash):
name fxhash ns/iter hashbrown ns/iter diff ns/iter diff % speedup
find_existing 5,951 2,935 -3,016 -50.68% x 2.03
find_nonexisting 4,637 2,283 -2,354 -50.77% x 2.03
get_remove_insert 29 25 -4 -13.79% x 1.16
grow_by_insertion 160 177 17 10.62% x 0.90
hashmap_as_queue 22 18 -4 -18.18% x 1.22
new_drop 9 0 -9 -100.00% x inf
new_insert_drop 64 55 -9 -14.06% x 1.16
Add this to your Cargo.toml:
[dependencies]
hashbrown = "0.1"and this to your crate root:
extern crate hashbrown;This crate has the following Cargo features:
nightly: Enables nightly-only features:no_stdsupport and ~10% speedup from branch hint intrinsics.
Licensed under either of
- Apache License, Version 2.0, (LICENSE-APACHE or https://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or https://opensource.org/licenses/MIT)
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.