Rust HashMap: Fast, Secure Key-Value Storage

WHY IT EXISTS Hash maps exist to provide a high-performance way to store and retrieve data associated with a unique key. Unlike an array which requires an integer index, a HashMap lets you use more complex types like strings as keys, enabling average-case O(1) time complexity for lookups, insertions, and deletions.

THE MENTAL MODEL Think of a HashMap as a coat check. You hand over your coat (the value) and get a unique ticket (the key). To retrieve your coat, you present the ticket. The system doesn't care about the order you arrived; it just needs the ticket to find your coat almost instantly. The key must be unique, and you cannot alter the ticket number after it has been issued.

HOW IT WORKS Rust's HashMap is a port of Google's highly optimized SwissTable, which uses quadratic probing and SIMD instructions for fast lookups. When you insert a (key, value) pair, the map computes a hash of the key to determine where to store the value in an internal array. To retrieve the value, it re-hashes the key to find its location. By default, it uses a cryptographically secure hashing algorithm (SipHash 1-3) seeded with a random number. This protects against HashDoS (Hash Denial of Service) attacks, where a malicious user could craft keys that all hash to the same bucket, degrading performance.

WHEN TO USE IT Use HashMap whenever you need to associate values with keys. It is the idiomatic choice for tasks like caching the results of expensive computations, counting item frequencies in a collection, or representing objects with named properties. Its performance is excellent for a wide range of key sizes.

WHEN NOT TO USE IT Do not use HashMap if you need a guaranteed iteration order; its random seeding means iteration order is non-deterministic. For sorted iteration by key, use BTreeMap instead. If your keys are simple integers and you don't need cryptographic security, a specialized, faster hasher from an external crate might be a better choice.

ONE CANONICAL EXAMPLE A key must implement the Eq and Hash traits, and they must be consistent: if two keys are equal, their hashes must also be equal. The most dangerous footgun is modifying a key while it is in the map in a way that changes its hash or equality (e.g., through a RefCell or unsafe code). This violates the map's core invariants and results in unspecified behavior, which can include panics, incorrect results, or infinite loops.