third_party/rust/fnv/README.md
author Manish Goregaokar <manishearth@gmail.com>
Fri, 31 Mar 2017 06:01:06 -0500
changeset 398827 5f9e2952306a45343072c48a423cf5085098ec3d
parent 387544 d300c689f52e788542909647d3ab05719a46bb85
child 505692 d2c99742610827141e7c50a5da9692449fcbc6b3
permissions -rw-r--r--
servo: Merge #16201 - stylo: Handle text-emphasis-position pres attrs (from Manishearth:text-emph-pos); r=emilio Somehow slipped through the cracks. try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=e1d349e847b528be3d61ad2ebf374a791800cfbb Source-Repo: https://github.com/servo/servo Source-Revision: 955d3a8b8746b5060d421253263cf9bb05808866

# rust-fnv

An implementation of the [Fowler–Noll–Vo hash function][chongo].

### [Read the documentation](https://doc.servo.org/fnv/)


## About

The FNV hash function is a custom `Hasher` implementation that is more
efficient for smaller hash keys.

[The Rust FAQ states that][faq] while the default `Hasher` implementation,
SipHash, is good in many cases, it is notably slower than other algorithms
with short keys, such as when you have a map of integers to other values.
In cases like these, [FNV is demonstrably faster][graphs].

Its disadvantages are that it performs badly on larger inputs, and
provides no protection against collision attacks, where a malicious user
can craft specific keys designed to slow a hasher down. Thus, it is
important to profile your program to ensure that you are using small hash
keys, and be certain that your program could not be exposed to malicious
inputs (including being a networked server).

The Rust compiler itself uses FNV, as it is not worried about
denial-of-service attacks, and can assume that its inputs are going to be
small—a perfect use case for FNV.


## Usage

To include this crate in your program, add the following to your `Cargo.toml`:

```toml
[dependencies]
fnv = "1.0.3"
```


## Using FNV in a HashMap

The `FnvHashMap` type alias is the easiest way to use the standard library’s
`HashMap` with FNV.

```rust
use fnv::FnvHashMap;

let mut map = FnvHashMap::default();
map.insert(1, "one");
map.insert(2, "two");

map = FnvHashMap::with_capacity_and_hasher(10, Default::default());
map.insert(1, "one");
map.insert(2, "two");
```

Note, the standard library’s `HashMap::new` and `HashMap::with_capacity`
are only implemented for the `RandomState` hasher, so using `Default` to
get the hasher is the next best option.


## Using FNV in a HashSet

Similarly, `FnvHashSet` is a type alias for the standard library’s `HashSet`
with FNV.

```rust
use fnv::FnvHashSet;

let mut set = FnvHashSet::default();
set.insert(1);
set.insert(2);

set = FnvHashSet::with_capacity_and_hasher(10, Default::default());
set.insert(1);
set.insert(2);
```

[chongo]: http://www.isthe.com/chongo/tech/comp/fnv/index.html
[faq]: https://www.rust-lang.org/faq.html#why-are-rusts-hashmaps-slow
[graphs]: http://cglab.ca/~abeinges/blah/hash-rs/