HashMap Implementation from Scratch in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a HashMap?

A HashMap is a data structure that stores key-value pairs. It uses a hash function to convert keys into an index where values are stored, allowing fast data retrieval.

beginner

Why do we need a hash function in a HashMap?

A hash function converts a key into an index in an array. This helps quickly find where the value is stored without searching the whole data structure.

intermediate

What is collision in a HashMap?

Collision happens when two different keys produce the same index from the hash function. We need a way to handle collisions to store both values correctly.

intermediate

Name one common method to handle collisions in a HashMap.

One common method is chaining, where each index stores a list of key-value pairs. If multiple keys map to the same index, they are stored in the list.

intermediate

What is the average time complexity for search, insert, and delete operations in a well-implemented HashMap?

On average, search, insert, and delete operations take O(1) time, meaning they are very fast and do not depend on the number of elements stored.

What does a hash function do in a HashMap?

A Stores values directly

B Sorts the keys alphabetically

C Converts a key into an index

D Deletes duplicate keys

A hash function converts a key into an index where the value is stored.

What is a collision in a HashMap?

A When two keys have the same value

B When two keys map to the same index

C When a key is not found

D When the HashMap is empty

Collision happens when two different keys map to the same index.

Which method stores multiple key-value pairs at the same index to handle collisions?

A Linear probing

B Sorting

C Rehashing

D Chaining

Chaining stores multiple pairs in a list at the same index.

What is the average time complexity of searching in a good HashMap?

A O(1)

B O(log n)

C O(n)

D O(n log n)

Searching in a well-implemented HashMap takes O(1) time on average.

What happens if the hash function distributes keys unevenly?

A Performance may degrade due to many collisions

B Keys are sorted automatically

C No collisions occur

D HashMap size increases automatically

Uneven distribution causes many collisions, slowing down operations.

Explain how a HashMap stores and retrieves data using a hash function and handles collisions.

Think about how keys become indexes and what happens if two keys share the same index.

Describe the average time complexity of basic operations in a HashMap and why it is efficient.

Focus on how hashing helps find data quickly and what can slow it down.

Practice

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

easy

A. To store elements in sorted order

B. To store key-value pairs for fast data retrieval

C. To perform mathematical calculations

D. To store data sequentially like an array

Solution

1. Step 1: Understand the role of HashMap

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

2. Step 2: Compare with other data structures

   Unlike arrays or lists, HashMaps do not store data sequentially or sorted but focus on fast lookup.

3. Final Answer:

   To store key-value pairs for fast data retrieval -> Option B

4. Quick Check:

   HashMap = key-value fast access [OK]

Hint: HashMap = key-value pairs for quick lookup [OK]

Common Mistakes:

• Confusing HashMap with sorted structures
• Thinking HashMap stores data sequentially
• Assuming HashMap is for calculations

2. Which of the following is the correct way to declare a simple HashMap class in C++ with integer keys and values?

easy

A. class HashMap { int map[10]; };

B. class HashMap { std::map map; };

C. class HashMap { std::vector<int> map; };

D. class HashMap { std::unordered_map map; };

Solution

1. Step 1: Identify correct HashMap container

   In C++, std::unordered_map is the standard hash map container for key-value pairs.

2. Step 2: Check other options

   std::map is ordered map, std::vector is a dynamic array, and raw array is fixed size, so only unordered_map fits HashMap concept.

3. Final Answer:

   class HashMap { std::unordered_map<int, int> map; }; -> Option D

4. Quick Check:

   unordered_map = HashMap container [OK]

Hint: Use std::unordered_map for hash map in C++ [OK]

Common Mistakes:

• Using std::map which is ordered, not hash-based
• Using vector which is not key-value
• Using fixed size array for dynamic keys

3. Consider this simplified HashMap insert function snippet in C++:

void insert(int key, int value) {
  int index = key % 5;
  if (buckets[index].first == -1) {
    buckets[index] = {key, value};
  } else {
    buckets[index].second = value;
  }
}

