🎓 A1Learner
🔍

Rust Write Your Own Hasher

A hasher turns pieces into one number. Nothing stops you from building the stirrer yourself.

Start from a fixed number

FNV-1a begins every hash at the same offset value. Empty input keeps it, untouched.

struct Fnv(u64);

impl Default for Fnv {
    fn default() -> Self { Fnv(0xcbf2_9ce4_8422_2325) }
}

Stir one byte at a time

Each byte flips bits with xor. Then a multiply spreads the change through the whole number.

fn write(&mut self, bytes: &[u8]) {
    for &byte in bytes {
        self.0 ^= byte as u64;
        self.0 = self.0.wrapping_mul(0x0000_0100_0000_01b3);
    }
}

Empty input, known answer

Feed nothing and finish returns the start value. Test suites check this case first.

println!("empty = {:016x}", fnv_of(b""));

Two more known answers

The FNV test vectors are public. A correct stirrer must land on them.

println!("a = {:016x}", fnv_of(b"a"));
println!("foobar = {:016x}", fnv_of(b"foobar"));

Plug it into a map

BuildHasherDefault wraps any hasher that has a Default. The map keeps its std shape.

let mut counts: HashMap<String, u32, BuildHasherDefault<Fnv>> = HashMap::default();

Example

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

#[derive(Clone)]
struct Fnv(u64);

impl Default for Fnv {
    fn default() -> Self {
        Fnv(0xcbf2_9ce4_8422_2325)
    }
}

impl Hasher for Fnv {
    fn write(&mut self, bytes: &[u8]) {
        for &byte in bytes {
            self.0 ^= byte as u64;
            self.0 = self.0.wrapping_mul(0x0000_0100_0000_01b3);
        }
    }

    fn finish(&self) -> u64 {
        self.0
    }
}

fn fnv_of(bytes: &[u8]) -> u64 {
    let mut hasher = Fnv::default();
    hasher.write(bytes);
    hasher.finish()
}

fn main() {
    println!("empty = {:016x}", fnv_of(b""));
    println!("a = {:016x}", fnv_of(b"a"));
    println!("foobar = {:016x}", fnv_of(b"foobar"));
    let mut counts: HashMap<String, u32, BuildHasherDefault<Fnv>> = HashMap::default();
    for word in ["oak", "elm", "oak", "ash", "elm", "oak"] {
        *counts.entry(word.to_string()).or_insert(0) += 1;
    }
    println!("oak = {:?}", counts.get("oak"));
    println!("kinds = {}", counts.len());
}

Key points

  • FNV-1a: a tiny hash design by Fowler, Noll and Vo
  • The a means xor first, then multiply
  • wrapping_mul: a multiply that wraps past the top instead of panicking
  • Hashers want the wrap
  • A hasher with a Default can serve a HashMap through BuildHasherDefault
  • No map surgery is needed
  • Test a hasher against known answers
  • Public vectors catch a wrong prime or a swapped step at once
  • This stirrer suits fast lookups over keys you control
  • It has no attack resistance at all
  • A hasher stirs the pieces it is fed and finishes with one number

In this example, the Fnv struct holds one u64. It starts at the offset value. write stirs each byte in with xor and a wrapping multiply by the FNV prime. finish simply reads the number back. The first three prints check the stirrer against the public FNV-1a vectors, and all three land. Then the same hasher drives a real HashMap through BuildHasherDefault. The word oak was counted three times, and the map holds three kinds of word.

Note

Never invent a hash for security work

A home-made hasher can be collided and flooded on purpose

Secrets belong to vetted designs

Try it Yourself

Edit the code, then press Run.

Running is simulated · Rust Playground

Exercise

Why does the lesson check the hasher against published vectors?