Disclaimer: I discovered a previous explanation here but I found it a little confusing, so I’m hoping mine is easier to follow.
Rust’s HashMap (and HashSet and Vec) collections both offer an initialization
method fn with_capacity(capacity: usize) that allocates enough memory up front to hold
capacity elements. Why don’t BTreeMap (and BTreeSet) also have this method?
The answer lies in the difference between how the two structs are laid out in memory.
In short, HashMap, like Vec, uses an array (a contiguous block of memory), which is
required to get O(1) insertion and lookup by element index. In Vec, this is done
explicitly, but in HashMap, the key is hashed and then translated to the index where
the value resides in the array.
Let’s take a HashMap with room for four entries (I’m going to omit real-world
implementation details like bucketing in the case of collisions, for the sake of
simplicity). It’s in essence a four element array. Here’s a representation of the memory
for a HashMap with three entries (let’s say a byte each) and room for one more (light
green is a filled byte of memory and dark is empty, though reserved for the struct).
Say we insert two more elements. Now we’ll need to allocate more memory in order to hold the fifth. Usual implementations double the size of the array (so we don’t need to allocate for every single insertion). Under ideal conditions, we can just take the next four bytes of memory.
(In actuality, the elements are unlikely to be filled contiguously like this, since the hasher will output an array index with roughly even random distribution)
However, what if some other struct has been allocated some of those next four bytes?
In this case, we need to move the entire HashMap to a place in memory where there’s
room for eight entries. Instead of allocating just four more bytes, we need to first
deallocate four bytes and then allocate eight, which is much more expensive.
This is where with_capacity() comes in. If we know we’re going to eventually have at
least five elements, it makes sense to allocate all eight bytes up front so we don’t
need to deallocate and reallocate, which is exactly what with_capacity() does.
So why doesn’t BTreeMap have this method? Take a look at how a BTree
works.
For this example, I’m going to simplify it into a regular binary search tree. The
difference between the two is essentially that a BST has a single value and two pointers
per node, but a BTree has an array of values and an array of pointers:
For the purposes of this explanation, they’re more or less equivalent.
Each node in the BST consists of a value and pointers to its left and right children.
Here’s a BTreeMap with a single node and value (light blue). The second and third dark
blue bytes are reserved for pointers to its children, which are empty at present.
When an element is inserted, a new node is created and memory for it is allocated. Since
pointers can point to any memory address, there’s no need to require the nodes to be in
sequential bytes of memory as with HashMap. Here’s what it might look like if we were
to insert a new entry:
We can put it anywhere we have at least three bytes of memory free. Nodes of a
BTreeMap can be spread out over the program’s memory, since we’re free of the
constraint of having to keep the entries contiguously. This means that we will never
have to deallocate and reallocate old entries, so we don’t get to save any cycles (over
the program’s entire runtime) by allocating extra memory at BTreeMap’s initialization.
Maybe BTreeMap::with_capacity() would make sense if you’d explicitly like to pay for
the allocation ahead of time in order to save time during insertion, if latency is more
costly at that point, but I suppose this use case may be a bit too specific for a
standard library function. There’s a delicate balance between usefulness and bloat.