GitHub - Amanieu/hashbrown: A faster HashMap for Rust
source link: https://github.com/Amanieu/hashbrown
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
README.md
hashbrown
A high-performance hash table for Rust.
Documentation
Change log
Features
- Drop-in replacement for the standard library
HashMap
andHashSet
types. - Around 2x faster than
FxHashMap
and 8x faster than the standardHashMap
. - Compatible with
#[no_std]
(currently requires nightly for thealloc
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
:
[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
- 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.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK