Clarify documentation on HashMap::capacity()

[tomjakubowski]

The documentation for HashMap::capacity() says:

Returns the number of elements the map can hold without reallocating.

However, a HashMap will sometimes store more elements than its capacity indicates. See this example (Playpen link):

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    for i in 0..1000 {
        map.insert(i, i);
        let (cap, len) = (map.capacity(), map.len());
        assert!(cap >= len, "cap {} len {}", cap, len);
    }
}

[sfackler]

Seems to me like this is more of a bug in capacity rather than a docs issue. cc @gankro

[Gankra]

This is intended behaviour. It's a lower-bound.

[tomjakubowski]

@gankro maybe the wrong venue for this question, but as a user of HashMap is there a way to know whether an operation resizes a HashMap + moves its allocation, either in advance or after the operation has completed? More precisely, I guess I'd like to know whether any value in the HashMap has been relocated.

If values are only moved when a resize happens I suppose I could just take a pointer to some value before the operation, and then locate it again and compare its address after the operation.

[pnkfelix]

@tomjakubowski I think you cannot predict whether a value will be moved, regardless of whether the hashmap is resized.

In particular, we use robin-hood hashing which can move elements around (essentially as an attempt to move the most frequently accessed elements to an earlier point in the chain of hash-colliding elements).

[Gankra]

robin-hood doesn't do "most frequent" but rather "furthest from its ideal". But yeah all the elements are in general slowly drifting to higher addresses. You'd need a chaining hashmap to try to guarantee position properties. Even then an optimized chaining map wouldn't try to preserve that property.

If you want to know if a reallocation happened just check if the capacity has increased. It's a lower-bound but it's fairly accurate.

[tomjakubowski]

Ah, I see. Thanks for the clarification @gankro and @pnkfelix

[steveklabnik]

So, this isn't a bug then? Or should we clarify that it's a lower bound?

[Gankra]

Hmm... I thought I specifically worded the docs to make this more clear (or at least, more debateable). Yes clarifying that for HashMap it is a lower bound seems appropriate. Although it might not even be that if we decide to allow reallocs if degenerate collisions are detected...