hashbrown
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.
Change log
Features
- Drop-in replacement for the standard library
HashMap
andHashSet
types. - Uses
FxHash
as the default hasher, which is much faster than SipHash. - Around 2x faster than
FxHashMap
and 8x faster than the standardHashMap
. - Lower memory usage: only 1 byte of overhead per entry instead of 8.
- Compatible with
#[no_std]
(currently requires nightly for thealloc
crate). - Empty hash maps do not allocate any memory.
- SIMD lookups to scan multiple hash entries in parallel.
Performance
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
Usage
Add this to your Cargo.toml
:
[]
= "0.5"
Then:
use HashMap;
let mut map = new;
This crate has the following Cargo features:
nightly
: Enables nightly-only features:no_std
support and#[may_dangle]
.serde
: Enables serde serialization support.rayon
: Enables rayon parallel iterator support.
License
Licensed under either of:
- Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
Contribution
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.