Hands-On Concurrency with Rust

Standard library HashMap

Let's poke around in HashMap's internals. A good starting place, I find, for inspecting unfamiliar Rust data structures is jumping into the source to the struct definition itself. Especially in the Rust codebase, there will be public rustdoc comments and private comments explaining implementation ambitions. The reader is warmly encouraged to inspect the HashMap comments for themselves. In this book, we're inspecting Rust at SHA da569fa9ddf8369a9809184d43c600dc06bd4b4d. The comments of src/libstd/collections/hash/map.rs explain that the HashMap is implemented with linear probing Robin Hood bucket stealing. Linear probing implies that we'll find HashMap implemented in terms of a cell storage—probably a contiguous memory ...