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

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

Best Practices

1. Use entry API for conditional inserts and updates
2. Pre-allocate capacity when size is known
3. Choose appropriate key types (borrowed vs owned)
4. Consider BTreeMap if ordering is needed
5. Handle missing keys with get or entry instead of direct indexing
6. Use shrink_to_fit after removing many elements
7. 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.