README.md
1hashbrown
2=========
3
4[](https://travis-ci.com/rust-lang/hashbrown)
5[](https://crates.io/crates/hashbrown)
6[](https://docs.rs/hashbrown)
7
8This crate is a Rust port of Google's high-performance [SwissTable] hash
9map, adapted to make it a drop-in replacement for Rust's standard `HashMap`
10and `HashSet` types.
11
12The original C++ version of SwissTable can be found [here], and this
13[CppCon talk] gives an overview of how the algorithm works.
14
15Since Rust 1.36, this is now the `HashMap` implementation for the Rust standard
16library. However you may still want to use this crate instead since it works
17in environments without `std`, such as embedded systems and kernels.
18
19[SwissTable]: https://abseil.io/blog/20180927-swisstables
20[here]: https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/raw_hash_set.h
21[CppCon talk]: https://www.youtube.com/watch?v=ncHmEUmJZf4
22
23## [Change log](CHANGELOG.md)
24
25## Features
26
27- Drop-in replacement for the standard library `HashMap` and `HashSet` types.
28- Uses `AHash` as the default hasher, which is much faster than SipHash.
29- Around 2x faster than the previous standard library `HashMap`.
30- Lower memory usage: only 1 byte of overhead per entry instead of 8.
31- Compatible with `#[no_std]` (but requires a global allocator with the `alloc` crate).
32- Empty hash maps do not allocate any memory.
33- SIMD lookups to scan multiple hash entries in parallel.
34
35## Performance
36
37Compared to the previous implementation of `std::collections::HashMap` (Rust 1.35).
38
39With the hashbrown default AHash hasher (not HashDoS-resistant):
40
41```text
42 name oldstdhash ns/iter hashbrown ns/iter diff ns/iter diff % speedup
43 insert_ahash_highbits 20,846 7,397 -13,449 -64.52% x 2.82
44 insert_ahash_random 20,515 7,796 -12,719 -62.00% x 2.63
45 insert_ahash_serial 21,668 7,264 -14,404 -66.48% x 2.98
46 insert_erase_ahash_highbits 29,570 17,498 -12,072 -40.83% x 1.69
47 insert_erase_ahash_random 39,569 17,474 -22,095 -55.84% x 2.26
48 insert_erase_ahash_serial 32,073 17,332 -14,741 -45.96% x 1.85
49 iter_ahash_highbits 1,572 2,087 515 32.76% x 0.75
50 iter_ahash_random 1,609 2,074 465 28.90% x 0.78
51 iter_ahash_serial 2,293 2,120 -173 -7.54% x 1.08
52 lookup_ahash_highbits 3,460 4,403 943 27.25% x 0.79
53 lookup_ahash_random 6,377 3,911 -2,466 -38.67% x 1.63
54 lookup_ahash_serial 3,629 3,586 -43 -1.18% x 1.01
55 lookup_fail_ahash_highbits 5,286 3,411 -1,875 -35.47% x 1.55
56 lookup_fail_ahash_random 12,365 4,171 -8,194 -66.27% x 2.96
57 lookup_fail_ahash_serial 4,902 3,240 -1,662 -33.90% x 1.51
58```
59
60With the libstd default SipHash hasher (HashDoS-resistant):
61
62```text
63 name oldstdhash ns/iter hashbrown ns/iter diff ns/iter diff % speedup
64 insert_std_highbits 32,598 20,199 -12,399 -38.04% x 1.61
65 insert_std_random 29,824 20,760 -9,064 -30.39% x 1.44
66 insert_std_serial 33,151 17,256 -15,895 -47.95% x 1.92
67 insert_erase_std_highbits 74,731 48,735 -25,996 -34.79% x 1.53
68 insert_erase_std_random 73,828 47,649 -26,179 -35.46% x 1.55
69 insert_erase_std_serial 73,864 40,147 -33,717 -45.65% x 1.84
70 iter_std_highbits 1,518 2,264 746 49.14% x 0.67
71 iter_std_random 1,502 2,414 912 60.72% x 0.62
72 iter_std_serial 6,361 2,118 -4,243 -66.70% x 3.00
73 lookup_std_highbits 21,705 16,962 -4,743 -21.85% x 1.28
74 lookup_std_random 21,654 17,158 -4,496 -20.76% x 1.26
75 lookup_std_serial 18,726 14,509 -4,217 -22.52% x 1.29
76 lookup_fail_std_highbits 25,852 17,323 -8,529 -32.99% x 1.49
77 lookup_fail_std_random 25,913 17,760 -8,153 -31.46% x 1.46
78 lookup_fail_std_serial 22,648 14,839 -7,809 -34.48% x 1.53
79```
80
81## Usage
82
83Add this to your `Cargo.toml`:
84
85```toml
86[dependencies]
87hashbrown = "0.8"
88```
89
90Then:
91
92```rust
93use hashbrown::HashMap;
94
95let mut map = HashMap::new();
96map.insert(1, "one");
97```
98
99This crate has the following Cargo features:
100
101- `nightly`: Enables nightly-only features: `#[may_dangle]`.
102- `serde`: Enables serde serialization support.
103- `rayon`: Enables rayon parallel iterator support.
104- `raw`: Enables access to the experimental and unsafe `RawTable` API.
105- `inline-more`: Adds inline hints to most functions, improving run-time performance at the cost
106 of compilation time. (enabled by default)
107- `ahash`: Compiles with ahash as default hasher. (enabled by default)
108- `ahash-compile-time-rng`: Activates the `compile-time-rng` feature of ahash, to increase the
109 DOS-resistance, but can result in issues for `no_std` builds. More details in
110 [issue#124](https://github.com/rust-lang/hashbrown/issues/124). (enabled by default)
111
112## License
113
114Licensed under either of:
115
116 * Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
117 * MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT)
118
119at your option.
120
121### Contribution
122
123Unless you explicitly state otherwise, any contribution intentionally submitted
124for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any
125additional terms or conditions.
126
){kind=link}
){kind=link}
){kind=link}