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