How Rust's HashMap Works Internally

Rust's HashMap looks small from the outside: hash a key, find a slot, return a value. The current standard-library implementation is built around SwissTable ideas, which make that lookup less like following a chain and more like scanning a compact index.

Those internals are not part of Rust's stable API. They can change without breaking user code. The useful part is understanding the shape of the current design and the costs it creates.

1. Hashing is supplied, not hard-coded

HashMap<K, V, S> stores a hash builder S. Each operation asks it for a hasher, feeds the key through Hash, and uses the resulting integer to begin a lookup. The default RandomState is seeded per map, which makes deliberately constructed collision attacks harder.

The exact default hashing algorithm is deliberately not a contract. Code that needs a different speed or security trade-off can provide another BuildHasher, but every key already in a map must have been processed by the same builder.

2. Control bytes narrow the search

The table keeps key-value storage alongside a compact control byte for each bucket. A control byte records whether the bucket is full, empty, or deleted. For a full bucket it also keeps a short fingerprint derived from the hash.

The remaining hash bits choose the first group of buckets to inspect. The table compares the wanted fingerprint against a group of control bytes at once, using vector instructions where they are available. Only matching fingerprints become candidates for a full key comparison.

That separation matters. Most misses are rejected by metadata that is much smaller and denser than the keys themselves.

3. Collisions probe another group

This is open addressing: colliding entries live elsewhere in the same table, not in a linked structure hanging from one bucket. If the first group does not contain the key, the probe sequence moves to another group and continues.

A genuinely empty bucket ends an unsuccessful lookup. A deleted bucket cannot, because entries later in the probe sequence may still depend on that path. Deletion therefore leaves a tombstone until later maintenance can reclaim it.

4. Capacity leaves room for probing

The table grows before every bucket is occupied. The SwissTable-style layout keeps roughly one slot in eight available so lookups usually find an empty bucket quickly; the exact growth policy remains an implementation detail.

Growing allocates a larger raw table and redistributes the entries. If the approximate size is already known, with_capacity or reserve avoids repeating that work.

use std::collections::HashMap;
 
let mut counts: HashMap<String, u64> = HashMap::with_capacity(1_024);
 
for word in ["timeout", "retry", "timeout"] {
    *counts.entry(word.to_owned()).or_insert(0) += 1;
}
 
// String implements Borrow<str>, so this lookup allocates nothing.
assert_eq!(counts.get("timeout"), Some(&2));

5. Ownership shapes the public API

Insertion moves owned keys and values into the map. Lookup is more flexible: get can accept a borrowed form of the key when the stored key implements Borrow for it and both forms hash and compare the same way. A map keyed by String can therefore be queried with &str.

The entry API performs the lookup once and then exposes the occupied or vacant case. That is why counters and in-place updates use entry instead of a get-then-insert pair.

Conclusion

The useful model is a hash builder feeding an open-addressed table, with compact metadata filtering candidates before key comparison. Rust then layers ownership, borrowing, and entry on top so callers can use that table without giving up the language's usual guarantees.