Bug: 171338702

Clone this repo:
  1. 8f5a27a Migrate to cargo_embargo. am: 3e1c42f469 by Andrew Walbran · 4 months ago emu-34-2-dev emu-34-2-release main master
  2. 3e1c42f Migrate to cargo_embargo. by Andrew Walbran · 4 months ago
  3. dff4c19 Make fnv available to product and vendor am: 24b05cb4ad am: 1f4830fdbf am: 7bc4e2b7a1 am: c9ebf3f0d2 by Matthew Maurer · 12 months ago android14-qpr1-release android14-qpr1-s2-release android-14.0.0_r16 android-14.0.0_r17 android-14.0.0_r18 android-14.0.0_r19 android-14.0.0_r20 android-14.0.0_r21 android-14.0.0_r22 android-14.0.0_r23 android-14.0.0_r24 android-14.0.0_r25 android-14.0.0_r26 android-14.0.0_r27
  4. c9ebf3f Make fnv available to product and vendor am: 24b05cb4ad am: 1f4830fdbf am: 7bc4e2b7a1 by Matthew Maurer · 12 months ago android14-dev
  5. 7bc4e2b Make fnv available to product and vendor am: 24b05cb4ad am: 1f4830fdbf by Matthew Maurer · 12 months ago emu-33-dev emu-33-release

rust-fnv

An implementation of the Fowler–Noll–Vo hash function.

Read the documentation

About

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 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.

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:

[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.

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.

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);