4.2 · HashMap and HashSet: Hashing Internals and Custom Hashers

Domain 4 — Collections Deep Dive Duration: ~15 minutes Library components: std::collections::HashMap, std::collections::HashSet, std::collections::hash_map::Entry, std::hash::Hash, std::hash::Hasher, std::hash::BuildHasher, std::hash::RandomState

Introduction

HashMap is the most common collection in Rust after Vec. Its lookups, insertions, and removals are amortized O(1). It has all that you need for key-value storage when the order is not important.

Internally, the standard library uses an implementation based on SwissTable (adopted from absl::flat_hash_map of Google). This implementation does quadratic probing, and SIMD instructions accelerate its metadata lookups. You do not need to know these internals to use the type. But they explain why the API has its shape, and why the iteration order is not predictable.

HashSet is literally HashMap<K, ()>. Each set operation is a thin wrapper around the related map operation, with no value type. When you need only membership, and not associated data, HashSet shows that intent clearly. It also has dedicated methods for set algebra.

This tutorial shows:

• How to create a HashMap, and how to insert, find, remove, and iterate its entries.
• The Entry API: or_insert, or_insert_with, and_modify, or_default.
• RandomState and BuildHasher, the trait for hasher factories.
• The Hash trait and the hash/eq contract.
• How to supply custom hashers.
• HashSet operations and set algebra.

HashMap Basics

Creation

HashMap::new() starts with zero capacity. HashMap::with_capacity(n) allocates space for at least n entries. Use it when the size is predictable, to prevent reallocations.

use std::collections::HashMap;

// An empty map does not allocate.
let mut hits: HashMap<&str, u64> = HashMap::new();
// len=0, cap=0

// One allocation with space for at least 100 entries.
let prealloc: HashMap<String, i32> = HashMap::with_capacity(100);
// len=0, cap >= 100

You can also make a map from an array of tuples with HashMap::from([(k, v), ...]). Or you can collect an iterator of (K, V) pairs into a map.

Insertion and Replacement

insert(key, value) returns Option<V>: Some(old) if the key was already present, and None if it was not. Thus you can detect a replacement, and you do not need a separate lookup.

// `hits` is the empty HashMap<&str, u64> from the previous snippet.
hits.insert("/index", 120);      // returns None: the key is new
hits.insert("/about", 45);
hits.insert("/api/data", 300);

let old = hits.insert("/about", 46);   // the key exists: 46 replaces 45
// old == Some(45), the previous value

Lookup

There are three ways to read a value:

Use get() in production code. The index operator is convenient in tests and assertions, where you know that the key exists.

Removal

remove(&key) returns Option<V>. remove_entry(&key) returns Option<(K, V)>. Use remove_entry when you need the owned key again (for example, a String that you want to use again).

Iteration

The iteration order is non-deterministic. Each call to keys(), values(), or iter(), and each for loop, may yield the entries in a different order. The order may also change between two runs of the same binary. If you need sorted output, collect the keys into a Vec and sort the Vec.

With values_mut() and iter_mut(), you change the values in place. You do not remove the entries and insert them again.

04_05_hashmap_basics.rs prints the output below. A line with (order varies) shows a map in Debug format, and the order of its entries changes between runs:

empty map: len=0, cap=0
with_capacity(100): len=0, cap≥100=true

after inserts: {"/index": 120, "/api/data": 300, "/about": 45}   # (order varies)
replaced /about: old=Some(45), new=Some(46)

hits["/api/data"] = 300

removed /about: Some(46)
remove_entry: Some(("/health", 999))

scores:
  alice: 90
  bob: 85
  carol: 95
total score = 270
after +5 curve: total = 285

collected from tuples: {"y": 2, "x": 1}   # (order varies)

All assertions passed.

The Entry API

A very common pattern is: find a key, and if the key is absent, insert a default value. HashMap has a full sub-API for this pattern. map.entry(key) returns an Entry enum, which is Occupied (the key exists) or Vacant (the key does not exist). With the methods of Entry, you handle the two cases in one expression and with only one lookup.

Figure: The Entry API Flow

or_insert

or_insert inserts its argument as the default value if the key is absent. Then it returns &mut V:

// word_count: HashMap<&str, u32>, initially empty.
let count = word_count.entry("the").or_insert(0);   // count: &mut u32
*count += 1;                                        // the first call changes 0 to 1

This is the usual pattern to count word frequencies. Rust always evaluates the argument of or_insert, also when the key exists. If the default value is expensive to create, use or_insert_with.

or_insert_with

or_insert_with accepts a closure and calls it only when the key is absent:

// cache: HashMap<String, Vec<u8>>. `key` is a String.
// `expensive_computation` represents a slow function that returns a Vec<u8>.
let data = cache.entry(key).or_insert_with(|| {
    expensive_computation()   // runs only on a cache miss
});
// data: &mut Vec<u8>, the value that is now in the cache

Thus, on a cache hit, the program does not allocate or compute a default value that it discards immediately.

or_default

