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

..--

.cargo_vcs_info.jsonD23-Nov-202374 65

.gitignoreD23-Nov-202318 32

.travis.ymlD23-Nov-2023179 98

Android.bpD23-Nov-20232 KiB7366

Cargo.tomlD23-Nov-2023886 3026

Cargo.toml.origD23-Nov-2023361 1815

LICENSED23-Nov-202310.6 KiB202169

LICENSE-APACHED23-Nov-202310.6 KiB202169

LICENSE-MITD23-Nov-20231 KiB2622

METADATAD23-Nov-2023344 1816

MODULE_LICENSE_APACHE2D23-Nov-20230

OWNERSD23-Nov-202340 21

README.mdD23-Nov-20232.2 KiB8255

TEST_MAPPINGD23-Nov-2023130 98

lib.rsD23-Nov-202318.7 KiB368301

README.md

1# rust-fnv
2
3An implementation of the [Fowler–Noll–Vo hash function][chongo].
4
5### [Read the documentation](https://doc.servo.org/fnv/)
6
7
8## About
9
10The FNV hash function is a custom `Hasher` implementation that is more
11efficient for smaller hash keys.
12
13[The Rust FAQ states that][faq] while the default `Hasher` implementation,
14SipHash, is good in many cases, it is notably slower than other algorithms
15with short keys, such as when you have a map of integers to other values.
16In cases like these, [FNV is demonstrably faster][graphs].
17
18Its disadvantages are that it performs badly on larger inputs, and
19provides no protection against collision attacks, where a malicious user
20can craft specific keys designed to slow a hasher down. Thus, it is
21important to profile your program to ensure that you are using small hash
22keys, and be certain that your program could not be exposed to malicious
23inputs (including being a networked server).
24
25The Rust compiler itself uses FNV, as it is not worried about
26denial-of-service attacks, and can assume that its inputs are going to be
27small—a perfect use case for FNV.
28
29
30## Usage
31
32To include this crate in your program, add the following to your `Cargo.toml`:
33
34```toml
35[dependencies]
36fnv = "1.0.3"
37```
38
39
40## Using FNV in a HashMap
41
42The `FnvHashMap` type alias is the easiest way to use the standard library’s
43`HashMap` with FNV.
44
45```rust
46use fnv::FnvHashMap;
47
48let mut map = FnvHashMap::default();
49map.insert(1, "one");
50map.insert(2, "two");
51
52map = FnvHashMap::with_capacity_and_hasher(10, Default::default());
53map.insert(1, "one");
54map.insert(2, "two");
55```
56
57Note, the standard library’s `HashMap::new` and `HashMap::with_capacity`
58are only implemented for the `RandomState` hasher, so using `Default` to
59get the hasher is the next best option.
60
61
62## Using FNV in a HashSet
63
64Similarly, `FnvHashSet` is a type alias for the standard library’s `HashSet`
65with FNV.
66
67```rust
68use fnv::FnvHashSet;
69
70let mut set = FnvHashSet::default();
71set.insert(1);
72set.insert(2);
73
74set = FnvHashSet::with_capacity_and_hasher(10, Default::default());
75set.insert(1);
76set.insert(2);
77```
78
79[chongo]: http://www.isthe.com/chongo/tech/comp/fnv/index.html
80[faq]: https://www.rust-lang.org/en-US/faq.html#why-are-rusts-hashmaps-slow
81[graphs]: https://cglab.ca/~abeinges/blah/hash-rs/
82