hashbrown

A high-performance hash table for Rust.

Features

Drop-in replacement for the standard library HashMap and HashSet types.
Around 2x faster than FxHashMap and 8x faster than the standard HashMap.
Compatible with #[no_std] (currently requires nightly for the alloc crate).
Empty hash maps do not allocate any memory.
Uses SIMD to speed up lookups. The algorithm is based on Google's "Swiss Table" hash map.
- Explained in detail in this video.

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:

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:

toml [dependencies] hashbrown = "0.1"

and this to your crate root:

rust extern crate hashbrown;

This crate has the following Cargo features:

nightly: Enables nightly-only features: no_std support and ~10% speedup from branch hint intrinsics.

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.