Fast hash functions

Deep dive

How it works

In: a key (integer or bytes) and an optional seed · Out: a 64-bit hash with well-mixed high and low bits · State: none (the seed is a parameter) · Cost: O(bytes); order of 1-5 ns for keys up to 16 bytes, tens of GB/s on long inputs

1. Integer keys: a finalizer (bijective mix) suffices: xor-shift, multiply by an odd constant, repeat. Murmur3 fmix64 and splitmix64 avalanche all bits in 2 multiplies.
2. Short strings: read the first and last 8 (or 4) bytes with possibly overlapping unaligned loads, so any length 4-16 costs 2 loads and no loop. Mix length in to separate "ab" from "ab\0".
3. Long strings: process 16-64 B per step on independent accumulators (ILP), then fold them; XXH3 uses SIMD multiply-accumulate across 8 lanes.
4. Seeding: xor a random seed into the initial state. This defeats precomputed collision sets for non-cryptographic hashes in practice but is not a proof; SipHash is a real keyed PRF.
5. Reducing to a table size: power-of-two mask on the good bits (multiplicative hashes have strong high bits), or Lemire's ((h as u128 * n as u128) >> 64) for arbitrary n without division.

Code

use std::collections::HashMap;
use std::hash::{BuildHasherDefault, Hasher};

/// Murmur3 fmix64: bijective, full avalanche. Good integer hash / finalizer.
pub fn fmix64(mut x: u64) -> u64 {
    x ^= x >> 33; x = x.wrapping_mul(0xFF51_AFD7_ED55_8CCD);
    x ^= x >> 33; x = x.wrapping_mul(0xC4CE_B9FE_1A85_EC53);
    x ^ (x >> 33)
}

/// 64x64 -> 128 multiply, fold halves. Note: if either operand is 0, output is 0, so inputs are xored with constants.
#[inline] fn fold(a: u64, b: u64) -> u64 { let r = a as u128 * b as u128; r as u64 ^ (r >> 64) as u64 }
#[inline] fn r64(d: &[u8]) -> u64 { u64::from_le_bytes(d[..8].try_into().unwrap()) }
#[inline] fn r32(d: &[u8]) -> u64 { u32::from_le_bytes(d[..4].try_into().unwrap()) as u64 }

const P0: u64 = 0xA076_1D64_78BD_642F;
const P1: u64 = 0xE703_7ED1_A0B4_28DB;

/// Folded-multiply byte hash in the style of wyhash/rapidhash (illustrative: run SMHasher before trusting it).
pub fn hash_bytes(d: &[u8], seed: u64) -> u64 {
    let n = d.len();
    let mut s = seed ^ P0;
    let (a, b) = if n <= 16 {
        if n >= 8 { (r64(d), r64(&d[n - 8..])) } // overlapping loads: no byte loop
        else if n >= 4 { (r32(d), r32(&d[n - 4..])) }
        else if n > 0 { (((d[0] as u64) << 16) | ((d[n / 2] as u64) << 8) | d[n - 1] as u64, 0) }
        else { (0, 0) }
    } else {
        let mut i = 0;
        while i + 16 < n { // single lane; production code runs 3-4 lanes for ILP
            s = fold(r64(&d[i..]) ^ P1, r64(&d[i + 8..]) ^ s);
            i += 16;
        }
        (r64(&d[n - 16..]), r64(&d[n - 8..])) // last 16 bytes, may overlap the loop
    };
    fold(P1 ^ n as u64, fold(a ^ P1, b ^ s))
}

/// FxHash (rustc-hash 1.x): one rotate, xor, multiply per word. Very fast, weak low bits, no seed.
#[derive(Default)]
pub struct FxHasher(u64);
impl Hasher for FxHasher {
    fn write(&mut self, bytes: &[u8]) {
        for c in bytes.chunks(8) {
            let mut w = [0u8; 8];
            w[..c.len()].copy_from_slice(c);
            self.write_u64(u64::from_le_bytes(w));
        }
    }
    fn write_u64(&mut self, w: u64) { self.0 = (self.0.rotate_left(5) ^ w).wrapping_mul(0x517C_C1B7_2722_0A95); }
    fn finish(&self) -> u64 { self.0 }
}
pub type FxHashMap<K, V> = HashMap<K, V, BuildHasherDefault<FxHasher>>;

