HashMap reallocates even though capacity is not exceeded

HashMap::with_capacity's documentation states:

The hash map will be able to hold at least capacity elements without reallocating. This method is allowed to allocate for more elements than capacity.

This statement is incorrect as the following code demonstrates.

fn main() {
    let initial_capacity = 100;
    let mut a = std::collections::HashMap::<u32, ()>::with_capacity(initial_capacity);
    let mut current_capacity = initial_capacity;
    for i in 0..1_000 {
        let new_capacity = a.capacity();
        if new_capacity != current_capacity {
            println!("iteration {i}, new capacity {new_capacity}");
            current_capacity = a.capacity();
        }

        assert!(a.len() < initial_capacity);
        a.insert(i, ());
        if a.len() == initial_capacity {
            a.remove(&i).unwrap();
        }
    }
}

A possible output of this program is as follows. It is a possible output because the default hasher is randomly seeded. You can make it deterministic with a custom hasher.

iteration 0, new capacity 112
iteration 100, new capacity 111
iteration 101, new capacity 110
iteration 105, new capacity 109
iteration 109, new capacity 108
iteration 111, new capacity 107
iteration 125, new capacity 106
iteration 137, new capacity 105
iteration 138, new capacity 104
iteration 141, new capacity 103
iteration 165, new capacity 102
iteration 187, new capacity 101
iteration 188, new capacity 100
iteration 252, new capacity 99
iteration 253, new capacity 224

As you can see in the output the capacity jumps from the initial 112 to 224 in iteration 253. This means the HashMap has allocated more memory. However, as the assert shows, the HashMap never held more elements than the initial capacity. This violates the guarantee documented in with_capacity.

This is a bug in hashbrown. I've opened an issue there too https://github.com/rust-lang/hashbrown/issues/602 .

Start by running the reproduction in the issue and reading HashMap::with_capacity and capacity behavior in hashbrown, including the linked hashbrown issue 602. Compare the observed reallocations with the documented guarantee; done means the behavior and documentation agree, with regression coverage for staying within the requested capacity.