Why Hash Map Exists and What Problem It Solves in DSA Rust - Why This Pattern

Mental Model

A hash map helps us find things quickly by using a special code to jump right to the spot instead of searching one by one.

Analogy: Imagine a huge library where books are arranged by a secret code on their cover. Instead of checking every shelf, you use the code to go directly to the right shelf and find your book fast.

Array of buckets:
[0] -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Key "apple" hashed to bucket 2:
[0] -> null
[1] -> null
[2] -> apple -> null
[3] -> null
[4] -> null

Dry Run Walkthrough

Input: Insert keys "apple", "banana", "grape" with values 5, 3, 7 into an empty hash map

Goal: Show how hash map stores and finds keys quickly without searching all entries

Step 1: Hash key "apple" to bucket 2 and insert (apple, 5)

[0] -> null
[1] -> null
[2] -> (apple,5) -> null
[3] -> null
[4] -> null

Why: We use the hash code to jump directly to bucket 2 to store apple

Step 2: Hash key "banana" to bucket 4 and insert (banana, 3)

[0] -> null
[1] -> null
[2] -> (apple,5) -> null
[3] -> null
[4] -> (banana,3) -> null

Why: Hash code sends banana to bucket 4, so we insert it there

Step 3: Hash key "grape" to bucket 2 and insert (grape, 7) after apple

[0] -> null
[1] -> null
[2] -> (apple,5) -> (grape,7) -> null
[3] -> null
[4] -> (banana,3) -> null

Why: Collision happens at bucket 2, so we chain grape after apple

Step 4: Find value for key "grape" by hashing to bucket 2 and searching chain

[0] -> null
[1] -> null
[2] -> (apple,5) -> (grape,7) -> null
[3] -> null
[4] -> (banana,3) -> null

Why: We jump to bucket 2 and check linked entries until we find grape

Result:

[0] -> null
[1] -> null
[2] -> (apple,5) -> (grape,7) -> null
[3] -> null
[4] -> (banana,3) -> null
Value for "grape" is 7

Annotated Code

DSA Rust

use std::collections::LinkedList;

struct Entry {
    key: String,
    value: i32,
}

struct HashMap {
    buckets: Vec<LinkedList<Entry>>,
    size: usize,
}

impl HashMap {
    fn new(size: usize) -> Self {
        let mut buckets = Vec::with_capacity(size);
        for _ in 0..size {
            buckets.push(LinkedList::new());
        }
        HashMap { buckets, size }
    }

    fn hash(&self, key: &str) -> usize {
        let mut hash = 0;
        for b in key.bytes() {
            hash = (hash * 31 + b as usize) % self.size;
        }
        hash
    }

    fn insert(&mut self, key: String, value: i32) {
        let index = self.hash(&key); // compute bucket index
        for entry in self.buckets[index].iter_mut() {
            if entry.key == key {
                entry.value = value; // update if key exists
                return;
            }
        }
        self.buckets[index].push_back(Entry { key, value }); // add new entry
    }

    fn get(&self, key: &str) -> Option<i32> {
        let index = self.hash(key); // compute bucket index
        for entry in self.buckets[index].iter() {
            if entry.key == key {
                return Some(entry.value); // found key
            }
        }
        None // key not found
    }

    fn print(&self) {
        for (i, bucket) in self.buckets.iter().enumerate() {
            print!("[{}] -> ", i);
            for entry in bucket {
                print!("({},{}) -> ", entry.key, entry.value);
            }
            println!("null");
        }
    }
}

fn main() {
    let mut map = HashMap::new(5);
    map.insert("apple".to_string(), 5);
    map.insert("banana".to_string(), 3);
    map.insert("grape".to_string(), 7);
    map.print();
    if let Some(val) = map.get("grape") {
        println!("Value for \"grape\" is {}", val);
    } else {
        println!("Key not found");
    }
}

let index = self.hash(&key); // compute bucket index

compute bucket index using hash function

for entry in self.buckets[index].iter_mut() { if entry.key == key { entry.value = value; return; } }

check if key exists in bucket to update value

self.buckets[index].push_back(Entry { key, value }); // add new entry

insert new key-value pair at bucket end

for entry in self.buckets[index].iter() { if entry.key == key { return Some(entry.value); } }

search bucket chain for key to get value

Output

[0] -> null

[1] -> null

[2] -> (apple,5) -> (grape,7) -> null

[3] -> null

[4] -> (banana,3) -> null

Value for "grape" is 7

Complexity Analysis

Time: O(1) average because hashing jumps directly to bucket; worst O(n) if many collisions chain in one bucket

Space: O(n) because we store all entries in buckets and linked lists

vs Alternative: Compared to array or list search O(n), hash map reduces lookup to near O(1) by using hashing and buckets

Edge Cases

Empty hash map

Get returns None because no keys exist

DSA Rust

for entry in self.buckets[index].iter() { if entry.key == key { return Some(entry.value); } }

Insert duplicate key

Value is updated instead of adding duplicate entry

DSA Rust

for entry in self.buckets[index].iter_mut() { if entry.key == key { entry.value = value; return; } }

