Amortize the cost of small tables about hashbrown HOT 7 CLOSED

I think jumping from 0 to 4 or even 8 would be fine.

from hashbrown.

Exponential strategy (doubling) works well to prevent reallocation. However when memory space is limited doubling might not be possible. Is it possible to provide (and change) a maximum growth size?

from hashbrown.

From my perspective as a mentor on Exercism, and my observations of new Rustaceans:

Hashmaps, probably due to having no literal syntax, seem to rarely be declared for just 2 values. Even people who come from langs which throw hashmaps everywhere will not use them as often because it requires the mental overhead of the use. When people want a tiny amount of k/v pairs, I often see them juggle some tuples or even declare tiny structs. HashMaps are favored when (from the logical perspective) you would have potentially Many and they want to do dynamic access.

So: yeah, 0 -> (4|8) seems fine.

from hashbrown.

Unlike a vector, the size of the hash table must be a power of two since we use a bit mask on the hash to map it to a table index. There are different table designs which use non-power-of-two sizes but they are generally much slower.

from hashbrown.

One thing we can infer here is that doubling the table size of a small hash table does not really double its size in bytes. This is very much unlike Vec, where doubling the buffer always makes it exactly twice as large in bytes.

I think it would be more appropriate to skip some powers of two when growing small hash tables. Growing table size as 0 -> 4 -> 16 -> 32 -> 64 -> 128 -> ... seems like a fine strategy to me, for example.

from hashbrown.

The reason why the size doesn't exactly double is that there is a fixed cost of 16 bytes in each allocation. There are 16 + N control bytes and N element slots. So the size is calculated as 16 + N + sizeof(T) * N.

from hashbrown.

By comparison, here is what the std HashMap does:

from hashbrown.