• Home
  • History
  • Annotate
Name Date Size #Lines LOC

..03-May-2022-

benches/H03-May-2022-332280

src/H03-May-2022-12,7567,640

tests/H03-May-2022-697534

.cargo-checksum.jsonH A D03-May-202289 11

.cargo_vcs_info.jsonH A D01-Jan-197074 65

.gitignoreH A D01-Jan-197030 43

CHANGELOG.mdH A D01-Jan-197011.2 KiB343245

Cargo.tomlH A D01-Jan-19702.1 KiB8571

Cargo.toml.orig-cargoH A D01-Jan-19701.7 KiB6050

LICENSE-APACHEH A D01-Jan-197010.6 KiB202169

LICENSE-MITH A D01-Jan-19701 KiB2622

README.mdH A D01-Jan-19707.1 KiB12798

clippy.tomlH A D01-Jan-197068 21

README.md

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