Collision in bucket

Multiple entries chained in linked list at same bucket

DSA Rust

self.buckets[index].push_back(Entry { key, value });

When to Use This Pattern

When you need very fast lookup, insert, or delete by key and want to avoid searching all items, reach for hash map because it uses hashing to jump directly to data.

Common Mistakes

Mistake: Not handling collisions, so new keys overwrite existing ones in same bucket
Fix: Use chaining (linked list) or open addressing to store multiple entries per bucket

Mistake: Not updating value when inserting duplicate key
Fix: Check existing keys in bucket and update value instead of adding new entry

Summary

Hash map stores key-value pairs for very fast access using a hash function to find the right bucket.

Use hash maps when you want quick lookup, insertion, or deletion by key without scanning all data.

The key insight is hashing turns a key into a bucket index, letting you jump directly to where data lives.

Practice

1. Why do we use a HashMap in Rust instead of a simple list or array?

easy

A. To save memory by compressing data

B. To store values in a sorted order automatically

C. To quickly find values by keys without searching the entire collection

D. To allow duplicate keys with different values

Solution

1. Step 1: Understand the problem with lists/arrays

   Lists require checking each item one by one to find a value, which is slow for large data.

2. Step 2: How HashMap solves this

   HashMap uses keys to jump directly to the value, making lookup very fast.

3. Final Answer:

   To quickly find values by keys without searching the entire collection -> Option C

4. Quick Check:

   Fast key-based lookup = C [OK]

Hint: HashMap = fast key lookup, not ordered or duplicates [OK]

Common Mistakes:

• Thinking HashMap sorts data automatically
• Believing HashMap compresses data
• Assuming HashMap allows duplicate keys

2. Which of the following is the correct way to create an empty HashMap in Rust?

easy

A. let map = HashMap::new();

B. let map = HashMap();

C. let map = new HashMap();

D. let map = HashMap[];

Solution

1. Step 1: Recall Rust syntax for creating HashMap

   Rust uses ::new() method to create an empty HashMap.

2. Step 2: Check each option

   Only HashMap::new() is valid syntax; others are incorrect.

3. Final Answer:

   let map = HashMap::new(); -> Option A

4. Quick Check:

   Correct Rust HashMap creation = B [OK]

Hint: Use HashMap::new() to create empty map in Rust [OK]

Common Mistakes:

• Using parentheses instead of ::new()
• Trying to use new keyword like other languages
• Using square brackets for initialization

3. What will be the output of this Rust code?

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert("apple", 3);
    map.insert("banana", 2);
    map.insert("apple", 5);
    println!("{:?}", map.get("apple"));
}

medium

A. Some(3)

B. Compilation error

C. None

D. Some(5)

Solution

1. Step 1: Understand insert behavior in HashMap

   Inserting a key that already exists updates its value to the new one.

2. Step 2: Trace the insertions and get

   "apple" first gets 3, then updated to 5. So, map.get("apple") returns Some(5).

3. Final Answer:

   Some(5) -> Option D

4. Quick Check:

   Updated value returned = D [OK]

Hint: Inserting same key updates value, get returns latest [OK]

Common Mistakes:

• Thinking insert adds duplicate keys
• Expecting original value after update
• Confusing None with Some

4. Identify the error in this Rust code using HashMap:

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert("key1", 10);
    let value = map["key2"];
    println!("{}", value);
}

medium

A. HashMap::new() is not the correct way to create a map

B. Using square brackets to access a non-existent key causes panic

C. Cannot insert values into a mutable HashMap

D. Missing semicolon after insert statement

Solution

1. Step 1: Check how map access works

   Using square brackets with a key that does not exist causes the program to panic at runtime.

2. Step 2: Identify the error in code

   Accessing "key2" which was never inserted triggers panic, causing runtime error.

3. Final Answer:

   Using square brackets to access a non-existent key causes panic -> Option B

4. Quick Check:

   Non-existent key access panics = A [OK]

Hint: Square brackets panic if key missing; use get() for safe access [OK]

Common Mistakes:

• Thinking HashMap::new() is wrong
• Believing insert needs immutable map
• Ignoring runtime panic on missing key

5. You want to count how many times each word appears in a list using a HashMap in Rust. Which approach correctly solves this problem?

hard

A. Use entry() method to update count or insert 1 if missing

B. Insert each word with value 1, then insert again with value 1 for duplicates

C. Store words in a vector and count manually later

D. Use a HashMap but clear it after each insertion

Solution

1. Step 1: Understand counting with HashMap

   We need to increase count if word exists, or add with count 1 if new.

2. Step 2: Use entry() API for efficient update

   The entry() method allows checking and updating count in one step safely.

3. Final Answer:

   Use entry() method to update count or insert 1 if missing -> Option A

4. Quick Check:

   Counting words with entry() = A [OK]

Hint: Use entry().or_insert(0) to count frequencies easily [OK]

Common Mistakes:

• Inserting 1 repeatedly without updating count
• Using vector instead of HashMap for counting
• Clearing map after each insert