Custom Hashers

HashMap<K, V, S> and HashSet<T, S> are parameterized over a third type parameter S: BuildHasher (which defaults to std::collections::hash_map::RandomState), allowing you to swap out the default SipHash-1-3 algorithm for a custom, deterministic, or high-speed non-cryptographic hasher.

The Hasher and BuildHasher Traits

pub trait Hasher {
    fn finish(&self) -> u64;
    fn write(&mut self, bytes: &[u8]);
    // Plus specialized write_u8, write_u32, write_u64, write_usize, ...
}

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

• Hasher computes the u64 hash for a single key lookup or insertion.
• BuildHasher is stored inside the HashMap and constructs a fresh Self::Hasher each time the map hashes a key. For stateless hashers that implement Default, std::hash::BuildHasherDefault<H> automatically implements BuildHasher with 0 bytes of storage overhead (size_of::<BuildHasherDefault<H>>() == 0).

Implementing a Custom Fast FnvHasher with BuildHasherDefault

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

pub struct Fnv1aHasher(u64);

impl Default for Fnv1aHasher {
    fn default() -> Self {
        Self(0xcbf29ce484222325) // FNV-1a 64-bit offset basis
    }
}

impl Hasher for Fnv1aHasher {
    fn write(&mut self, bytes: &[u8]) {
        for &b in bytes {
            self.0 ^= u64::from(b);
            self.0 = self.0.wrapping_mul(0x100000001b3); // FNV prime
        }
    }

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

// Zero-sized BuildHasher wrapper and convenient type alias:
type FnvBuildHasher = BuildHasherDefault<Fnv1aHasher>;
type FnvHashMap<K, V> = HashMap<K, V, FnvBuildHasher>;

fn main() {
    let mut map: FnvHashMap<&str, u32> = FnvHashMap::default();
    map.insert("id_1", 100);
    map.insert("id_2", 200);

    println!("FnvHashMap lookup 'id_1': {:?}", map.get("id_1"));
    println!(
        "Size of FnvHashMap<&str, u32>: {} bytes (vs 48 bytes with RandomState)",
        std::mem::size_of::<FnvHashMap<&str, u32>>()
    );
}

FnvHashMap lookup 'id_1': Some(100)
Size of FnvHashMap<&str, u32>: 32 bytes (vs 48 bytes with RandomState)

Notice that because BuildHasherDefault<Fnv1aHasher> is a zero-sized type (saving the 16-byte random key stored in RandomState), the stack size of FnvHashMap drops from 48 bytes to 32 bytes.

Common Hashers in the Rust Ecosystem