HashMap Implementation from Scratch in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Basic HashMap Insertions

What is the printed state of the HashMap after inserting three key-value pairs?

DSA C++

class HashMap {
private:
    static const int SIZE = 5;
    std::pair<int, int> table[SIZE];
    bool occupied[SIZE];

public:
    HashMap() {
        for (int i = 0; i < SIZE; i++) {
            occupied[i] = false;
        }
    }

    int hash(int key) {
        return key % SIZE;
    }

    void insert(int key, int value) {
        int idx = hash(key);
        while (occupied[idx]) {
            idx = (idx + 1) % SIZE;
        }
        table[idx] = {key, value};
        occupied[idx] = true;
    }

    void print() {
        for (int i = 0; i < SIZE; i++) {
            if (occupied[i]) {
                std::cout << table[i].first << ":" << table[i].second << " ";
            } else {
                std::cout << "_ ";
            }
        }
        std::cout << std::endl;
    }
};

int main() {
    HashMap map;
    map.insert(1, 10);
    map.insert(6, 20);
    map.insert(11, 30);
    map.print();
    return 0;
}

A 1:10 6:20 11:30 _ _

B 1:10 6:20 _ 11:30 _

C _ 1:10 6:20 11:30 _

D 1:10 _ 6:20 11:30 _

💡 Hint

Remember the hash function is key % 5 and collision is resolved by linear probing.

Keys 1, 6, and 11 all hash to index 1 (1 % 5 = 1, 6 % 5 = 1, 11 % 5 = 1). Insert 1 at index 1. For 6, index 1 is occupied, so move to index 2. For 11, indexes 1 and 2 are occupied, so move to index 3.

🧠 Conceptual

intermediate

Understanding HashMap Collision Resolution

Which collision resolution technique is used in the following HashMap implementation?

DSA C++

void insert(int key, int value) {
    int idx = hash(key);
    while (occupied[idx]) {
        idx = (idx + 1) % SIZE;
    }
    table[idx] = {key, value};
    occupied[idx] = true;
}

A Quadratic probing

B Linear probing

C Separate chaining with linked lists

D Double hashing

💡 Hint

Look at how the index is updated when a collision occurs.

The code increments the index by 1 each time a collision happens, wrapping around the table. This is linear probing.

🔧 Debug

advanced

Identify the Bug in HashMap Search Method

What error will occur when running the search method below if the key is not present?

DSA C++

int search(int key) {
    int idx = hash(key);
    while (occupied[idx]) {
        if (table[idx].first == key) {
            return table[idx].second;
        }
        idx = (idx + 1) % SIZE;
    }
    return -1;
}

// Assume SIZE = 5 and occupied array is properly maintained.

A Returns -1 correctly when key not found

B Infinite loop if key not present

C Accesses uninitialized memory causing runtime error

D Throws a compilation error due to missing return

💡 Hint

Consider what happens when the key is not in the table and the loop condition.

The loop stops when it finds an empty slot (occupied[idx] == false), so it returns -1 correctly if the key is not found.

❓ Predict Output

advanced

Output After Deletion and Re-insertion in HashMap

What is the printed state of the HashMap after deleting key 6 and inserting key 16 with value 160?

DSA C++

class HashMap {
private:
    static const int SIZE = 5;
    std::pair<int, int> table[SIZE];
    bool occupied[SIZE];
    bool deleted[SIZE];

public:
    HashMap() {
        for (int i = 0; i < SIZE; i++) {
            occupied[i] = false;
            deleted[i] = false;
        }
    }

    int hash(int key) {
        return key % SIZE;
    }

    void insert(int key, int value) {
        int idx = hash(key);
        while (occupied[idx] && !deleted[idx]) {
            idx = (idx + 1) % SIZE;
        }
        table[idx] = {key, value};
        occupied[idx] = true;
        deleted[idx] = false;
    }

    void remove(int key) {
        int idx = hash(key);
        while (occupied[idx]) {
            if (!deleted[idx] && table[idx].first == key) {
                deleted[idx] = true;
                return;
            }
            idx = (idx + 1) % SIZE;
        }
    }

    void print() {
        for (int i = 0; i < SIZE; i++) {
            if (occupied[i] && !deleted[i]) {
                std::cout << table[i].first << ":" << table[i].second << " ";
            } else {
                std::cout << "_ ";
            }
        }
        std::cout << std::endl;
    }
};

int main() {
    HashMap map;
    map.insert(1, 10);
    map.insert(6, 20);
    map.insert(11, 30);
    map.remove(6);
    map.insert(16, 160);
    map.print();
    return 0;
}

A 1:10 _ 11:30 16:160 _

B 1:10 16:160 11:30 _ _

C 1:10 _ 11:30 _ 16:160

D _ 1:10 11:30 16:160 _

💡 Hint

Remember that deleted slots can be reused for insertion.

Key 6 was at index 2 and marked deleted. Inserting 16 hashes to index 1, which is occupied, then index 2 is deleted and reused for 16.

🚀 Application

expert

Predict Final HashMap State After Multiple Operations

Given the following sequence of operations on an empty HashMap of size 7, what is the final printed state?

Operations:

1. insert(3, 30)
2. insert(10, 100)
3. insert(17, 170)
4. remove(10)
5. insert(24, 240)
6. insert(31, 310)
7. remove(3)
8. insert(38, 380)

DSA C++

class HashMap {
private:
    static const int SIZE = 7;
    std::pair<int, int> table[SIZE];
    bool occupied[SIZE];
    bool deleted[SIZE];

public:
    HashMap() {
        for (int i = 0; i < SIZE; i++) {
            occupied[i] = false;
            deleted[i] = false;
        }
    }

    int hash(int key) {
        return key % SIZE;
    }

    void insert(int key, int value) {
        int idx = hash(key);
        while (occupied[idx] && !deleted[idx]) {
            idx = (idx + 1) % SIZE;
        }
        table[idx] = {key, value};
        occupied[idx] = true;
        deleted[idx] = false;
    }

    void remove(int key) {
        int idx = hash(key);
        while (occupied[idx]) {
            if (!deleted[idx] && table[idx].first == key) {
                deleted[idx] = true;
                return;
            }
            idx = (idx + 1) % SIZE;
        }
    }

    void print() {
        for (int i = 0; i < SIZE; i++) {
            if (occupied[i] && !deleted[i]) {
                std::cout << table[i].first << ":" << table[i].second << " ";
            } else {
                std::cout << "_ ";
            }
        }
        std::cout << std::endl;
    }
};

int main() {
    HashMap map;
    map.insert(3, 30);
    map.insert(10, 100);
    map.insert(17, 170);
    map.remove(10);
    map.insert(24, 240);
    map.insert(31, 310);
    map.remove(3);
    map.insert(38, 380);
    map.print();
    return 0;
}

A _ 24:240 31:310 38:380 17:170 _ _

B _ 24:240 _ 31:310 38:380 17:170 _

C _ 24:240 31:310 _ 38:380 17:170 _

D _ 24:240 31:310 38:380 _ 17:170 _

💡 Hint

Trace each insertion and removal carefully, remembering linear probing and lazy deletion.

Keys hash as follows: 3->3, 10->3, 17->3, 24->3, 31->3, 38->3. Insertions and removals shift keys forward. After removals and insertions, the final occupied and non-deleted slots are at indices 1,2,3,5 with keys 24,31,38,17 respectively.

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