Internally, you can imagine the HashMap as being implemented as two vectors: a table, and a buffer. Of course, we're simplifying here; there are actually no vectors in the implementation. But this analogy is accurate enough.
If you want to look at the actual implementation, feel free to do so, as Rust is completely open source: https://github.com/rust-lang/rust/blob/master/src/libstd/collections/hash/table.rs.
In the background, the buffer stores our values in a sequential fashion. In the front, we have a table storing buckets that don't do much more than point to the element they stand for. When you insert a key-value pair, what happens is:
- The value gets put in the buffer.
- The key goes through a hashing function and becomes an index.
- The table creates a bucket at said index that points to the actual value:
Rust's hashing algorithm doesn't actually generate unique indices, for performance reasons. Instead, Rust uses a clever way to handle hash...