HashMap allows len > capacity

[bluss]

It looks like HashMap::capacity() returns a too small value. It does not always report a capacity greater or equal to current length!

Output:

len=116, cap=116
len=117, cap=116
len=118, cap=232

Testcase (playpen)

use std::collections::HashMap;

fn main() {
    let mut x = HashMap::new();

    for i in 0..116 {
        x.insert(i, 0);
    }
    println!("len={}, cap={}", x.len(), x.capacity());
    x.insert(1729, 0);
    println!("len={}, cap={}", x.len(), x.capacity());
    x.insert(1730, 0);
    println!("len={}, cap={}", x.len(), x.capacity());
}

[Gankra]

If I recall correctly, this was known in designing this. The issue is basically an artifact of integer rounding from doing this computations efficiently. This isn't a soundness issue or anything. It's just that the capacity is supposed to be a hasty lower-bound on how many elements you can cram in before a reallocation happens, and this is a degenerate consequence of this.

A monkey-patch over this would be to just make capacity() yield max(capacity(), len). This should be fine since that method isn't used internally, and it's not otherwise something you'd expect in a hot path.

[rthomas]

Hey - first PR for rust, thought I would give this one a try as the suggested solution seemed quite straightforward.

[rthomas]

This can be closed now, as the PR has been merged.

[bluss]

@rthomas Thank you! Closed by #30991