HashMap Implementation from Scratch in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this Rust HashMap insertion code?

Consider a simple HashMap implemented with separate chaining. After inserting keys 1, 2, and 3 with values 'a', 'b', and 'c', what is the printed state of the map?

DSA Rust

let mut map = std::collections::HashMap::new();
map.insert(1, 'a');
map.insert(2, 'b');
map.insert(3, 'c');
println!("{:?}", map);

A Compilation error due to missing type annotations

B {"3": "c", "2": "b", "1": "a"}

C {"1": "a", "2": "b", "3": "c"}

D {"1": "a", "3": "c"}

💡 Hint

Think about how insertion order affects the printed output in Rust's HashMap debug format.

Rust's HashMap does not guarantee order, but the debug print shows all inserted key-value pairs. Since all keys 1, 2, and 3 are inserted, all appear in the output. Option C shows all pairs correctly.

🧠 Conceptual

intermediate

Which collision resolution method is used in this HashMap implementation?

In a HashMap implemented from scratch using an array of buckets where each bucket holds a linked list of entries, what collision resolution technique is being used?

A Separate chaining with linked lists

B Cuckoo hashing

C Double hashing

D Open addressing with linear probing

💡 Hint

Think about how collisions are handled when multiple keys hash to the same bucket.

Separate chaining uses linked lists (or other structures) in each bucket to store multiple entries that hash to the same index. This matches the description.

🔧 Debug

advanced

What error does this Rust HashMap get method code produce?

Given this code snippet trying to get a value from a custom HashMap, what error occurs?

DSA Rust

let mut map = std::collections::HashMap::new();
map.insert(1, "one");
let value = map.get(&2).unwrap();
println!("{}", value);

A panic at unwrap on None value

B Compilation error: missing lifetime specifier

C No error, prints "one"

D Type mismatch error

💡 Hint

What happens when you unwrap an Option that is None?

Calling unwrap on None causes a panic at runtime. Since key 2 was not inserted, get returns None, so unwrap panics.

🚀 Application

advanced

How many items are in the HashMap after these operations?

Starting with an empty HashMap, perform these operations: insert key 1 with value 'x', insert key 2 with value 'y', insert key 1 with value 'z', then remove key 2. How many items remain?

DSA Rust

let mut map = std::collections::HashMap::new();
map.insert(1, 'x');
map.insert(2, 'y');
map.insert(1, 'z');
map.remove(&2);
println!("{}", map.len());

A 3

B 1

C 0

D 2

💡 Hint

Remember that inserting a key that already exists updates its value.

Inserting key 1 twice updates its value, so only one entry for key 1 exists. Key 2 is removed, so only one item remains.

❓ Predict Output

expert

What is the output of this Rust HashMap custom hash function code?

Given a custom HashMap implementation with a simple hash function that returns key modulo 3, and inserting keys 3, 6, 9 with values 'a', 'b', 'c', what is the final state of the buckets?

DSA Rust

struct Entry {
    key: i32,
    value: char,
    next: Option<Box<Entry>>,
}

let mut buckets: Vec<Option<Box<Entry>>> = vec![None; 3];

fn hash(key: i32) -> usize {
    (key % 3) as usize
}

fn insert(buckets: &mut Vec<Option<Box<Entry>>>, key: i32, value: char) {
    let index = hash(key);
    let new_entry = Box::new(Entry { key, value, next: buckets[index].take() });
    buckets[index] = Some(new_entry);
}

insert(&mut buckets, 3, 'a');
insert(&mut buckets, 6, 'b');
insert(&mut buckets, 9, 'c');

// Print bucket keys in order from head to tail for each bucket
for (i, bucket) in buckets.iter().enumerate() {
    print!("Bucket {}: ", i);
    let mut current = bucket.as_ref();
    while let Some(entry) = current {
        print!("{} -> ", entry.key);
        current = entry.next.as_ref();
    }
    println!("null");
}

A

Bucket 0: null
Bucket 1: 3 -> 6 -> 9 -> null
Bucket 2: null

B

Bucket 0: 3 -> 6 -> 9 -> null
Bucket 1: null
Bucket 2: null

C

Bucket 0: 3 -> null
Bucket 1: 6 -> null
Bucket 2: 9 -> null

D

Bucket 0: 9 -> 6 -> 3 -> null
Bucket 1: null
Bucket 2: null

💡 Hint

New entries are added at the head of the linked list in each bucket.

Each key hashes to bucket 0 (3 % 3 = 0). Insertions add new entries at the head, so the last inserted key 9 is at the head, followed by 6, then 3.

