An implementation of the Fowler–Noll–Vo hash function.
The FNV hash function is a custom
Hasher implementation that is more
efficient for smaller hash keys.
The Rust FAQ states that while the default
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.
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.
To include this crate in your program, add the following to your
[dependencies] fnv = "1.0.0"
Using FNV in a HashMap
To configure a
HashMap in the standard library to use the FNV hasher, you
must create a default instance of a
FnvHasher state, then create a new
map using this state with
HashMap::with_hash_state. A full example:
#![feature(hashmap_hasher)] use std::collections::HashMap; use std::collections::hash_state::DefaultState; use fnv::FnvHasher; let fnv = DefaultState::<FnvHasher>::default(); let mut map = HashMap::with_hash_state(fnv); map.insert(1, "one"); map.insert(2, "two");
Using FNV in a HashSet
The standard library’s
HashSet can be configured to use the FNV hasher
with the same mechanism.
#![feature(hashmap_hasher)] use std::collections::HashSet; use std::collections::hash_state::DefaultState; use fnv::FnvHasher; let fnv = DefaultState::<FnvHasher>::default(); let mut set = HashSet::with_hash_state(fnv); set.insert(1); set.insert(2);