Hashing in Rust Collections

Hashing is the mechanism that allows HashMap and HashSet to turn an arbitrary key into a storage location inside the collection. Without it, every lookup would have to scan every key, which defeats the point of these data structures. Rust gives you full control over how hashing happens through a pair of traits — Hash for the key types and BuildHasher for the algorithm that produces the actual hash values.

This section explains how those traits work, what the default hashing algorithm does, and when you might want to replace it with something else. Every concept builds on the idea that a hash function must produce the same output for equal keys, and that the map depends on that output to find your data again.

The Hash Trait

Any type you want to use as a key in a HashMap or HashSet must implement the Hash trait. This trait defines a single method, hash, which feeds the type’s data into a Hasher. The Hasher combines that data into a final integer, the hash value.

For most types, you get a Hash implementation automatically by deriving it:

#[derive(Hash, Eq, PartialEq, Debug)]
struct Book {
    isbn: String,
    edition: u32,
}

The derive macro hashes every field in order. If two Book values have the same isbn and edition, they will produce the same hash — exactly what the map needs. When you implement Hash manually, you are responsible for the same guarantee: if two values are equal according to Eq, their hash methods must produce the same result. If you violate this, the map will break in unpredictable ways, but the program will not trigger undefined behavior. Rust’s safety guarantees still hold; you just get a broken map.

Writing a manual implementation is rare. It is only necessary when you want to exclude some fields from hashing — for example, a cache timestamp that does not affect equality — or when you need to control the hashing order. In those cases, you call state.write_* methods on the Hasher for each piece of data that contributes to equality.

The Default Hashing Algorithm

Every HashMap holds a build hasher — an object that knows how to create a fresh Hasher for each operation. By default, that build hasher is RandomState, and the Hasher it produces uses an algorithm called SipHash 1-3.

SipHash is designed to resist HashDoS attacks. In a HashDoS attack, an attacker crafts many keys that all collide to the same hash bucket, turning an O(1) map into O(n) and grinding the server to a halt. SipHash prevents this by seeding each Hasher with a random key generated once per HashMap instance. Two different maps will shuffle the same keys into completely different internal layouts.

That protection comes with a trade-off: SipHash is relatively slow for short keys like integers or small strings. If your program spends most of its time inside the map and you control all the keys, the security guarantee may cost more than it benefits you. That is when you consider a different hasher.

The BuildHasher Trait

BuildHasher is the trait that makes the hashing algorithm swappable. The full type signature of HashMap is HashMap<K, V, S = RandomState>, and that third generic parameter S is the build hasher. When you write HashMap::new(), you get S = RandomState. When you need a custom hasher, you provide a type that implements BuildHasher.

A BuildHasher must produce Hasher values that implement std::hash::Hasher. That lower-level trait provides the write_* methods that the Hash trait feeds into. You rarely implement Hasher from scratch — most custom hashers wrap an existing algorithm like FxHasher or ahash::AHasher. The BuildHasher just needs to know how to construct them.

The standard library provides a convenience wrapper: BuildHasherDefault<H> turns any Hasher that implements Default into a BuildHasher. This is the bridge that lets you drop in third-party hashers without writing any trait implementations yourself.

Why Replace the Default Hasher

There are two practical reasons to choose a different hashing algorithm:

Performance. For workloads dominated by integer keys or tiny strings, a faster non-cryptographic hash function can measurably improve throughput. Crates like rustc-hash (which provides FxHasher) are designed to be fast for exactly these cases. The trade-off is that they offer no protection against crafted collisions; if an attacker can influence the keys, they can degrade the map.

Deterministic ordering. RandomState injects a per-map random seed, so the iteration order of a HashMap changes between runs. For testing or for caching, you sometimes want the same keys to produce the same internal layout every time. A hasher without a random seed — for example, BuildHasherDefault<DefaultHasher> — makes iteration order reproducible for a given set of insertions, though the order is still unspecified and may shift if the insertion order changes.

Using an Alternative Hasher

To use a faster hasher like FxHash from the rustc-hash crate, add it to Cargo.toml and then construct the map with with_hasher.