Practice

1. What is the main purpose of a HashMap in data structures?

easy

A. To store elements in a queue-like manner

B. To store elements in sorted order

C. To store key-value pairs for fast lookup

D. To store elements in a stack-like manner

Solution

1. Step 1: Understand HashMap functionality

   A HashMap stores data as key-value pairs, allowing quick access by key.

2. Step 2: Compare with other data structures

   Unlike stacks or queues, HashMaps do not maintain order but focus on fast lookup.

3. Final Answer:

   To store key-value pairs for fast lookup -> Option C

4. Quick Check:

   HashMap = key-value fast access [OK]

Hint: HashMap = fast key-value storage [OK]

Common Mistakes:

• Confusing HashMap with sorted structures
• Thinking HashMap stores elements in order
• Mixing HashMap with stack or queue behavior

2. Which of the following is the correct Rust syntax to create an empty HashMap from scratch?

easy

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

B. let map = new HashMap();

C. let map = HashMap();

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

Solution

1. Step 1: Recall Rust HashMap creation syntax

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

2. Step 2: Check other options for Rust correctness

   Options B, C, and D are not valid Rust syntax for HashMap creation.

3. Final Answer:

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

4. Quick Check:

   Rust HashMap empty = HashMap::new() [OK]

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

Common Mistakes:

• Using constructor syntax like new HashMap()
• Calling HashMap() without ::new()
• Using non-existent methods like empty()

3. Consider this simplified Rust code snippet for a custom HashMap insert method:

let mut map = MyHashMap::new();
map.insert("apple", 3);
map.insert("banana", 5);
map.insert("apple", 7);
println!("{:?}", map.get("apple"));

What will be printed?

medium

A. Some(3)

B. Some(7)

C. None

D. Some(5)

Solution

1. Step 1: Analyze insertions for key "apple"

   First insert sets "apple" to 3, second insert updates "apple" to 7.

2. Step 2: Check the get method output

   Getting "apple" returns the latest value, which is 7, wrapped in Some.

3. Final Answer:

   Some(7) -> Option B

4. Quick Check:

   Last insert value = get output [OK]

Hint: Last inserted value for key is returned [OK]

Common Mistakes:

• Assuming first inserted value remains
• Confusing None with Some value
• Mixing values of different keys

4. Given this Rust snippet for a custom HashMap insert method, what is the bug?

fn insert(&mut self, key: K, value: V) {
    let index = self.hash(&key) % self.buckets.len();
    if self.buckets[index].is_empty() {
        self.buckets[index].push((key, value));
    } else {
        self.buckets[index].push((key, value));
    }
}

medium

A. It does not update value if key exists, causing duplicates

B. It uses wrong hash function signature

C. It does not handle empty buckets correctly

D. It forgets to resize buckets when full

Solution

1. Step 1: Review insert logic for existing keys

   The code always pushes new (key, value) pairs without checking for existing keys.

2. Step 2: Identify consequence of missing update

   This causes duplicate keys in the same bucket, breaking expected HashMap behavior.

3. Final Answer:

   It does not update value if key exists, causing duplicates -> Option A

4. Quick Check:

   Insert must update existing key, not just push [OK]

Hint: Check for existing key before inserting [OK]

Common Mistakes:

• Ignoring key existence before insert
• Assuming push replaces existing entries
• Missing bucket resizing logic

5. You are implementing a custom HashMap in Rust with separate chaining. Which approach best handles collisions and updates existing keys efficiently?

hard

A. Store key-value pairs in a vector at each bucket; on insert, search vector for key to update or append

B. Use a single vector for all keys without hashing; append all pairs sequentially

C. Replace entire bucket vector on each insert without checking keys

D. Use a linked list but never check for existing keys before inserting

Solution

1. Step 1: Understand separate chaining collision handling

   Separate chaining uses a list (vector) at each bucket to store multiple key-value pairs.

2. Step 2: Efficient insert requires checking existing keys

   Before inserting, search the bucket's vector for the key to update value or append if not found.

3. Step 3: Evaluate options

   Store key-value pairs in a vector at each bucket; on insert, search vector for key to update or append correctly describes this approach; others ignore key checks or hashing.

4. Final Answer:

   Store key-value pairs in a vector at each bucket; on insert, search vector for key to update or append -> Option A

5. Quick Check:

   Separate chaining + key check = efficient insert [OK]

Hint: Search bucket vector for key before insert [OK]

Common Mistakes:

• Ignoring key existence in bucket
• Not using hashing for bucket selection
• Replacing bucket data blindly