/// Map a hash to [0, n) without division (Lemire).
pub fn reduce(h: u64, n: u64) -> u64 { ((h as u128 * n as u128) >> 64) as u64 }

Complexity and constants

• 64-bit multiply: 3-4 cycles latency, 1/cycle throughput on x86-64 and Apple/ARM big cores; mulx/umulh give the high half.
• fmix64: dependency chain of 2 multiplies + 3 xor-shifts, order of 10 cycles latency; throughput higher when hashing independent keys.
• Short-key hashing is latency-bound and often dominates hash-table lookup time for string keys; long-key hashing is bandwidth-bound.
• SipHash-1-3 (Rust's default HashMap hasher) costs order of 3-10× a fast hash on short keys.

Efficiency

• Cost: keys up to 16 bytes take order of 1-5 ns (two overlapping loads and a few 64-bit multiplies at 3-4 cycles latency); SipHash-1-3 takes order of 10-20 ns. Long inputs: XXH3 reaches tens of GB/s (order of), SipHash order of 1-2 GB/s. Bound: multiply latency for short keys, memory bandwidth for long ones.
• Levers:
  • folded 128-bit multiply — mixes 64 input bits in about 4 cycles (wyhash family, foldhash) — trusted keys
  • overlapping loads for 4-16 byte keys — no byte loop, 2 loads for any length (as above) — short strings
  • several independent lanes — hides multiply latency (XXH3 uses SIMD lanes) — inputs over 16 bytes
  • hash once, derive k indexes by double hashing — 1 hash instead of k — Bloom filters, sketches (Bloom filter)
  • hardware CRC32C or AES rounds — about 1 cycle per 8 bytes (CRC32C), one AES round per 128 bits (aHash) — checksums, trusted hash tables
• Naive → standard → state of the art:
  • byte-at-a-time hash (FNV) · about 1 byte per cycle (order of)
  • SipHash-1-3 · order of 10-20 ns on short keys, safe against HashDoS
  • foldhash, rapidhash, XXH3 · order of 1-5 ns on short keys, tens of GB/s on long ones

Implementation notes

• aHash uses AES-NI rounds (aesenc) when available; one AES round mixes 128 bits in about 4 cycles.
• Seed per table or per process from the OS RNG; keep it out of logs and error messages.
• For HashMap<u64, _> with sequential keys, identity hashing looks fast in microbenchmarks and collapses in Swiss tables, which need good top and bottom bits.

Pitfalls

• Hashing structs field by field through Hasher::write with tiny calls: per-call overhead can exceed the mixing cost. Implement Hash to write one packed u64/u128 when possible.
• Fx/multiplicative hashes have weak low bits; masking with & (n-1) on a table that indexes by low bits can cluster. Use the high bits or add a finalizer.
• Assuming XXH64 values equal XXH3 values, or that a crate's output is stable across major versions.
• Folded multiply "blinding": if input ^ constant == 0 the product is 0 and earlier state is lost. Real designs keep the risk at 2^-64 per block and accept it for non-adversarial use.
• hash % n with power-of-two n keeps only the low bits; with a weak hash that is a collision factory.

Variants and alternatives

In production

• Languages and runtimes: Rust std (SipHash-1-3), hashbrown (foldhash), rustc (FxHash), Go runtime (AES-based hash on amd64/arm64).
• Databases and storage: Cassandra (Murmur3 partitioner), RocksDB (xxHash for checksums), Abseil absl::Hash (wyhash family).
• Compression and data formats: xxHash in zstd and LZ4 frame checksums.
• Networking: SipHash was designed for hash-table keys from the network (HashDoS; Crosby and Wallach 2003).

Implementations

Sources

• Jean-Philippe Aumasson, Daniel J. Bernstein, SipHash: a fast short-input PRF, INDOCRYPT 2012. paper · pdf
• Scott A. Crosby, Dan S. Wallach, Denial of Service via Algorithmic Complexity Attacks, USENIX Security 2003. pdf
• Yann Collet, xxHash specification and benchmarks. spec · code
• Daniel Lemire, Fast Random Integer Generation in an Interval, ACM TOMACS, 2019. paper · arXiv
• Austin Appleby, SMHasher test suite (and Reini Urban's extended SMHasher). code
• Wang Yi, wyhash. code