or_default is the short form of or_insert_with(Default::default). Use it when the value type implements Default. Vec, String, u32, and most standard types implement Default:

// groups: HashMap<char, Vec<String>>. `name` is a &str and `initial` is its first char.
// For a new initial, or_default inserts an empty Vec. It returns &mut Vec<String>.
groups.entry(initial).or_default().push(name.to_string());

and_modify

and_modify runs a closure on the value if the key exists. Put it before or_insert or or_default, which handle the absent key:

// stock: HashMap<&str, i32>. `ticker` is a &str and `qty` is an i32.
stock.entry(ticker)
    .and_modify(|holding| *holding += qty)   // the key exists: add qty to the value
    .or_insert(qty);                         // the key is absent: insert qty

This chain has two cases. If the key exists, it updates the value. If the key does not exist, it sets the initial value.

key()

You can read the key of an Entry, and the call does not consume the Entry. Use key() for logging, or for a condition before you decide to insert:

// map: HashMap<String, i32>, initially empty.
let entry = map.entry("hello".to_string());   // a Vacant entry that owns the key
println!("entry key = {:?}", entry.key());    // key() borrows the key: "hello"
entry.or_insert(42);                          // consumes the entry and inserts 42

04_06_entry_api.rs prints:

word_count: {"the": 3, "on": 1, "mat": 1, "sat": 1, "cat": 2}   # (order varies)

  computing default for session_42...
cache hit for session_42: len=64

groups by initial: {'C': ["Charlie", "Cleo"], 'A': ["Alice", "Ada"], 'B': ["Bob", "Brenda"]}   # (order varies)

portfolio: {"AAPL": 7, "GOOG": 13, "MSFT": 20}   # (order varies)

page visits: {"/about": 1, "/home": 3}   # (order varies)

entry key = "hello"

All assertions passed.

SwissTable Internals (Conceptual)

In Rust 1.36, a SwissTable design replaced the Robin Hood hashing implementation of HashMap. The primary ideas are:

1. Flat, open-addressed layout. All entries are in one contiguous array of buckets. There are no linked lists and no chains on the heap. This layout gives very good cache locality.

2. Metadata bytes. Each bucket has a control field of one byte. The field contains a 7-bit part of the hash (the "H2" hash) and a status bit. One SIMD instruction can load and compare a group of control bytes. A group has 16 bytes with SSE2 on x86-64, and 8 bytes with NEON on AArch64. Thus the table examines all the candidate buckets of a group in parallel.

3. Quadratic probing. When a collision occurs, the table probes the subsequent groups at offsets that increase quadratically. In each group, the SIMD lookup examines all the candidates at the same time.

4. Growth policy. The table grows when the load factor is more than approximately 7/8. To grow, the table hashes each entry again into a new, larger table.

Figure: SwissTable Conceptual Layout

You never use these details directly. The important effect that you can see is that the iteration order is non-deterministic. The table layout depends on the insertion order, the capacity, and the random hash seed.

RandomState and BuildHasher

Each HashMap keeps a hasher factory together with its buckets. The default factory is RandomState. At construction time, RandomState seeds the hasher with random bytes from the OS. This seed is a defense against HashDoS attacks. In such an attack, an attacker sends many keys with the same hash value, to make your map lookups O(n). The attack fails because the hash function is different for each map instance.

BuildHasher is the trait that describes a hasher factory:

pub trait BuildHasher {
    type Hasher: Hasher;                      // the hasher type that the factory makes
    fn build_hasher(&self) -> Self::Hasher;   // makes one new hasher
    // The trait also has a provided method, `hash_one`.
}

RandomState implements BuildHasher. Each call to build_hasher() returns a Hasher with the seed of that RandomState. Two different RandomState instances typically give different hashes for the same input:

use std::hash::{BuildHasher, RandomState};

let rs1 = RandomState::new();   // each instance has its own seed
let rs2 = RandomState::new();
// hash(42) through rs1 != hash(42) through rs2 (usually)

Deterministic Hashing with BuildHasherDefault

For tests, benchmarks, or applications where HashDoS is not a risk, you can use BuildHasherDefault<DefaultHasher>. It gives you a deterministic hasher:

use std::hash::BuildHasherDefault;
use std::collections::HashMap;
use std::hash::DefaultHasher;

// The third type parameter of HashMap is the hasher factory.
// BuildHasherDefault makes each hasher with DefaultHasher::default(): no random seed.
let map: HashMap<&str, i32, BuildHasherDefault<DefaultHasher>> =
    HashMap::with_hasher(BuildHasherDefault::default());

Tutorial 13.2 explains in detail how to implement a custom Hasher state machine and a BuildHasher.

04_07_custom_hash.rs prints the output below. Its first lines use the GridPoint key type, which the subsequent section shows. The RandomState hashes change in each run. The DefaultHasher results are the same in each run, but a different Rust release can change them:

lookup (0,0) with different label: Some("home base")

hash(p1)          = 13646096770106105413   # (same value in each run)
hash(p1_relabeled) = 13646096770106105413   # (same value as hash(p1))
hashes match (label excluded): true

