hashbrown 0.1.0

A faster replacement for HashMap

hashbrown

Build Status Crates.io

A high-performance hash table for Rust.

Documentation

Change log

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.

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:

[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_std support and ~10% speedup from branch hint intrinsics.

License

Licensed under either of

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.