| 1 |
hashbrown |
| 2 |
========= |
| 3 |
|
| 4 |
[](https://github.com/rust-lang/hashbrown/actions) |
| 5 |
[](https://crates.io/crates/hashbrown) |
| 6 |
[](https://docs.rs/hashbrown) |
| 7 |
[](https://github.com/rust-lang/hashbrown) |
| 8 |
|
| 9 |
This crate is a Rust port of Google's high-performance [SwissTable] hash |
| 10 |
map, adapted to make it a drop-in replacement for Rust's standard `HashMap` |
| 11 |
and `HashSet` types. |
| 12 |
|
| 13 |
The original C++ version of SwissTable can be found [here], and this |
| 14 |
[CppCon talk] gives an overview of how the algorithm works. |
| 15 |
|
| 16 |
Since Rust 1.36, this is now the `HashMap` implementation for the Rust standard |
| 17 |
library. However you may still want to use this crate instead since it works |
| 18 |
in environments without `std`, such as embedded systems and kernels. |
| 19 |
|
| 20 |
[SwissTable]: https://abseil.io/blog/20180927-swisstables |
| 21 |
[here]: https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/raw_hash_set.h |
| 22 |
[CppCon talk]: https://www.youtube.com/watch?v=ncHmEUmJZf4 |
| 23 |
|
| 24 |
## [Change log](CHANGELOG.md) |
| 25 |
|
| 26 |
## Features |
| 27 |
|
| 28 |
- Drop-in replacement for the standard library `HashMap` and `HashSet` types. |
| 29 |
- Uses [AHash](https://github.com/tkaitchuck/aHash) as the default hasher, which is much faster than SipHash. |
| 30 |
However, AHash does *not provide the same level of HashDoS resistance* as SipHash, so if that is important to you, you might want to consider using a different hasher. |
| 31 |
- Around 2x faster than the previous standard library `HashMap`. |
| 32 |
- Lower memory usage: only 1 byte of overhead per entry instead of 8. |
| 33 |
- Compatible with `#[no_std]` (but requires a global allocator with the `alloc` crate). |
| 34 |
- Empty hash maps do not allocate any memory. |
| 35 |
- SIMD lookups to scan multiple hash entries in parallel. |
| 36 |
|
| 37 |
## Performance |
| 38 |
|
| 39 |
Compared to the previous implementation of `std::collections::HashMap` (Rust 1.35). |
| 40 |
|
| 41 |
With the hashbrown default AHash hasher: |
| 42 |
|
| 43 |
| name | oldstdhash ns/iter | hashbrown ns/iter | diff ns/iter | diff % | speedup | |
| 44 |
|:------------------------|:-------------------:|------------------:|:------------:|---------:|---------| |
| 45 |
| insert_ahash_highbits | 18,865 | 8,020 | -10,845 | -57.49% | x 2.35 | |
| 46 |
| insert_ahash_random | 19,711 | 8,019 | -11,692 | -59.32% | x 2.46 | |
| 47 |
| insert_ahash_serial | 19,365 | 6,463 | -12,902 | -66.63% | x 3.00 | |
| 48 |
| insert_erase_ahash_highbits | 51,136 | 17,916 | -33,220 | -64.96% | x 2.85 | |
| 49 |
| insert_erase_ahash_random | 51,157 | 17,688 | -33,469 | -65.42% | x 2.89 | |
| 50 |
| insert_erase_ahash_serial | 45,479 | 14,895 | -30,584 | -67.25% | x 3.05 | |
| 51 |
| iter_ahash_highbits | 1,399 | 1,092 | -307 | -21.94% | x 1.28 | |
| 52 |
| iter_ahash_random | 1,586 | 1,059 | -527 | -33.23% | x 1.50 | |
| 53 |
| iter_ahash_serial | 3,168 | 1,079 | -2,089 | -65.94% | x 2.94 | |
| 54 |
| lookup_ahash_highbits | 32,351 | 4,792 | -27,559 | -85.19% | x 6.75 | |
| 55 |
| lookup_ahash_random | 17,419 | 4,817 | -12,602 | -72.35% | x 3.62 | |
| 56 |
| lookup_ahash_serial | 15,254 | 3,606 | -11,648 | -76.36% | x 4.23 | |
| 57 |
| lookup_fail_ahash_highbits | 21,187 | 4,369 | -16,818 | -79.38% | x 4.85 | |
| 58 |
| lookup_fail_ahash_random | 21,550 | 4,395 | -17,155 | -79.61% | x 4.90 | |
| 59 |
| lookup_fail_ahash_serial | 19,450 | 3,176 | -16,274 | -83.67% | x 6.12 | |
| 60 |
|
| 61 |
|
| 62 |
With the libstd default SipHash hasher: |
| 63 |
|
| 64 |
|name | oldstdhash ns/iter | hashbrown ns/iter | diff ns/iter | diff % | speedup | |
| 65 |
|:------------------------|:-------------------:|------------------:|:------------:|---------:|---------| |
| 66 |
|insert_std_highbits |19,216 |16,885 | -2,331 | -12.13% | x 1.14 | |
| 67 |
|insert_std_random |19,179 |17,034 | -2,145 | -11.18% | x 1.13 | |
| 68 |
|insert_std_serial |19,462 |17,493 | -1,969 | -10.12% | x 1.11 | |
| 69 |
|insert_erase_std_highbits |50,825 |35,847 | -14,978 | -29.47% | x 1.42 | |
| 70 |
|insert_erase_std_random |51,448 |35,392 | -16,056 | -31.21% | x 1.45 | |
| 71 |
|insert_erase_std_serial |87,711 |38,091 | -49,620 | -56.57% | x 2.30 | |
| 72 |
|iter_std_highbits |1,378 |1,159 | -219 | -15.89% | x 1.19 | |
| 73 |
|iter_std_random |1,395 |1,132 | -263 | -18.85% | x 1.23 | |
| 74 |
|iter_std_serial |1,704 |1,105 | -599 | -35.15% | x 1.54 | |
| 75 |
|lookup_std_highbits |17,195 |13,642 | -3,553 | -20.66% | x 1.26 | |
| 76 |
|lookup_std_random |17,181 |13,773 | -3,408 | -19.84% | x 1.25 | |
| 77 |
|lookup_std_serial |15,483 |13,651 | -1,832 | -11.83% | x 1.13 | |
| 78 |
|lookup_fail_std_highbits |20,926 |13,474 | -7,452 | -35.61% | x 1.55 | |
| 79 |
|lookup_fail_std_random |21,766 |13,505 | -8,261 | -37.95% | x 1.61 | |
| 80 |
|lookup_fail_std_serial |19,336 |13,519 | -5,817 | -30.08% | x 1.43 | |
| 81 |
|
| 82 |
## Usage |
| 83 |
|
| 84 |
Add this to your `Cargo.toml`: |
| 85 |
|
| 86 |
```toml |
| 87 |
[dependencies] |
| 88 |
hashbrown = "0.12" |
| 89 |
``` |
| 90 |
|
| 91 |
Then: |
| 92 |
|
| 93 |
```rust |
| 94 |
use hashbrown::HashMap; |
| 95 |
|
| 96 |
let mut map = HashMap::new(); |
| 97 |
map.insert(1, "one"); |
| 98 |
``` |
| 99 |
## Flags |
| 100 |
This crate has the following Cargo features: |
| 101 |
|
| 102 |
- `nightly`: Enables nightly-only features including: `#[may_dangle]`. |
| 103 |
- `serde`: Enables serde serialization support. |
| 104 |
- `rayon`: Enables rayon parallel iterator support. |
| 105 |
- `raw`: Enables access to the experimental and unsafe `RawTable` API. |
| 106 |
- `inline-more`: Adds inline hints to most functions, improving run-time performance at the cost |
| 107 |
of compilation time. (enabled by default) |
| 108 |
- `bumpalo`: Provides a `BumpWrapper` type which allows `bumpalo` to be used for memory allocation. |
| 109 |
- `ahash`: Compiles with ahash as default hasher. (enabled by default) |
| 110 |
- `ahash-compile-time-rng`: Activates the `compile-time-rng` feature of ahash. For targets with no random number generator |
| 111 |
this pre-generates seeds at compile time and embeds them as constants. See [aHash's documentation](https://github.com/tkaitchuck/aHash#flags) (disabled by default) |
| 112 |
|
| 113 |
## License |
| 114 |
|
| 115 |
Licensed under either of: |
| 116 |
|
| 117 |
* Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or https://www.apache.org/licenses/LICENSE-2.0) |
| 118 |
* MIT license ([LICENSE-MIT](LICENSE-MIT) or https://opensource.org/licenses/MIT) |
| 119 |
|
| 120 |
at your option. |
| 121 |
|
| 122 |
### Contribution |
| 123 |
|
| 124 |
Unless you explicitly state otherwise, any contribution intentionally submitted |
| 125 |
for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any |
| 126 |
additional terms or conditions. |