rustc-hashCrate

Overview

rustc-hash is the hasher the Rust compiler uses on itself, published so other programs can use it too. It is not cryptographic and does not pretend to be; for a digest that resists forgery you want sha2 and the digest traits.

Using it is an import and a default():

use rustc_hash::{FxHashMap, FxHashSet};

let mut counts: FxHashMap<u32, u32> = FxHashMap::default();
*counts.entry(7).or_insert(0) += 1;

let mut seen: FxHashSet<&str> = FxHashSet::default();
seen.insert("a");
seen.insert("a");

assert_eq!(counts[&7], 1);
assert_eq!(seen.len(), 1);

Those are type aliases for std::collections::HashMap and HashSet with the hasher substituted, so everything else about them is unchanged. Note default() rather than new(): new is only defined for the standard RandomState, and unlike foldhash this crate ships no extension trait to restore it.

The defining property is that there is no randomness at all. FxBuildHasher is a unit struct — zero bytes — with a fixed algorithm and a fixed seed. Two consequences, and which one is a feature depends entirely on your situation:

use rustc_hash::FxHashMap;

// Build the same map twice, in two separate maps.
let build = || {
    let mut map: FxHashMap<u32, u32> = FxHashMap::default();
    for i in 0..8 {
        map.insert(i, i * i);
    }
    map.keys().copied().collect::<Vec<_>>()
};

// Identical iteration order — and identical on the next run of the program.
assert_eq!(build(), build());

The feature is reproducibility: a compiler that wants byte-identical output from identical input cannot have its data structures iterating in a different order each run, and that is precisely why rustc uses this. The hazard is that it is trivially vulnerable to collision attacks — an attacker who knows the algorithm, and it is public, can generate keys that all land in one bucket and turn a map into a linked list. So: fine for compiler-internal data, keys you generated, anything where the inputs are yours. Never for keys that came off the network.

Do not store the hash values. The Fx name is kept for compatibility but the algorithm behind it is not the Firefox one any more — 2.0 replaced it with a polynomial hash designed by Orson Peters, and 2.1.1 changed it again to fix a regression on large maps in rustc. Two changes within one major version is the clearest possible statement that the output is not a stable value.

Against the alternatives. Compared to std's SipHash-1-3 this is much faster on short keys and gives up the DoS resistance that motivated SipHash. Compared to foldhash — which is, interestingly, the same author's later design and what hashbrown now defaults to — rustc-hash is deterministic where foldhash randomises, and foldhash is the better-distributed of the two. Pick rustc-hash when you want reproducibility or are matching the compiler's behaviour; pick foldhash when you want a fast hash map and have no opinion beyond that.

The dependency is minimal: nothing required, #![no_std] at its core with the map aliases behind the default std feature, MSRV 1.77, and optional rand and nightly features.

When to use it

use rustc_hash::FxHashMap;

// A symbol table in a code generator, emitted in iteration order.
fn emit(symbols: &[(&str, u32)]) -> String {
    let mut table: FxHashMap<&str, u32> = FxHashMap::default();
    for (name, id) in symbols {
        table.insert(name, *id);
    }

    table
        .iter()
        .map(|(name, id)| format!("{name}={id}"))
        .collect::<Vec<_>>()
        .join(";")
}

let input = [("alpha", 1), ("beta", 2), ("gamma", 3)];

// The same input gives the same output, every run.
assert_eq!(emit(&input), emit(&input));

use rustc_hash::FxHashMap;
use std::collections::HashMap;

// Interning: map ids to data, looked up constantly.
let mut nodes: FxHashMap<u32, &str> = HashMap::with_capacity_and_hasher(
    1024,
    rustc_hash::FxBuildHasher,
);

for id in 0..1000u32 {
    nodes.insert(id, "node");
}

assert_eq!(nodes.len(), 1000);
assert_eq!(nodes.get(&500), Some(&"node"));
assert_eq!(nodes.get(&5000), None);

use rustc_hash::{FxBuildHasher, FxHasher};
use std::hash::{BuildHasher, Hasher};

// FxBuildHasher is a unit struct, so it needs no construction and no seed.
const HASHER: FxBuildHasher = FxBuildHasher;
let hash = HASHER.hash_one(42u32);
assert_eq!(hash, FxBuildHasher.hash_one(42u32));

// FxHasher::with_seed is const too, for a fixed non-zero seed.
const SEEDED: FxHasher = FxHasher::with_seed(99);
let _ = SEEDED;

// Zero-sized, so a map using it is smaller than a std one.
assert_eq!(std::mem::size_of::<FxBuildHasher>(), 0);
assert_eq!(
    std::mem::size_of::<std::collections::hash_map::RandomState>(),
    16
);

API map

The crate is small: two aliases, two hasher types, and two optional variants that add back the randomness the default deliberately omits.

use rustc_hash::{FxHashMap, FxHashSet};

// default(), not new().
let mut map: FxHashMap<&str, u32> = FxHashMap::default();
map.insert("key", 1);

let mut set: FxHashSet<u32> = FxHashSet::default();
set.insert(1);

assert_eq!(map["key"], 1);
assert!(set.contains(&1));

use rustc_hash::FxBuildHasher;
use std::collections::HashMap;
use std::hash::BuildHasher;

// Pass it to any container generic over its hasher.
let mut map: HashMap<&str, u32, FxBuildHasher> = HashMap::default();
map.insert("a", 1);

// Or hash directly; it is a unit struct, so there is nothing to construct.
let hash = FxBuildHasher.hash_one("a");
assert_eq!(hash, FxBuildHasher.hash_one("a"));
assert_eq!(map["a"], 1);

use rustc_hash::FxHasher;
use std::hash::Hasher;

let mut hasher = FxHasher::default();
hasher.write_u32(42);
hasher.write(b"bytes");
let first = hasher.finish();

// Same writes in the same order give the same result.
let mut again = FxHasher::default();
again.write_u32(42);
again.write(b"bytes");
assert_eq!(first, again.finish());

use rustc_hash::{FxHashMapRand, FxRandomState};
use std::hash::BuildHasher;

// Each instance seeds itself, so the same key hashes differently.
let first = FxRandomState::new();
let second = FxRandomState::new();
assert_ne!(first.hash_one("key"), second.hash_one("key"));

// Eight bytes, against std's sixteen.
assert_eq!(std::mem::size_of::<FxRandomState>(), 8);

let mut map: FxHashMapRand<&str, u32> = FxHashMapRand::default();
map.insert("key", 1);
assert_eq!(map["key"], 1);

use rustc_hash::FxSeededState;
use std::hash::BuildHasher;

let a = FxSeededState::with_seed(7);
let b = FxSeededState::with_seed(7);
let c = FxSeededState::with_seed(8);

// Reproducible per seed, and different between seeds.
assert_eq!(a.hash_one("key"), b.hash_one("key"));
assert_ne!(a.hash_one("key"), c.hash_one("key"));