> ## Documentation Index > Fetch the complete documentation index at: https://docs.syntblaze.com/llms.txt > Use this file to discover all available pages before exploring further. # Rust HashMap A `HashMap` in Rust is a dynamically sized, heap-allocated collection that stores key-value pairs, providing average $O(1)$ time complexity for lookups, insertions, and deletions. Under the hood, Rust's standard library implements a **SwissTable**—an open-addressing hash table utilizing quadratic probing (specifically a triangular probing sequence) and SIMD-accelerated metadata lookups (ported from Google's Abseil C++ library). ## Trait Requirements For a type `K` to be used as a key in a `HashMap`, it must implement two specific traits from the standard library: 1. **`std::cmp::Eq`**: Ensures strict equivalence relations. This is required to resolve hash collisions. Because floating-point types (`f32`, `f64`) possess `NaN` values that do not equal themselves, they only implement `PartialEq`, not `Eq`, and cannot be used directly as keys. 2. **`std::hash::Hash`**: Allows the type to feed its internal state into a `Hasher` to compute a deterministic hash value. ## Default Hashing Algorithm By default, `HashMap` utilizes **SipHash 1-3**. This algorithm is cryptographically resistant to HashDoS (Denial of Service) attacks, ensuring that malicious actors cannot intentionally trigger worst-case $O(n)$ collision performance. Because SipHash prioritizes security over raw throughput, developers often override the default `BuildHasher` with faster, non-cryptographic algorithms (like `ahash` or `FxHash`) when operating on trusted keys. ## Initialization and Memory Allocation A `HashMap` does not allocate heap memory until the first element is inserted unless explicitly instructed. ```rust theme={"dark"} use std::collections::HashMap; // Zero-allocation initialization. Explicit type annotations satisfy the compiler. let mut map: HashMap = HashMap::new(); // Pre-allocating memory for a known lower bound to prevent reallocation overhead. let mut preallocated_map: HashMap<&str, i32> = HashMap::with_capacity(100); ``` ## Ownership and Move Semantics `HashMap` takes ownership of the keys and values inserted into it. If types do not implement the `Copy` trait, they are moved into the map, rendering the original variables inaccessible. ```rust theme={"dark"} let key = String::from("k1"); let val = String::from("v1"); let mut map: HashMap = HashMap::new(); map.insert(key, val); // `key` and `val` are moved here. // println!("{}", key); // COMPILER ERROR: value borrowed here after move ``` To store references, both the key and value must have lifetimes that outlive the `HashMap`: ```rust theme={"dark"} let key = String::from("k1"); let mut map: HashMap<&str, i32> = HashMap::new(); // Storing a string slice (reference) instead of an owned String map.insert(&key, 42); ``` ## Retrieval and Mutation Because a key might not exist, retrieval methods return an `Option` enum containing a reference to the value, preventing null pointer dereferencing. When the key type `K` is a reference (e.g., `&str`), the `get` method requires a reference to that key type (`&&str`) due to how the `Borrow` trait is implemented. ```rust theme={"dark"} // Returns Option<&V> if let Some(value) = map.get(&"k1") { println!("Found: {}", value); } // Returns Option<&mut V> for in-place mutation if let Some(value_mut) = map.get_mut(&"k1") { *value_mut += 10; } ``` ## The Entry API Rust provides the `Entry` API to handle conditional insertion and mutation without requiring multiple hash lookups. It returns an `enum` (`Occupied` or `Vacant`) representing the state of the bucket. Unlike `get`, the `entry` method takes the key by value. ```rust theme={"dark"} let mut map: HashMap<&str, i32> = HashMap::new(); // Inserts 100 if "k1" does not exist. Returns a mutable reference to the value. map.entry("k1").or_insert(100); // In-place mutation using a closure if the key exists, otherwise inserts a default. map.entry("k1") .and_modify(|e| *e += 1) .or_insert(1); ```
Tired of Poor Rust Skills? Fix That With Deep Grasping! Learn More