vendor/hashbrown/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
   8 This crate is a Rust port of Google's high-performance [SwissTable] hash
   9 map, adapted to make it a drop-in replacement for Rust's standard `HashMap`
  10 and `HashSet` types.
  11
  12 The original C++ version of SwissTable can be found [here], and this
  13 [CppCon talk] gives an overview of how the algorithm works.
  14
  15 [SwissTable]: https://abseil.io/blog/20180927-swisstables
  16 [here]: https://github.com/abseil/abseil-cpp/blob/master/absl/container/internal/raw_hash_set.h
  17 [CppCon talk]: https://www.youtube.com/watch?v=ncHmEUmJZf4
  18
  19 ## [Change log](CHANGELOG.md)
  20
  21 ## Features
  22
  23 - Drop-in replacement for the standard library `HashMap` and `HashSet` types.
  24 - Uses `FxHash` as the default hasher, which is much faster than SipHash.
  25 - Around 2x faster than `FxHashMap` and 8x faster than the standard `HashMap`.
  26 - Lower memory usage: only 1 byte of overhead per entry instead of 8.
  27 - Compatible with `#[no_std]` (currently requires nightly for the `alloc` crate).
  28 - Empty hash maps do not allocate any memory.
  29 - SIMD lookups to scan multiple hash entries in parallel.
  30
  31 ## Performance
  32
  33 Compared to `std::collections::HashMap`:
  34
  35 ```
  36  name               stdhash ns/iter  hashbrown ns/iter  diff ns/iter    diff %  speedup
  37  find_existing      23,831           2,935                   -20,896   -87.68%   x 8.12
  38  find_nonexisting   25,326           2,283                   -23,043   -90.99%  x 11.09
  39  get_remove_insert  124              25                          -99   -79.84%   x 4.96
  40  grow_by_insertion  197              177                         -20   -10.15%   x 1.11
  41  hashmap_as_queue   72               18                          -54   -75.00%   x 4.00
  42  new_drop           14               0                           -14  -100.00%    x inf
  43  new_insert_drop    78               55                          -23   -29.49%   x 1.42
  44 ```
  45
  46 Compared to `rustc_hash::FxHashMap` (standard `HashMap` using `FxHash` instead of `SipHash`):
  47
  48 ```
  49  name               fxhash ns/iter  hashbrown ns/iter  diff ns/iter    diff %  speedup
  50  find_existing      5,951           2,935                    -3,016   -50.68%   x 2.03
  51  find_nonexisting   4,637           2,283                    -2,354   -50.77%   x 2.03
  52  get_remove_insert  29              25                           -4   -13.79%   x 1.16
  53  grow_by_insertion  160             177                          17    10.62%   x 0.90
  54  hashmap_as_queue   22              18                           -4   -18.18%   x 1.22
  55  new_drop           9               0                            -9  -100.00%    x inf
  56  new_insert_drop    64              55                           -9   -14.06%   x 1.16
  57 ```
  58
  59 ## Usage
  60
  61 Add this to your `Cargo.toml`:
  62
  63 ```toml
  64 [dependencies]
  65 hashbrown = "0.5"
  66 ```
  67
  68 Then:
  69
  70 ```rs
  71 use hashbrown::HashMap;
  72 let mut map = HashMap::new();
  73 ```
  74
  75 This crate has the following Cargo features:
  76
  77 - `nightly`: Enables nightly-only features: `no_std` support and `#[may_dangle]`.
  78 - `serde`: Enables serde serialization support.
  79 - `rayon`: Enables rayon parallel iterator support.
  80
  81 ## License
  82
  83 Licensed under either of:
  84
  85  * Apache License, Version 2.0, ([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
  86  * MIT license ([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT)
  87
  88 at your option.
  89
  90 ### Contribution
  91
  92 Unless you explicitly state otherwise, any contribution intentionally submitted
  93 for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any
  94 additional terms or conditions.