RandomState seed 1 → hash(42) = 14353867740142031612   # (varies)
RandomState seed 2 → hash(42) = 7071660002262858912   # (varies)

map with DefaultHasher: {"beta": 2, "alpha": 1}   # (same order in each run)

palette lookup red: Some("red")

All assertions passed.

The Hash Trait and the Hash/Eq Contract

Each type that you use as a HashMap key (or a HashSet element) must implement Hash and Eq. A strict contract connects these two implementations:

If a == b, then hash(a) == hash(b).

The contract does not require the converse. Different values may have the same hash, and collisions are normal. But if two equal values have different hashes, the map silently loses entries. It searches for the key in one bucket, but the entry is in a different bucket.

Deriving Hash

When equality uses all the fields, derive the two traits:

// The two derives use the same fields: r, g, and b.
#[derive(Hash, PartialEq, Eq)]
struct Color { r: u8, g: u8, b: u8 }

The derived Hash gives each field to the hasher in declaration order. The derived PartialEq compares each field. Thus the contract holds automatically.

Manual Hash Implementation

Sometimes only some fields define identity. For example, a struct can have a label field that is only text for the user, and not a part of logical equality. Then you must implement Hash manually and hash exactly the fields that PartialEq uses:

// `Hash` and `Hasher` are the traits from std::hash.
struct GridPoint {
    x: i32,
    y: i32,
    label: String, // not part of identity
}

// Equality compares x and y only.
impl PartialEq for GridPoint {
    fn eq(&self, other: &Self) -> bool {
        self.x == other.x && self.y == other.y
    }
}
impl Eq for GridPoint {}

// Hash the same fields that `eq` compares: x and y.
impl Hash for GridPoint {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.x.hash(state);
        self.y.hash(state);
        // `label` is absent on purpose
    }
}

Now two GridPoint values with the same (x, y) but different labels have the same hash and compare as equal. A lookup gives the correct result, and the label of the lookup key has no effect.

Common Mistakes

• Hash uses more fields than Eq compares. This breaks the contract. Two values can be == and have different hashes. This is the dangerous case.
• Hash uses fewer fields than Eq compares. This is not a correctness bug. Two values can be != and have the same hash. The contract permits this: it is only a collision.
• Floating-point fields. f32 and f64 do not implement Hash. The reason is NaN != NaN, which makes the contract impossible to keep. If you need floats as keys, use a wrapper that orders the bits, or the ordered-float crate.

HashSet: When a Set Is Better Than a Map

HashSet<T> is a HashMap<T, ()> with a simpler API. Use it when you need membership and uniqueness but have no associated value.

Creation and Membership

use std::collections::HashSet;

let mut visited: HashSet<&str> = HashSet::new();
visited.insert("Paris");    // returns true: the value is new
visited.insert("Tokyo");
visited.insert("Berlin");
visited.insert("Paris");    // returns false: the value is already present

visited.contains("Tokyo");  // true
visited.remove("Berlin");   // true: the value was present

To remove duplicates in one line, collect an iterator into a HashSet:

let unique: HashSet<i32> = vec![1, 2, 2, 3, 3, 3, 4].into_iter().collect();
// unique contains 1, 2, 3, and 4, in an arbitrary order

Set Algebra

HashSet has the four standard operations of set algebra. Each method returns a lazy iterator:

The method forms return iterators of &T. The operator forms (&, |, ^, -) return new owned HashSet<T> values. They are convenient, but they allocate.

Subset, Superset, and Disjoint

let small: HashSet<i32> = HashSet::from([3, 4]);
let big: HashSet<i32>   = HashSet::from([1, 2, 3, 4, 5]);

small.is_subset(&big);    // true: 3 and 4 are in `big`
big.is_superset(&small);  // true: the same test from the other side
small.is_disjoint(&HashSet::from([10, 20])); // true: the sets have no common element

is_subset checks that each element of self is in the other set. is_disjoint checks that the intersection is empty. The two methods stop at the first counterexample.

04_08_hashset.rs prints the output below. The Debug format of a HashSet shows the elements in an order that changes between runs:

visited: {"Berlin", "Paris", "Tokyo"}   # (order varies)
primes: {2, 11, 5, 13, 3, 7}   # (order varies)
unique: {2, 3, 4, 1}   # (order varies)

contains Tokyo: true
removed Berlin: true

A = {4, 2, 5, 3, 1}   # (order varies)
B = {7, 3, 4, 5, 6}   # (order varies)
A ∪ B = {6, 3, 2, 5, 1, 7, 4}   # (order varies)
A ∩ B = {5, 4, 3}   # (order varies)
A \ B = {2, 1}   # (order varies)
A △ B = {7, 1, 6, 2}   # (order varies)

{3,4} ⊂ {1..5}: true
disjoint with {10,20}: true

bitwise operators work too: &x & &y = {2, 3}   # (order varies)

All assertions passed.

Summary

Code Examples