Custom hashing: beating SipHash on integer keys

std::collections::HashMap is slower than it needs to be, on purpose, and the reason is worth knowing before you change it.

Its default hasher is SipHash-1-3, a keyed pseudo-random function seeded from the OS at process start. That is not a performance choice; it is a security choice. Without it, an attacker who can control your keys — URL paths, HTTP headers, JSON field names — can pick thousands of inputs that all land in one bucket, turning your O(1) lookups into O(n) and your web server into a stalled thread pool. That is a hash-flooding DoS, and it took down real services in 2011 before every major language patched it.

So SipHash is right for a map keyed by attacker-controlled strings. It is overkill for a map keyed by u64s you generated yourself, and swapping it out is the usual first optimisation on any hot HashMap<u64, _>.

In the wider ecosystem you would add rustc-hash or ahash and be done. There are no crates here, so you write it — which is better pedagogy anyway, because implementing Hasher and BuildHasher by hand is the only way to understand what the map is actually calling.

The two traits

Hasher is the state machine. It receives bytes (or, through the specialised methods, whole integers) and eventually produces a u64.

pub trait Hasher {
    fn finish(&self) -> u64;
    fn write(&mut self, bytes: &[u8]);
    // plus write_u8, write_u64, ... which DEFAULT to calling `write`
}

Only finish and write are required. E0046 tells you if you forget one.

BuildHasher is the factory. A HashMap needs a fresh hasher for every key, so it stores a builder, not a hasher.

pub trait BuildHasher {
    type Hasher: Hasher;
    fn build_hasher(&self) -> Self::Hasher;
}

What to write

pub const OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
pub const PRIME:  u64 = 0x0000_0100_0000_01b3;

pub struct FastHasher(pub u64);
pub struct FastBuild;

pub fn hash_of(v: u64) -> u64
pub fn count_pairs(keys: Vec<u64>) -> u64

FastHasher starts at OFFSET and is FNV-1a shaped:

• write(bytes) — for each byte in order: state = (state ^ byte) * PRIME, wrapping.
• write_u64(v) — state = (state ^ v) * PRIME, wrapping. Override this one. Its default implementation calls write(&v.to_ne_bytes()) — native endian — so a hasher that inherits it produces different values on a big-endian target. The tests pin exact hash values, so the override is not optional.
• finish() — state ^ (state >> 32).

FastBuild::build_hasher returns FastHasher(OFFSET).

hash_of(v) is one call to BuildHasher::hash_one. Write it that way rather than building a hasher, hashing and finishing by hand — clippy’s manual_hash_one exists to push you there.

count_pairs(keys) returns the number of unordered pairs of equal keys: for every distinct value appearing c times, c * (c - 1) / 2, summed. Use a HashMap<u64, u64, FastBuild> — HashMap::with_capacity_and_hasher takes both the capacity and the builder, and pre-sizing matters here for the same reason it did two items ago.

The largest test runs two million keys over half a million distinct values.

The trap that eats an afternoon

HashMap iteration order is unspecified AND randomised per process.

Not just “arbitrary but stable” — genuinely different between runs of the same binary, because the default hasher is seeded from the OS. Any test that depends on iteration order will pass on your machine and fail in CI, or pass a hundred times and fail on the hundred-and-first.

If you need a deterministic order: sort the output, or use BTreeMap. This problem sums the counts, and addition is commutative, so order does not matter — that is not luck, it is how the problem was designed to be testable.

Note also that swapping in your own BuildHasher makes iteration order deterministic (no random seed), which is convenient and is exactly the property an attacker would exploit. Do not do it for a map with untrusted keys.

Related lints

derived_hash_with_manual_eq — correctness, denied by default: deriving Hash while hand-writing PartialEq breaks the contract that a == b implies hash(a) == hash(b), which silently corrupts every HashMap and HashSet holding your type. mutable_key_type catches keys with interior mutability, which can change their own hash while they sit in a bucket. manual_hash_one and implicit_hasher (pedantic — your public functions should be generic over S: BuildHasher so callers can bring their own).

Remember the grade is compile + tests + clippy -D warnings.