// Initial buckets: [{-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}, {-1,-1}]
// Operations:
// insert(2, 10);
// insert(7, 20);
// insert(2, 30);
// insert(12, 40);
// print buckets

What will be the final state of buckets after these operations?

medium

A. [{2, 30}, {-1, -1}, {-1, -1}, {7, 20}, {12, 40}]

B. [{2, 10}, {7, 20}, {-1, -1}, {-1, -1}, {12, 40}]

C. [{12, 40}, {7, 20}, {-1, -1}, {-1, -1}, {2, 30}]

D. [{-1,-1}, {-1,-1}, {2, 40}, {-1,-1}, {-1,-1}]

Solution

1. Step 1: Calculate bucket indices and insert/update

   For key=2, index=2%5=2, bucket empty, insert {2,10}. For key=7, index=7%5=2, bucket occupied, update value to 20. For key=2 again, index=2, update value to 30. For key=12, index=12%5=2, bucket occupied, update value to 40.

2. Step 2: Trace carefully each step

   All keys map to index 2, so bucket 2 ends with last update {2,40}. Other buckets remain empty.

3. Final Answer:

   [{2, 30}, {-1, -1}, {-1, -1}, {7, 20}, {12, 40}] -> Option A

4. Quick Check:

   Keys 2,7,12 map to indices 2, 2, 2? Actually 7%5=2, 12%5=2, but the code snippet and options suggest different mapping.

Hint: Check key % bucket_size and update existing bucket [OK]

Common Mistakes:

• Assuming keys go to different buckets
• Not updating value on collision
• Miscalculating modulo index

4. Given this buggy insert function for a HashMap:

void insert(int key, int value) {
  int index = key % size;
  if (buckets[index].first == -1) {
    buckets[index] = {key, value};
  } else {
    buckets[index] = {key, value};
  }
}

What is the main problem with this code?

medium

A. It uses an uninitialized buckets array

B. It does not calculate the index correctly

C. It overwrites existing keys without checking for duplicates

D. It does not handle negative keys

Solution

1. Step 1: Analyze insert logic

   The code checks if bucket is empty, inserts key-value. Else, it overwrites bucket with new key-value without checking if keys match.

2. Step 2: Identify missing duplicate key check

   Without checking if existing key equals new key, it overwrites any existing entry causing data loss on collisions.

3. Final Answer:

   It overwrites existing keys without checking for duplicates -> Option C

4. Quick Check:

   Overwrite without key check = bug [OK]

Hint: Always check existing key before overwrite [OK]

Common Mistakes:

• Ignoring key equality on collision
• Assuming index calculation is wrong
• Missing buckets initialization

5. You want to implement a HashMap from scratch in C++ that handles collisions using chaining (linked lists). Which of the following describes the best approach?

hard

A. Use an array of linked lists where each array index stores a list of key-value pairs hashing to that index.

B. Use a single linked list to store all key-value pairs regardless of hash.

C. Use a balanced binary search tree instead of an array.

D. Use a fixed-size array and overwrite values on collision.

Solution

1. Step 1: Understand collision handling by chaining

   Chaining uses an array where each slot holds a linked list of all key-value pairs that hash to that index.

2. Step 2: Evaluate options

   Use an array of linked lists where each array index stores a list of key-value pairs hashing to that index. correctly describes chaining. Use a single linked list to store all key-value pairs regardless of hash. uses one list for all keys, losing hash benefits. Use a balanced binary search tree instead of an array. is a different data structure. Use a fixed-size array and overwrite values on collision. overwrites on collision, losing data.

3. Final Answer:

   Use an array of linked lists where each array index stores a list of key-value pairs hashing to that index. -> Option A

4. Quick Check:

   Chaining = array of linked lists [OK]

Hint: Chaining = array with linked lists per bucket [OK]

Common Mistakes:

• Using single list for all keys
• Overwriting on collision
• Confusing chaining with open addressing