๐ŸŽ“ A1Learner
๐Ÿ”

Rust Faster Hashing

Faster hashing means swapping a HashMap's hasher for a quicker algorithm. The default hasher is SipHash 1-3, a careful bodyguard against attack.

The default: safe, not fastest

Every HashMap you have built so far uses the SipHash bodyguard:

let mut scores: HashMap<u64, u64> = HashMap::new();
scores.insert(7, 100);

The swap is one line

Same shape, different engine โ€” FxHashMap comes from the rustc-hash crate:

// rustc-hash = "2"
use rustc_hash::FxHashMap;
let mut scores: FxHashMap<u64, u64> = FxHashMap::default();
scores.insert(7, 100);

Or keep std's map, plug in the hasher

HashMap takes the hasher as a third building block, so std's map can wear the faster engine:

use std::collections::HashMap;
use std::hash::BuildHasherDefault;
use rustc_hash::FxHasher;
let mut scores: HashMap<u64, u64, BuildHasherDefault<FxHasher>> = HashMap::default();
scores.insert(7, 100);

Example

// Cargo.toml: rustc-hash = "2"
use std::collections::HashMap;
use rustc_hash::FxHashMap;
fn main() {
    let mut std_map: HashMap<u64, u64> = HashMap::new();
    let mut fx_map: FxHashMap<u64, u64> = FxHashMap::default();
    for k in 0..200_000u64 {
        std_map.insert(k, k * 3);
        fx_map.insert(k, k * 3);
    }
    let mut std_total = 0u64;
    let mut fx_total = 0u64;
    for k in 0..200_000u64 {
        std_total += std_map[&k];
        fx_total += fx_map[&k];
    }
    println!("std: {} entries, total = {std_total}", std_map.len());
    println!("fx: {} entries, total = {fx_total}", fx_map.len());
    println!("same answers = {}", std_total == fx_total);
}

Key points

  • Hasher: the algorithm that turns a key into the number that picks its bucket
  • The default hasher is SipHash 1-3
  • It is high quality and safe against hash-flooding attacks
  • But it is comparatively slow, especially on short integer keys
  • Hash flooding (HashDoS): an attacker crafts keys that collide on purpose
  • The collisions slow a service to a crawl
  • The default hasher exists to stop exactly this
  • The rustc-hash crate provides FxHashMap and FxHashSet
  • They are drop-in replacements
  • Their hasher is far faster for integer keys
  • But they offer no flooding protection
  • ahash and fnv are other fast hashers worth benchmarking if hashing stays hot after the swap
  • Some keys barely need hashing: an already-random integer can use the nohash-hasher crate, which returns the value almost as-is

In this example, the same 200,000 integer keys are inserted and looked up in both maps. Both maps agree on every answer. The swap changes speed, never results. Timed runs for this course did the identical work in about half the time with the Fx map. Best runs: 13 ms against 24 ms, and 35 ms against 70 ms. That is the whole point of the swap: measure the default, swap one line, measure again.

Note

Only swap hashers for maps whose keys you control

If strangers on the internet supply the keys, keep the default bodyguard

Try it Yourself

Edit the code, then press Run.

Running is simulated ยท Rust Playground

Exercise

When is swapping to FxHashMap a bad idea?