Complete Guide to Rust HashMap

Introduction to HashMap in Rust

HashMap is a collection type that stores key-value pairs, allowing fast insertion, lookup, and deletion based on keys. It's one of the most commonly used data structures in Rust, providing average constant-time complexity for basic operations. HashMaps are part of the standard library's collections module and are implemented using a hash table.

Key Concepts

Key-Value Storage: Each value is associated with a unique key
Hashing: Keys are hashed to determine storage location
Average O(1) Operations: Fast lookup, insertion, and deletion
No Guaranteed Order: Iteration order is arbitrary
Ownership: HashMap owns its keys and values
Type Parameters: HashMap<K, V> where K is key type, V is value type

1. Creating and Initializing HashMaps

Basic Creation

use std::collections::HashMap; fn main() { // Creating an empty HashMap let mut scores: HashMap<String, i32> = HashMap::new(); // Creating with capacity let mut with_capacity: HashMap<String, i32> = HashMap::with_capacity(10); println!("Capacity: {}", with_capacity.capacity()); // From arrays/tuples let teams = vec![ String::from("Blue"), String::from("Yellow"), ]; let initial_scores = vec![10, 50]; let scores: HashMap<_, _> = teams.iter() .zip(initial_scores.iter()) .map(|(k, v)| (k.clone(), *v)) .collect(); println!("Scores from zip: {:?}", scores); // Using from_iter with tuples let data = vec![ (String::from("Red"), 30), (String::from("Green"), 40), (String::from("Blue"), 50), ]; let map: HashMap<_, _> = data.into_iter().collect(); println!("From vec of tuples: {:?}", map); // Using collect with iterator let map: HashMap<_, _> = (1..=5) .map(|i| (format!("key_{}", i), i * 10)) .collect(); println!("From range: {:?}", map); }

From Iterator Patterns

use std::collections::HashMap; fn main() { // From a vector of tuples let pairs = vec![("a", 1), ("b", 2), ("c", 3)]; let map: HashMap<&str, i32> = pairs.into_iter().collect(); println!("From pairs: {:?}", map); // Transforming while collecting let words = vec!["apple", "banana", "cherry", "date"]; let word_lengths: HashMap<&str, usize> = words .into_iter() .map(|word| (word, word.len())) .collect(); println!("Word lengths: {:?}", word_lengths); // Filtering while collecting let numbers = vec![1, 2, 3, 4, 5, 6]; let even_squares: HashMap<i32, i32> = numbers .into_iter() .filter(|&n| n % 2 == 0) .map(|n| (n, n * n)) .collect(); println!("Even squares: {:?}", even_squares); // From a string (counting characters) let text = "hello world hello"; let char_counts: HashMap<char, i32> = text .chars() .filter(|c| !c.is_whitespace()) .fold(HashMap::new(), |mut acc, c| { *acc.entry(c).or_insert(0) += 1; acc }); println!("Character counts: {:?}", char_counts); }

2. Basic Operations

Inserting and Updating

use std::collections::HashMap; fn main() { let mut scores = HashMap::new(); // Inserting values scores.insert(String::from("Blue"), 10); scores.insert(String::from("Yellow"), 50); scores.insert(String::from("Red"), 30); println!("After inserts: {:?}", scores); // Insert returns Option of old value let old_value = scores.insert(String::from("Blue"), 25); println!("Old value for Blue: {:?}", old_value); // Some(10) // Insert if key doesn't exist scores.entry(String::from("Green")).or_insert(40); scores.entry(String::from("Blue")).or_insert(100); // Won't change println!("After or_insert: {:?}", scores); // Update based on existing value let text = "hello world wonderful world"; let mut word_counts = HashMap::new(); for word in text.split_whitespace() { let count = word_counts.entry(word).or_insert(0); *count += 1; } println!("Word counts: {:?}", word_counts); // Complex update let mut map: HashMap<&str, Vec<i32>> = HashMap::new(); map.entry("numbers").or_insert_with(Vec::new).push(1); map.entry("numbers").or_insert_with(Vec::new).push(2); map.entry("numbers").or_insert_with(Vec::new).push(3); println!("Numbers: {:?}", map); }

Accessing Values

use std::collections::HashMap; fn main() { let mut scores = HashMap::new(); scores.insert(String::from("Blue"), 10); scores.insert(String::from("Yellow"), 50); // Using get (returns Option<&V>) let team_name = String::from("Blue"); if let Some(score) = scores.get(&team_name) { println!("Blue score: {}", score); } // Using get with default let score = scores.get(&String::from("Red")).unwrap_or(&0); println!("Red score (default): {}", score); // Direct indexing (panics if key not found) // let score = scores[&String::from("Red")]; // Panics! // Safe access with match match scores.get(&String::from("Yellow")) { Some(score) => println!("Yellow: {}", score), None => println!("Yellow not found"), } // Check if contains key if scores.contains_key(&String::from("Blue")) { println!("Blue exists"); } // Getting multiple values let keys_to_check = vec!["Blue", "Red", "Yellow"]; for key in keys_to_check { match scores.get(&String::from(key)) { Some(score) => println!("{}: {}", key, score), None => println!("{} not found", key), } } }

Removing Elements

use std::collections::HashMap; fn main() { let mut scores = HashMap::new(); scores.insert(String::from("Blue"), 10); scores.insert(String::from("Yellow"), 50); scores.insert(String::from("Red"), 30); scores.insert(String::from("Green"), 40); println!("Before removal: {:?}", scores); // Remove by key (returns Option<V>) let removed = scores.remove(&String::from("Blue")); println!("Removed: {:?}", removed); // Remove entry if it matches a value if let Some((key, value)) = scores.remove_entry(&String::from("Yellow")) { println!("Removed entry: {} => {}", key, value); } // Remove with condition (drain_filter is unstable) let mut to_remove = Vec::new(); for (key, &value) in &scores { if value < 35 { to_remove.push(key.clone()); } } for key in to_remove { scores.remove(&key); } println!("After conditional removal: {:?}", scores); // Clear all entries scores.clear(); println!("After clear: {:?}", scores); println!("Is empty: {}", scores.is_empty()); }

3. Iteration

Basic Iteration

use std::collections::HashMap; fn main() { let mut scores = HashMap::new(); scores.insert("Blue".to_string(), 10); scores.insert("Yellow".to_string(), 50); scores.insert("Red".to_string(), 30); scores.insert("Green".to_string(), 40); // Iterate over key-value pairs println!("All entries:"); for (key, value) in &scores { println!(" {}: {}", key, value); } // Iterate over keys println!("Keys:"); for key in scores.keys() { println!(" {}", key); } // Iterate over values println!("Values:"); for value in scores.values() { println!(" {}", value); } // Mutable iteration over values println!("Doubling all scores:"); for value in scores.values_mut() { *value *= 2; } for (key, value) in &scores { println!(" {}: {}", key, value); } // Consuming iteration (moves ownership) let scores_clone = scores.clone(); for (key, value) in scores_clone { println!("Consumed: {} => {}", key, value); } // scores_clone is no longer valid // Using iterators with adapters let high_scores: Vec<_> = scores .iter() .filter(|(_, &score)| score > 50) .map(|(key, _)| key) .collect(); println!("High score keys: {:?}", high_scores); }

Advanced Iteration Patterns

use std::collections::HashMap; fn main() { let mut scores = HashMap::new(); scores.insert("Blue".to_string(), 10); scores.insert("Yellow".to_string(), 50); scores.insert("Red".to_string(), 30); scores.insert("Green".to_string(), 40); // Finding min/max by value let min_score = scores.iter().min_by_key(|(_, &v)| v); println!("Min score: {:?}", min_score); let max_score = scores.iter().max_by_key(|(_, &v)| v); println!("Max score: {:?}", max_score); // Sum of values let total: i32 = scores.values().sum(); println!("Total scores: {}", total); // Transform values while iterating let doubled: HashMap<_, _> = scores .iter() .map(|(k, v)| (k.clone(), v * 2)) .collect(); println!("Doubled: {:?}", doubled); // Conditional collection let filtered: HashMap<_, _> = scores .into_iter() .filter(|(_, v)| *v > 30) .collect(); println!("Filtered: {:?}", filtered); // Fold over entries let mut map = HashMap::new(); map.insert("a", 1); map.insert("b", 2); map.insert("c", 3); let sum: i32 = map.iter().fold(0, |acc, (_, &v)| acc + v); println!("Sum using fold: {}", sum); // Partition by predicate let mut map = HashMap::new(); map.insert(1, "odd"); map.insert(2, "even"); map.insert(3, "odd"); map.insert(4, "even"); let (odds, evens): (Vec<_>, Vec<_>) = map .into_iter() .partition(|(k, _)| k % 2 == 1); println!("Odd keys: {:?}", odds); println!("Even keys: {:?}", evens); }

4. Entry API

Using Entry for Efficient Operations

use std::collections::hash_map::Entry; use std::collections::HashMap; fn main() { let mut map = HashMap::new(); // Entry pattern - insert if absent match map.entry("key1") { Entry::Vacant(entry) => { entry.insert(42); println!("Inserted new value"); } Entry::Occupied(mut entry) => { *entry.get_mut() += 1; println!("Updated existing value"); } } // More concise with or_insert map.entry("key2").or_insert(100); map.entry("key2").or_insert(200); // Won't change println!("Map: {:?}", map); // or_insert_with for lazy initialization let expensive_computation = || { println!("Performing expensive computation..."); 42 * 100 }; map.entry("key3").or_insert_with(expensive_computation); map.entry("key3").or_insert_with(expensive_computation); // Won't call // or_insert_with_key (uses the key) map.entry("key4").or_insert_with_key(|k| k.len()); println!("After lazy init: {:?}", map); // Modify in place let text = "hello world hello universe hello"; let mut word_counts = HashMap::new(); for word in text.split_whitespace() { *word_counts.entry(word).or_insert(0) += 1; } println!("Word counts: {:?}", word_counts); // Complex modifications let mut map: HashMap<&str, Vec<i32>> = HashMap::new(); map.entry("numbers") .or_insert_with(Vec::new) .push(1); map.entry("numbers") .and_modify(|v| v.push(2)) .or_insert_with(|| vec![2]); map.entry("letters") .and_modify(|v| v.push(3)) .or_insert_with(|| vec![1, 2, 3]); println!("Modified map: {:?}", map); // Entry with chaining let mut map = HashMap::new(); map.entry("count") .and_modify(|c| *c += 1) .or_insert(1); map.entry("count") .and_modify(|c| *c += 1) .or_insert(1); println!("Count: {}", map["count"]); // 2 }

Advanced Entry Patterns

use std::collections::HashMap; fn main() { // Grouping items by key let items = vec![ ("fruit", "apple"), ("fruit", "banana"), ("fruit", "orange"), ("vegetable", "carrot"), ("vegetable", "broccoli"), ]; let mut grouped: HashMap<&str, Vec<&str>> = HashMap::new(); for (category, item) in items { grouped.entry(category) .or_insert_with(Vec::new) .push(item); } println!("Grouped items: {:?}", grouped); // Counting occurrences with enum enum Event { Click, KeyPress(char), Resize { width: u32, height: u32 }, } let events = vec![ Event::Click, Event::KeyPress('a'), Event::Resize { width: 100, height: 100 }, Event::Click, Event::KeyPress('b'), Event::Click, ]; let mut event_counts: HashMap<&str, u32> = HashMap::new(); for event in &events { let key = match event { Event::Click => "click", Event::KeyPress(_) => "keypress", Event::Resize { .. } => "resize", }; *event_counts.entry(key).or_insert(0) += 1; } println!("Event counts: {:?}", event_counts); // Cache pattern struct ExpensiveComputation; impl ExpensiveComputation { fn compute(&self, input: &str) -> usize { println!("Computing for: {}", input); input.len() } } let mut cache: HashMap<String, usize> = HashMap::new(); let computer = ExpensiveComputation; for input in &["hello", "world", "hello", "rust", "world"] { let result = cache.entry((*input).to_string()) .or_insert_with(|| computer.compute(input)); println!("Result for {}: {}", input, result); } }

5. Performance and Capacity

Capacity Management

use std::collections::HashMap; fn main() { // Creating with specific capacity let mut map: HashMap<i32, i32> = HashMap::with_capacity(1000); println!("Initial capacity: {}", map.capacity()); // Adding elements for i in 0..100 { map.insert(i, i * 10); } println!("After 100 inserts, capacity: {}", map.capacity()); // Shrink to fit map.shrink_to_fit(); println!("After shrink_to_fit: {}", map.capacity()); // Reserve additional capacity map.reserve(200); println!("After reserving 200: {}", map.capacity()); // Try reserve (may fail) match map.try_reserve(1000) { Ok(()) => println!("Successfully reserved more space"), Err(e) => println!("Failed to reserve: {}", e), } // Check current metrics println!("Length: {}", map.len()); println!("Capacity: {}", map.capacity()); println!("Load factor: {:.2}", map.len() as f64 / map.capacity() as f64); // Clear and reuse capacity map.clear(); println!("After clear, capacity: {}", map.capacity()); // Capacity retained map.shrink_to_fit(); println!("After shrink_to_fit: {}", map.capacity()); }

Performance Benchmarking

use std::collections::HashMap; use std::time::Instant; fn main() { // Compare insertion performance with different capacities let sizes = [1000, 10000, 100000]; for &size in &sizes { // Without pre-allocation let start = Instant::now(); let mut map = HashMap::new(); for i in 0..size { map.insert(i, i * 2); } let time_without = start.elapsed(); // With pre-allocation let start = Instant::now(); let mut map = HashMap::with_capacity(size); for i in 0..size { map.insert(i, i * 2); } let time_with = start.elapsed(); println!("Size {}: Without={:?}, With={:?} (Ratio: {:.2})", size, time_without, time_with, time_without.as_secs_f64() / time_with.as_secs_f64()); } // Lookup performance let size = 100000; let mut map = HashMap::with_capacity(size); for i in 0..size { map.insert(i, i * 2); } let start = Instant::now(); for i in 0..size { let _ = map.get(&i); } let lookup_time = start.elapsed(); println!("Lookup time for {} items: {:?}", size, lookup_time); // Compare hash function performance use std::collections::hash_map::RandomState; use std::hash::{BuildHasher, Hasher}; let mut map = HashMap::with_capacity_and_hasher(size, RandomState::new()); let start = Instant::now(); for i in 0..size { map.insert(i, i * 2); } let time_custom = start.elapsed(); println!("Custom hasher time: {:?}", time_custom); }

6. Custom Key Types

Using Custom Types as Keys

use std::collections::HashMap; use std::hash::{Hash, Hasher}; #[derive(Debug, Eq, PartialEq, Hash)] struct Person { name: String, age: u32, } impl Person { fn new(name: &str, age: u32) -> Self { Person { name: name.to_string(), age, } } } #[derive(Debug)] struct Record { value: i32, timestamp: u64, } // Custom implementation of Hash for more control struct CaseInsensitiveString(String); impl PartialEq for CaseInsensitiveString { fn eq(&self, other: &Self) -> bool { self.0.to_lowercase() == other.0.to_lowercase() } } impl Eq for CaseInsensitiveString {} impl Hash for CaseInsensitiveString { fn hash<H: Hasher>(&self, state: &mut H) { self.0.to_lowercase().hash(state); } } fn main() { // Using custom struct as key let mut person_records: HashMap<Person, Record> = HashMap::new(); person_records.insert( Person::new("Alice", 30), Record { value: 100, timestamp: 1234567890 }, ); person_records.insert( Person::new("Bob", 25), Record { value: 200, timestamp: 1234567891 }, ); // Lookup by Person let alice = Person::new("Alice", 30); if let Some(record) = person_records.get(&alice) { println!("Alice's record: {:?}", record); } // Case-insensitive keys let mut map: HashMap<CaseInsensitiveString, i32> = HashMap::new(); map.insert(CaseInsensitiveString("Hello".to_string()), 1); map.insert(CaseInsensitiveString("WORLD".to_string()), 2); println!("Get 'hello': {:?}", map.get(&CaseInsensitiveString("hello".to_string()))); println!("Get 'world': {:?}", map.get(&CaseInsensitiveString("world".to_string()))); // Tuple as key let mut coordinate_map: HashMap<(i32, i32), String> = HashMap::new(); coordinate_map.insert((0, 0), "origin".to_string()); coordinate_map.insert((1, 0), "east".to_string()); coordinate_map.insert((0, 1), "north".to_string()); println!("At (1,0): {:?}", coordinate_map.get(&(1, 0))); // Array as key let mut array_map: HashMap<[i32; 2], String> = HashMap::new(); array_map.insert([0, 0], "origin".to_string()); array_map.insert([1, 0], "right".to_string()); println!("Array key: {:?}", array_map.get(&[0, 0])); }

7. Nested HashMaps

Multi-level Maps

use std::collections::HashMap; fn main() { // HashMap of HashMaps let mut users: HashMap<String, HashMap<String, i32>> = HashMap::new(); // Adding user Alice with her scores let mut alice_scores = HashMap::new(); alice_scores.insert("math".to_string(), 95); alice_scores.insert("physics".to_string(), 87); users.insert("alice".to_string(), alice_scores); // Adding user Bob with his scores let mut bob_scores = HashMap::new(); bob_scores.insert("math".to_string(), 78); bob_scores.insert("chemistry".to_string(), 92); users.insert("bob".to_string(), bob_scores); // Access nested values if let Some(scores) = users.get("alice") { if let Some(math_score) = scores.get("math") { println!("Alice's math score: {}", math_score); } } // Update nested value using entry users.entry("charlie".to_string()) .or_insert_with(HashMap::new) .insert("physics".to_string(), 88); // Iterate over nested structure for (user, scores) in &users { println!("User: {}", user); for (subject, score) in scores { println!(" {}: {}", subject, score); } } // Count occurrences with nested structure let data = vec![ ("fruit", "apple"), ("fruit", "banana"), ("fruit", "apple"), ("vegetable", "carrot"), ("vegetable", "broccoli"), ("fruit", "banana"), ]; let mut counts: HashMap<&str, HashMap<&str, i32>> = HashMap::new(); for (category, item) in data { *counts .entry(category) .or_insert_with(HashMap::new) .entry(item) .or_insert(0) += 1; } println!("Counts: {:?}", counts); }

8. Serialization and Deserialization

Using serde with HashMap

use serde::{Serialize, Deserialize}; use serde_json; use std::collections::HashMap; #[derive(Debug, Serialize, Deserialize)] struct Config { settings: HashMap<String, String>, enabled: bool, version: u32, } fn main() -> Result<(), Box<dyn std::error::Error>> { // Create a HashMap let mut settings = HashMap::new(); settings.insert("host".to_string(), "localhost".to_string()); settings.insert("port".to_string(), "8080".to_string()); settings.insert("timeout".to_string(), "30".to_string()); let config = Config { settings, enabled: true, version: 1, }; // Serialize to JSON let json = serde_json::to_string_pretty(&config)?; println!("Serialized config:\n{}", json); // Deserialize from JSON let deserialized: Config = serde_json::from_str(&json)?; println!("Deserialized: {:?}", deserialized); // HashMap-specific serialization let mut map = HashMap::new(); map.insert("key1", "value1"); map.insert("key2", "value2"); map.insert("key3", "value3"); let json_map = serde_json::to_string(&map)?; println!("Map as JSON: {}", json_map); // Parse JSON into HashMap let json_data = r#"{"name":"Alice","age":"30","city":"New York"}"#; let parsed: HashMap<String, String> = serde_json::from_str(json_data)?; println!("Parsed JSON: {:?}", parsed); Ok(()) }

9. Common Patterns and Use Cases

Caching and Memoization

use std::collections::HashMap; use std::time::{Duration, Instant}; struct Cache<T> { data: HashMap<String, (T, Instant)>, ttl: Duration, } impl<T: Clone> Cache<T> { fn new(ttl: Duration) -> Self { Cache { data: HashMap::new(), ttl, } } fn get(&self, key: &str) -> Option<&T> { self.data.get(key).and_then(|(value, time)| { if time.elapsed() < self.ttl { Some(value) } else { None } }) } fn insert(&mut self, key: String, value: T) { self.data.insert(key, (value, Instant::now())); } fn cleanup(&mut self) { let now = Instant::now(); self.data.retain(|_, (_, time)| now.duration_since(*time) < self.ttl); } } fn main() { let mut cache: Cache<String> = Cache::new(Duration::from_secs(5)); cache.insert("user_1".to_string(), "Alice".to_string()); cache.insert("user_2".to_string(), "Bob".to_string()); println!("Cached user_1: {:?}", cache.get("user_1")); println!("Cached user_3: {:?}", cache.get("user_3")); std::thread::sleep(Duration::from_secs(6)); cache.cleanup(); println!("After TTL, user_1: {:?}", cache.get("user_1")); }

Index and Counter

use std::collections::HashMap; struct Indexer { word_to_id: HashMap<String, usize>, id_to_word: HashMap<usize, String>, next_id: usize, } impl Indexer { fn new() -> Self { Indexer { word_to_id: HashMap::new(), id_to_word: HashMap::new(), next_id: 0, } } fn get_or_create_id(&mut self, word: &str) -> usize { if let Some(&id) = self.word_to_id.get(word) { id } else { let id = self.next_id; self.word_to_id.insert(word.to_string(), id); self.id_to_word.insert(id, word.to_string()); self.next_id += 1; id } } fn get_word(&self, id: usize) -> Option<&String> { self.id_to_word.get(&id) } fn get_id(&self, word: &str) -> Option<&usize> { self.word_to_id.get(word) } fn size(&self) -> usize { self.word_to_id.len() } } fn main() { let mut indexer = Indexer::new(); let words = vec!["hello", "world", "hello", "rust", "world", "programming"]; for word in words { let id = indexer.get_or_create_id(word); println!("Word '{}' has id {}", word, id); } println!("\nReverse lookup:"); for id in 0..indexer.size() { if let Some(word) = indexer.get_word(id) { println!("ID {}: '{}'", id, word); } } }

Frequency Counter

use std::collections::HashMap; use std::hash::Hash; struct FrequencyCounter<T> { counts: HashMap<T, usize>, } impl<T: Eq + Hash> FrequencyCounter<T> { fn new() -> Self { FrequencyCounter { counts: HashMap::new(), } } fn add(&mut self, item: T) { *self.counts.entry(item).or_insert(0) += 1; } fn add_many(&mut self, items: Vec<T>) { for item in items { self.add(item); } } fn frequency(&self, item: &T) -> usize { self.counts.get(item).copied().unwrap_or(0) } fn most_frequent(&self) -> Option<(&T, &usize)> { self.counts.iter().max_by_key(|(_, &count)| count) } fn least_frequent(&self) -> Option<(&T, &usize)> { self.counts.iter().min_by_key(|(_, &count)| count) } fn total_count(&self) -> usize { self.counts.values().sum() } fn unique_count(&self) -> usize { self.counts.len() } fn frequencies(&self) -> &HashMap<T, usize> { &self.counts } fn clear(&mut self) { self.counts.clear(); } } fn main() { let mut counter = FrequencyCounter::new(); let data = vec![ "apple", "banana", "apple", "orange", "banana", "apple", "grape", "orange", ]; counter.add_many(data); println!("Frequency of 'apple': {}", counter.frequency(&"apple")); println!("Frequency of 'banana': {}", counter.frequency(&"banana")); println!("Most frequent: {:?}", counter.most_frequent()); println!("Least frequent: {:?}", counter.least_frequent()); println!("Total count: {}", counter.total_count()); println!("Unique items: {}", counter.unique_count()); println!("All frequencies: {:?}", counter.frequencies()); }

Graph Representation

use std::collections::{HashMap, HashSet, VecDeque}; struct Graph<T> { adjacency_list: HashMap<T, HashSet<T>>, } impl<T: Eq + Hash + Clone> Graph<T> { fn new() -> Self { Graph { adjacency_list: HashMap::new(), } } fn add_vertex(&mut self, vertex: T) { self.adjacency_list.entry(vertex).or_insert_with(HashSet::new); } fn add_edge(&mut self, from: T, to: T) { self.adjacency_list .entry(from.clone()) .or_insert_with(HashSet::new) .insert(to.clone()); self.adjacency_list.entry(to).or_insert_with(HashSet::new); } fn add_bidirectional_edge(&mut self, a: T, b: T) { self.add_edge(a.clone(), b.clone()); self.add_edge(b, a); } fn neighbors(&self, vertex: &T) -> Option<&HashSet<T>> { self.adjacency_list.get(vertex) } fn bfs(&self, start: T) -> Vec<T> { let mut visited = HashSet::new(); let mut queue = VecDeque::new(); let mut result = Vec::new(); visited.insert(start.clone()); queue.push_back(start); while let Some(vertex) = queue.pop_front() { result.push(vertex.clone()); if let Some(neighbors) = self.adjacency_list.get(&vertex) { for neighbor in neighbors { if !visited.contains(neighbor) { visited.insert(neighbor.clone()); queue.push_back(neighbor.clone()); } } } } result } fn has_cycle(&self) -> bool { let mut visited = HashSet::new(); let mut recursion_stack = HashSet::new(); for vertex in self.adjacency_list.keys() { if !visited.contains(vertex) { if self.has_cycle_helper(vertex, &mut visited, &mut recursion_stack) { return true; } } } false } fn has_cycle_helper(&self, vertex: &T, visited: &mut HashSet<T>, stack: &mut HashSet<T>) -> bool { visited.insert(vertex.clone()); stack.insert(vertex.clone()); if let Some(neighbors) = self.adjacency_list.get(vertex) { for neighbor in neighbors { if !visited.contains(neighbor) { if self.has_cycle_helper(neighbor, visited, stack) { return true; } } else if stack.contains(neighbor) { return true; } } } stack.remove(vertex); false } fn shortest_path(&self, start: T, end: T) -> Option<Vec<T>> { let mut visited = HashSet::new(); let mut queue = VecDeque::new(); let mut parent = HashMap::new(); visited.insert(start.clone()); queue.push_back(start.clone()); while let Some(vertex) = queue.pop_front() { if vertex == end { return Some(self.reconstruct_path(parent, start, end)); } if let Some(neighbors) = self.adjacency_list.get(&vertex) { for neighbor in neighbors { if !visited.contains(neighbor) { visited.insert(neighbor.clone()); parent.insert(neighbor.clone(), vertex.clone()); queue.push_back(neighbor.clone()); } } } } None } fn reconstruct_path(&self, parent: HashMap<T, T>, start: T, end: T) -> Vec<T> { let mut path = Vec::new(); let mut current = end; path.push(current.clone()); while current != start { if let Some(prev) = parent.get(&current) { path.push(prev.clone()); current = prev.clone(); } else { break; } } path.reverse(); path } } fn main() { let mut graph = Graph::new(); graph.add_bidirectional_edge(1, 2); graph.add_bidirectional_edge(1, 3); graph.add_bidirectional_edge(2, 4); graph.add_bidirectional_edge(3, 4); graph.add_bidirectional_edge(4, 5); println!("BFS from 1: {:?}", graph.bfs(1)); println!("Has cycle: {}", graph.has_cycle()); if let Some(path) = graph.shortest_path(1, 5) { println!("Shortest path: {:?}", path); } // Directed graph with cycle let mut directed = Graph::new(); directed.add_edge(1, 2); directed.add_edge(2, 3); directed.add_edge(3, 1); println!("Directed has cycle: {}", directed.has_cycle()); }

10. Concurrency with HashMap

Thread-safe HashMap

use std::collections::HashMap; use std::sync::{Arc, Mutex}; use std::thread; fn main() { // Shared HashMap with Mutex let shared_map = Arc::new(Mutex::new(HashMap::new())); let mut handles = vec![]; for i in 0..10 { let map_clone = shared_map.clone(); handles.push(thread::spawn(move || { let mut map = map_clone.lock().unwrap(); map.insert(i, format!("Value {}", i)); })); } for handle in handles { handle.join().unwrap(); } println!("Final map: {:?}", shared_map.lock().unwrap()); // Multiple readers with RwLock use std::sync::RwLock; let shared_map = Arc::new(RwLock::new(HashMap::new())); // Writers let mut write_handles = vec![]; for i in 0..5 { let map_clone = shared_map.clone(); write_handles.push(thread::spawn(move || { let mut map = map_clone.write().unwrap(); map.insert(i, i * 10); })); } // Readers let mut read_handles = vec![]; for _ in 0..5 { let map_clone = shared_map.clone(); read_handles.push(thread::spawn(move || { let map = map_clone.read().unwrap(); println!("Map size: {}", map.len()); })); } for handle in write_handles { handle.join().unwrap(); } for handle in read_handles { handle.join().unwrap(); } // Concurrent HashMap with DashMap (external crate) // use dashmap::DashMap; // let map = DashMap::new(); // rayon::scope(|s| { // for i in 0..1000 { // s.spawn(|_| { // map.insert(i, i * 2); // }); // } // }); }

11. Advanced HashMap Features

Custom Hashers

use std::collections::HashMap; use std::hash::{BuildHasherDefault, Hasher}; // Simple identity hasher (for integers only - not safe for real use) struct IdentityHasher { value: u64, } impl Hasher for IdentityHasher { fn finish(&self) -> u64 { self.value } fn write(&mut self, bytes: &[u8]) { // Simplified for example - not correct for general use if bytes.len() == 8 { self.value = u64::from_le_bytes(bytes.try_into().unwrap()); } } } type IdentityBuildHasher = BuildHasherDefault<IdentityHasher>; // FNV hasher (often faster for small keys) use fnv::FnvHashMap; // External crate fn main() { // Using custom hasher let mut map: HashMap<i32, String, IdentityBuildHasher> = HashMap::with_hasher(IdentityBuildHasher::default()); map.insert(1, "one".to_string()); map.insert(2, "two".to_string()); println!("Custom hasher map: {:?}", map); // Using FNV (faster for small keys) let mut fnv_map: HashMap<i32, String> = HashMap::default(); fnv_map.insert(1, "one".to_string()); fnv_map.insert(2, "two".to_string()); // Alternative using fnv crate // use fnv::FnvHashMap; // let mut map = FnvHashMap::default(); // map.insert(1, "one"); }

Performance Optimization Tips

use std::collections::HashMap; fn main() { // 1. Pre-allocate capacity when size is known let expected_size = 1000; let mut map = HashMap::with_capacity(expected_size); // 2. Use entry API for conditional inserts/updates let mut map = HashMap::new(); // Efficient - single lookup *map.entry("key").or_insert(0) += 1; // Inefficient - two lookups // if !map.contains_key("key") { // map.insert("key", 0); // } // *map.get_mut("key").unwrap() += 1; // 3. Choose appropriate key type // &str vs String - &str can't be owned by HashMap let mut map1: HashMap<&str, i32> = HashMap::new(); map1.insert("key", 1); // Key is borrowed let mut map2: HashMap<String, i32> = HashMap::new(); map2.insert("key".to_string(), 1); // Key is owned // 4. Consider using `BTreeMap` if ordering needed // BTreeMap has slower insertion but maintains order // 5. Use `shrink_to_fit` to free memory let mut map = HashMap::with_capacity(1000); for i in 0..100 { map.insert(i, i); } map.shrink_to_fit(); // 6. Clone vs retain let mut map = HashMap::new(); for i in 0..100 { map.insert(i, i * 10); } // Filter and create new let filtered: HashMap<_, _> = map .into_iter() .filter(|(k, _)| k % 2 == 0) .collect(); println!("Filtered: {:?}", filtered); }

Conclusion

HashMap is one of the most versatile and commonly used data structures in Rust:

Key Takeaways

Fast Operations: Average O(1) for insert, get, remove
Flexible Keys: Any type implementing Eq + Hash
Entry API: Efficient conditional operations
Ownership: HashMap owns its keys and values
No Order: Iteration order is not guaranteed
Customizable: Can use custom hashers for specific needs

Best Practices

Use entry API for conditional inserts and updates
Pre-allocate capacity when size is known
Choose appropriate key types (borrowed vs owned)
Consider BTreeMap if ordering is needed
Handle missing keys with get or entry instead of direct indexing
Use shrink_to_fit after removing many elements
Consider performance implications of different hashers

Common Use Cases

Caching and memoization
Counting frequencies
Building indexes
Representing graphs
Configuration storage
Lookup tables
Grouping data

HashMap is an essential tool in Rust programming, providing fast and flexible key-value storage with strong type safety guarantees.