🎓 A1Learner
🔍

Rust Hashing a Value Yourself

A hash fingerprint is one number that stands in for a whole value. The hashing machinery behind HashMap also works on its own, outside any map.

One value in, one number out

A helper does the three steps: build a hasher, feed the value, finish.

fn fingerprint<T: Hash>(state: &RandomState, value: &T) -> u64 {
    let mut hasher = state.build_hasher();
    value.hash(&mut hasher);
    hasher.finish()
}

Equal values, equal fingerprints

Hash the same word twice through one state. The numbers match.

let a = fingerprint(&state, &"ferris");
let b = fingerprint(&state, &"ferris");
println!("same = {}", a == b);

The shortcut hasher

DefaultHasher skips the shared state. Two fresh ones still agree inside one run.

let mut one = DefaultHasher::new();
"ferris".hash(&mut one);
let mut two = DefaultHasher::new();
"ferris".hash(&mut two);
println!("agree = {}", one.finish() == two.finish());

Write Hash by hand

A manual impl feeds the fields one by one. It must feed them in the same order every time.

impl Hash for ManualPoint {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.x.hash(state);
        self.y.hash(state);
    }
}

Order is part of the value

Swap the fields and the fingerprint changes. The stream of pieces is the value, as far as the hasher knows.

let a = fingerprint(&state, &Point { x: 3, y: 4 });
let b = fingerprint(&state, &Point { x: 4, y: 3 });
println!("differ = {}", a != b);

Example

use std::collections::hash_map::RandomState;
use std::hash::{BuildHasher, Hash, Hasher};

fn fingerprint<T: Hash>(state: &RandomState, value: &T) -> u64 {
    let mut hasher = state.build_hasher();
    value.hash(&mut hasher);
    hasher.finish()
}

#[derive(Hash)]
struct Point { x: i32, y: i32 }

struct ManualPoint { x: i32, y: i32 }

impl Hash for ManualPoint {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.x.hash(state);
        self.y.hash(state);
    }
}

fn main() {
    let state = RandomState::new();
    let first = fingerprint(&state, &"ferris");
    let second = fingerprint(&state, &"ferris");
    println!("same word, same print = {}", first == second);
    let other = fingerprint(&state, &"crab");
    println!("new word, new print = {}", first != other);
    let derived = fingerprint(&state, &Point { x: 3, y: 4 });
    let manual = fingerprint(&state, &ManualPoint { x: 3, y: 4 });
    println!("derive matches manual = {}", derived == manual);
}

Key points

  • Hash: the trait that feeds a value to a hasher, piece by piece
  • Hasher: the trait that stirs the pieces and ends the job with finish(), one u64
  • RandomState: the key source behind HashMap
  • One shared state makes fingerprints comparable inside a run
  • The keys are drawn fresh for every run of your programme
  • The same value earns a new number tomorrow
  • Use fingerprints for quick comparisons inside a run
  • Never save one and expect a later run to honour it

In this example, one RandomState serves every fingerprint, so the numbers can be compared. The word ferris hashes to the same number twice. The word crab earns a different one. Then a derived Hash and a hand-written Hash meet on the same point. Both feed x, then y, in the same order. Their fingerprints match exactly. The lesson hides the numbers on purpose: they change with every run, and only the comparisons are stable.

Note

Hash is built for speed, not for secrets

It is not encryption, and it must never guard a password

Try it Yourself

Edit the code, then press Run.

Running is simulated · Rust Playground

Exercise

You saved a fingerprint number in a file last week. Today the same key gives another number. What happened?