[dependencies]
rustc-hash = "2"

use rustc_hash::FxBuildHasher;
use std::collections::HashMap;
let mut scores: HashMap<String, u32, FxBuildHasher> =
    HashMap::with_hasher(FxBuildHasher::default());
scores.insert("Alice".to_string(), 95);
scores.insert("Bob".to_string(), 87);

The only difference from the default is the type annotation on HashMap — it now carries a third generic parameter — and the call to with_hasher. The Entry API, iteration, and everything else work identically.

Several other crates follow the same pattern:

• ahash provides AHasher with optional hardware acceleration on CPUs that support AES instructions.
• fnv provides the Fowler–Noll–Vo hash, which is simple and fast for small keys.
• nohash_hasher offers a build hasher that passes the integer key through unchanged, useful when the keys are already well-distributed random numbers.

Each of these exposes a BuildHasher type you can plug directly into HashMap or HashSet.

Implementing a Custom BuildHasher

If none of the existing crates fit your requirements, you can write your own build hasher by implementing BuildHasher. The simplest way is to wrap a Hasher that already implements Default.

use std::hash::{BuildHasher, Hasher};
use std::collections::hash_map::DefaultHasher;
#[derive(Default)]
struct MyBuildHasher;
impl BuildHasher for MyBuildHasher {
    type Hasher = DefaultHasher;
    fn build_hasher(&self) -> DefaultHasher {
        DefaultHasher::new()
    }
}

use std::collections::HashMap;
let mut map: HashMap<i32, String, MyBuildHasher> =
    HashMap::with_hasher(MyBuildHasher::default());
map.insert(1, "one".to_string());

The important detail is type Hasher = DefaultHasher; inside the trait implementation. That associated type tells the compiler what kind of hasher the build hasher produces, and the HashMap will call build_hasher() whenever it needs to compute a hash.

The Contract Between Hash and Eq

The relationship between Hash and Eq is the one rule you must never break: if a == b, then hash(a) must equal hash(b). The map relies on this to locate keys. If a key’s hash changes while the key sits in the map, the map will look in the wrong bucket and treat the key as absent.

A common mistake is to store a key whose hash depends on data that can mutate after insertion. The HashMap documentation warns against using Cell, RefCell, or any form of interior mutability inside a key while it is inside the map.

use std::cell::Cell;
use std::collections::HashMap;
#[derive(Hash, Eq, PartialEq)]
struct MutableKey {
    id: u32,
    tag: Cell<u32>,
}
let key = MutableKey { id: 1, tag: Cell::new(10) };
let mut map = HashMap::new();
map.insert(key, "value");
// Danger: changing tag changes the hash, but the map does not re-index.
map.get(&key).unwrap().tag.set(20);
// The key now lives in the wrong bucket — lookups will likely fail.

The map does not detect this and will not panic. It will simply produce incorrect results for lookups, removals, and re-insertions involving that key. The program remains memory-safe, but the map is logically corrupted.

The same risk exists if you implement Hash and Eq manually on a struct that contains a String and you later mutate that String through a separate path. The only safe approach is to treat keys as immutable while they are inside the map.

Summary

Hashing in Rust collections is a layered system: the Hash trait tells a type how to present itself to a hasher, the Hasher trait defines how to combine that data into a final number, and the BuildHasher trait lets the collection choose which hashing algorithm to use. The default choice — SipHash via RandomState — gives every map a randomized, collision-resistant layout that defends against denial-of-service attacks.

The most important decision you will make about hashing is whether to leave the default alone or to trade security for speed. If profiling shows that the map dominates your runtime and you trust all the keys, switching to a faster hasher like FxHasher or AHasher can be a low-effort optimisation. If you need deterministic iteration order for testing, a non-random hasher gives you that predictability at the cost of attack resistance.

When you move on to working with keys that hold references or interior mutability, the rule to remember is simple: a key’s hash must never change after it enters the map. Breaking that contract does not make your program crash, but it makes your map silently wrong. That is harder to debug than a panic, so the design of Hash and Eq rewards types that are simple, owned, and immutable — the same properties that make Rust’s ownership system comfortable everywhere else.