Hands-On Data Structures and Algorithms with Rust

Architecture

HashMap is a highly optimized data structure that employs a performance heuristic called Robin Hood hashing to improve caching behavior, and thereby lookup times.

Robin Hood hashing is best explained together with the insertion algorithm linear probing, which is somewhat similar to the algorithm used in the hash map of the previous chapter. However, instead of an array of arrays (or Vec<Vec<(K, V)>>), the basic data structure is a flat array wrapped (together with all unsafe code) in a structure called RawTable<K, V>.

The table organizes its data into buckets (empty or full) that represent the data at a particular hash. Linear probing means that whenever a collision occurs (two hashes are equal without their keys being equal), ...