What bounds do we have on the worst case sizes of
HashMap<K, V> ?
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.
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.
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.
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.
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.