tag | 3f7300fa69b305d89a89f1066a7550f75279ff2f | |
---|---|---|
tagger | The Android Open Source Project <initial-contribution@android.com> | Tue May 07 15:28:53 2024 -0700 |
object | ba193943c882307a52ded6a280732e1370c8eb50 |
Android VTS 14.0 Release 4 (11681991)
commit | ba193943c882307a52ded6a280732e1370c8eb50 | [log] [tgz] |
---|---|---|
author | Android Build Coastguard Worker <android-build-coastguard-worker@google.com> | Fri Mar 10 02:20:00 2023 +0000 |
committer | Android Build Coastguard Worker <android-build-coastguard-worker@google.com> | Fri Mar 10 02:20:00 2023 +0000 |
tree | d00e21722478b6ecfd989500bf6fae481049ab99 | |
parent | 9106aaebf141dba9250e01034c9a6bcd25831e45 [diff] | |
parent | c9ebf3f0d2f82ea611c99234c54c925fda034200 [diff] |
Snap for 9719949 from c9ebf3f0d2f82ea611c99234c54c925fda034200 to udc-release Change-Id: Iaa156c49d60600b22beaeb196060a20a6aa7fe2f
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 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.
To include this crate in your program, add the following to your Cargo.toml
:
[dependencies] fnv = "1.0.3"
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.
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);