Capacity and Performance

Because HashMap<K, V> and HashSet<T> are open-addressed hash tables, their lookup speed and memory footprint depend on load factor, table resizing (rehashing), tombstone cleanup, and key/value inline size.

Power-of-Two Bucket Sizing and the 87.5% Load Factor

Internally, HashMap always allocates a power-of-two number of raw buckets ($4, 8, 16, 32, \dots, 2^k$) so bucket indexing uses a single bitwise AND (h1 & (raw_buckets - 1)) instead of slow integer division (%).

To keep probe sequences short, HashMap enforces a maximum load factor of $7/8$ (87.5%):

$$\text{usable capacity} = \text{raw buckets} \times \frac{7}{8}$$

What Happens During a Rehash

When inserting a new element would exceed the $7/8$ load factor (growth_left == 0), HashMap rehashes:

1. Allocates a new table with double the raw buckets ($2^{k+1}$).
2. Recomputes key.hash(&mut hasher) for every existing element in the old table and inserts (K, V) into its new bucket position.
3. Frees the old table.

Unlike Vec<T> reallocation (which is a single contiguous memcpy), rehashing a HashMap must re-hash every key and scatter elements into new bucket offsets. Pre-allocating with HashMap::with_capacity(expected_len) or map.reserve(additional) avoids intermediate rehashes completely:

use std::collections::HashMap;

fn main() {
    // Pre-allocates a 1024-bucket table (usable capacity = 896) in one allocation:
    let mut map: HashMap<u32, u32> = HashMap::with_capacity(500);
    let initial_cap = map.capacity();

    for i in 0..500 {
        map.insert(i, i * 2);
    }

    assert_eq!(map.capacity(), initial_cap);
    println!("Inserted 500 items with 0 rehashes (capacity = {initial_cap})");
}

Inserted 500 items with 0 rehashes (capacity = 896)

Inline Bucket Size and Large Values (Box<V>)

Because SwissTable stores (K, V) pairs directly inline in the bucket array (and leaves $1/8$ of buckets empty as load-factor slack), storing a very large struct V (for example, [u8; 4096]) wastes 4 KiB per empty slot and hurts cache locality during rehashing. When V is hundreds of bytes and the map is sparse or frequently resized, wrapping the value in Box<V> (HashMap<K, Box<LargeStruct>>) keeps each bucket down to an 8-byte pointer.