1hashbrown 2========= 3 4[![Build Status](https://travis-ci.com/rust-lang/hashbrown.svg?branch=master)](https://travis-ci.com/rust-lang/hashbrown) 5[![Crates.io](https://img.shields.io/crates/v/hashbrown.svg)](https://crates.io/crates/hashbrown) 6[![Documentation](https://docs.rs/hashbrown/badge.svg)](https://docs.rs/hashbrown) 7[![Rust](https://img.shields.io/badge/rust-1.49.0%2B-blue.svg?maxAge=3600)](https://github.com/rust-lang/hashbrown) 8 9This crate is a Rust port of Google's high-performance [SwissTable] hash 10map, adapted to make it a drop-in replacement for Rust's standard `HashMap` 11and `HashSet` types. 12 13The original C++ version of SwissTable can be found [here], and this 14[CppCon talk] gives an overview of how the algorithm works. 15 16Since Rust 1.36, this is now the `HashMap` implementation for the Rust standard 17library. However you may still want to use this crate instead since it works 18in 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 39Compared to the previous implementation of `std::collections::HashMap` (Rust 1.35). 40 41With 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 62With 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 84Add this to your `Cargo.toml`: 85 86```toml 87[dependencies] 88hashbrown = "0.11" 89``` 90 91Then: 92 93```rust 94use hashbrown::HashMap; 95 96let mut map = HashMap::new(); 97map.insert(1, "one"); 98``` 99## Flags 100This 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 111this 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 115Licensed under either of: 116 117 * Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0) 118 * MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT) 119 120at your option. 121 122### Contribution 123 124Unless you explicitly state otherwise, any contribution intentionally submitted 125for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any 126additional terms or conditions. 127