HashMap Performance in Rust and Faster Hashers Step by Step

A HashMap<u64, u64> lookup should be a few nanoseconds, and with the default hasher a large share of that is the hash function. Rust chose a safe default because a hash table that an attacker can degrade into a list is a denial-of-service bug. Trusted data does not need that protection, and swapping the hasher is a one-line change. This post covers the change, the risk and the order to try things. It sits in the performance cluster after Rust performance basics.

Rust 1.90, rustc-hash 2, ahash 0.8.

Swap the hasher

[dependencies]
rustc-hash = "2"

use rustc_hash::FxHashMap;

fn main() {
    let mut counts: FxHashMap<u32, u32> = FxHashMap::default();
    for n in [3, 1, 3, 2, 3] {
        *counts.entry(n).or_insert(0) += 1;
    }
    println!("{}", counts[&3]);
}

It prints 3. FxHashMap is HashMap<K, V, FxBuildHasher>; the API is otherwise identical, except new() is not available and you use default() or with_hasher. Switching the type alias in one place changes the whole program.

What you pay and get

The ranking is stable, and the size of the gap varies with key size and map size. For integer keys the differences are largest, and for long string keys the cost of reading the key dominates. A benchmark with real keys is the only reliable answer, as described in benchmarking pitfalls.

The security trade-off

A hash table degrades when many keys land in one bucket. With a predictable hasher such as Fx, an attacker who controls the keys can compute colliding ones. A request handler that stores header names or query parameters in an FxHashMap can be driven to O(n²) behavior with a modest request. Rules of thumb:

• Keys that you generate (indices, interned ids, enum values): any hasher
• Keys that come from files you control: any hasher
• Keys from the network or users: default hasher or a randomly seeded one

The attack class is covered in denial of service through parsers.

Cheaper wins first

1. Pre-size with HashMap::with_capacity_and_hasher, avoiding rehashing during growth.
2. Borrow for lookups. map.get("key") works on HashMap<String, V> because String: Borrow<str>, and needs no allocation.
3. Shrink the key. Interning strings to u32 ids turns a string hash into an integer hash.
4. Use a different structure. For dense small integer keys, a Vec indexed by the key is faster than any hash map. For a handful of keys, a sorted Vec and linear search is.

Limits

Iteration order is unspecified and differs by hasher, so tests should not depend on it. Deterministic hashers make runs reproducible, which is useful for debugging a compiler-like workload and not a security property. The HashMap documentation explains the default in the HashMap hashing section.