hash
A fast, non-cryptographic hasher and a deterministic BuildHasher for it —
for HashMap/HashSet keys you control, not keys an attacker chooses.
What it does
FxHasher is the fold/multiply hash rustc itself uses for its own compiler
data structures: rotate, xor in the next word, multiply by a fixed constant,
eight bytes at a time. It is fast because it does very little per word, and
weak for the same reason. FixedHasher is a BuildHasher that hands out
FoldedFxHashers from the same fixed starting state every time, so the same
key hashes to the same value on every run and every platform (the state is
u64 on every target, including wasm32). fixed_hash_one hashes a single
value with it.
FoldedFxHasher is FxHasher plus one step at the end: a 64x64 to 128-bit
multiply with the two halves XORed together. Plain Fx ends in a
multiplication, so its low output bits depend only on the low bits of the
key, and a table that picks buckets from the low bits collides heavily on
keys that differ only higher up (i << 12, aligned addresses, an entity id
with its generation in the high half). The folded multiply lets every key
bit reach the low bits. The bare FxHasher is still there, unchanged and
bit-for-bit equal to rustc-hash 1.1.0, for consumers that spread the hash
themselves. Figures and the measurement behind the choice: the collections
page and docs/mid-platform.md, "hash.rs."
There is no RandomState equivalent, on purpose. A fold/multiply hash can't
be made DoS-resistant by randomizing its seed, so a randomized version would
only look safer than it is. Anything that hashes untrusted input should use
std's own RandomState.
Example usage
#![allow(unused)] fn main() { use std::collections::HashMap; use mid_platform::hash::{fixed_hash_one, FixedHasher}; // As the hasher of a HashMap keyed by data the engine generates itself. let mut cells: HashMap<(i32, i32), u32, FixedHasher> = HashMap::with_hasher(FixedHasher); cells.insert((3, -4), 7); assert_eq!(cells[&(3, -4)], 7); // Hashing one value directly. Same result every run. assert_eq!(fixed_hash_one("mid-engine"), fixed_hash_one("mid-engine")); }
Status
Done — Phase 3, hasher half. FxHasher matches the published rustc-hash
1.1.0 on 64-bit targets, apart from negative i8/i16/i32 values.
FixedHasher's folded-multiply finish is confirmed on CI: it fixes the
collisions, costs 2.7x on a raw u64 hashing loop and 1.7x in a map
insert-and-lookup loop (nothing measurable on strings), and is still 6.9x and
2.3x faster than SipHash on those two. Its output is a property of this
crate version, not a stable format. The maps that use it are on the
collections page. Callable from C: mid_platform_fixed_hash_{bytes,u64}. Full design write-up, including why this is a second copy of
mid-collections's hasher rather than a dependency on it:
docs/mid-platform.md, "hash.rs."