vendor/hashbrown-0.9.1/README.md

   1 hashbrown
   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.36.0%2B-blue.svg?maxAge=3600)](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` as the default hasher, which is much faster than SipHash.
  30 - Around 2x faster than the previous standard library `HashMap`.
  31 - Lower memory usage: only 1 byte of overhead per entry instead of 8.
  32 - Compatible with `#[no_std]` (but requires a global allocator with the `alloc` crate).
  33 - Empty hash maps do not allocate any memory.
  34 - SIMD lookups to scan multiple hash entries in parallel.
  35
  36 ## Performance
  37
  38 Compared to the previous implementation of `std::collections::HashMap` (Rust 1.35).
  39
  40 With the hashbrown default AHash hasher (not HashDoS-resistant):
  41
  42 ```text
  43  name                       oldstdhash ns/iter  hashbrown ns/iter  diff ns/iter   diff %  speedup
  44  insert_ahash_highbits        20,846              7,397                   -13,449  -64.52%   x 2.82
  45  insert_ahash_random          20,515              7,796                   -12,719  -62.00%   x 2.63
  46  insert_ahash_serial          21,668              7,264                   -14,404  -66.48%   x 2.98
  47  insert_erase_ahash_highbits  29,570              17,498                  -12,072  -40.83%   x 1.69
  48  insert_erase_ahash_random    39,569              17,474                  -22,095  -55.84%   x 2.26
  49  insert_erase_ahash_serial    32,073              17,332                  -14,741  -45.96%   x 1.85
  50  iter_ahash_highbits          1,572               2,087                       515   32.76%   x 0.75
  51  iter_ahash_random            1,609               2,074                       465   28.90%   x 0.78
  52  iter_ahash_serial            2,293               2,120                      -173   -7.54%   x 1.08
  53  lookup_ahash_highbits        3,460               4,403                       943   27.25%   x 0.79
  54  lookup_ahash_random          6,377               3,911                    -2,466  -38.67%   x 1.63
  55  lookup_ahash_serial          3,629               3,586                       -43   -1.18%   x 1.01
  56  lookup_fail_ahash_highbits   5,286               3,411                    -1,875  -35.47%   x 1.55
  57  lookup_fail_ahash_random     12,365              4,171                    -8,194  -66.27%   x 2.96
  58  lookup_fail_ahash_serial     4,902               3,240                    -1,662  -33.90%   x 1.51
  59 ```
  60
  61 With the libstd default SipHash hasher (HashDoS-resistant):
  62
  63 ```text
  64  name                       oldstdhash ns/iter  hashbrown ns/iter  diff ns/iter   diff %  speedup
  65  insert_std_highbits        32,598              20,199                  -12,399  -38.04%   x 1.61
  66  insert_std_random          29,824              20,760                   -9,064  -30.39%   x 1.44
  67  insert_std_serial          33,151              17,256                  -15,895  -47.95%   x 1.92
  68  insert_erase_std_highbits  74,731              48,735                  -25,996  -34.79%   x 1.53
  69  insert_erase_std_random    73,828              47,649                  -26,179  -35.46%   x 1.55
  70  insert_erase_std_serial    73,864              40,147                  -33,717  -45.65%   x 1.84
  71  iter_std_highbits          1,518               2,264                       746   49.14%   x 0.67
  72  iter_std_random            1,502               2,414                       912   60.72%   x 0.62
  73  iter_std_serial            6,361               2,118                    -4,243  -66.70%   x 3.00
  74  lookup_std_highbits        21,705              16,962                   -4,743  -21.85%   x 1.28
  75  lookup_std_random          21,654              17,158                   -4,496  -20.76%   x 1.26
  76  lookup_std_serial          18,726              14,509                   -4,217  -22.52%   x 1.29
  77  lookup_fail_std_highbits   25,852              17,323                   -8,529  -32.99%   x 1.49
  78  lookup_fail_std_random     25,913              17,760                   -8,153  -31.46%   x 1.46
  79  lookup_fail_std_serial     22,648              14,839                   -7,809  -34.48%   x 1.53
  80 ```
  81
  82 ## Usage
  83
  84 Add this to your `Cargo.toml`:
  85
  86 ```toml
  87 [dependencies]
  88 hashbrown = "0.9"
  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
 100 This crate has the following Cargo features:
 101
 102 - `nightly`: Enables nightly-only features: `#[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 - `ahash`: Compiles with ahash as default hasher. (enabled by default)
 109 - `ahash-compile-time-rng`: Activates the `compile-time-rng` feature of ahash, to increase the
 110    DOS-resistance, but can result in issues for `no_std` builds. More details in
 111    [issue#124](https://github.com/rust-lang/hashbrown/issues/124). (enabled by default)
 112
 113 ## License
 114
 115 Licensed 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
 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.