Size bounds on Vec<T>, HashMap<K, V>

What bounds do we have on the worst case sizes of Vec<T> and HashMap<K, V> ?

For Vec<T>, assuming only push/modification (and no pop) I believe it is O(1) + 2 * n * sizeof(T), because the 'push' on the Vec may allocate double the space.

For HashMap<K, V> do we have any bounds?

Context: dealing with data structures where storing the data itself is in the GBs, so want to calculate if the worst case fits in RAM.

I imagine HashMap will have similar bounds, with it consuming 2x the map's capacity plus/minus a key-value pair.

The version in std is based on SwissTable, and they went through how it works in a fair amount of detail at a cppcon talk a while back. That'll probably have the technical details you are looking for.

1 Like

Minor nitpick: in the Vec case, I think we have:

length <= capacity <= 2 * length

Above, do you mean '2x map's capacity' or '2x map's length' ? If '2x capacity', what is the intuition ?

This code is probably key to finding the value. The "load" adds some space overhead, but it looks like it's still bumping up to powers of two. I didn't look deep enough to make any strong statements (such as a formula), and I don't know if there's any actual documented guarantees you can rely on.

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.