HashMap Implementation from Scratch in DSA C++

Mental Model

A HashMap stores key-value pairs by turning keys into indexes using a hash function, so we can find values quickly without searching everything.

Analogy: Imagine a library where each book has a unique code. Instead of searching all shelves, you use the code to go directly to the right shelf and find the book fast.

Buckets array:
[0] -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null
Each bucket can hold a linked list of key-value pairs.

Dry Run Walkthrough

Input: Insert key-value pairs: (10, 'A'), (20, 'B'), (30, 'C') into a HashMap with 5 buckets using hash = key % 5

Goal: Store the pairs so we can find each value by its key quickly using the hash function and handle collisions by chaining.

Step 1: Insert (10, 'A'): compute hash 10 % 5 = 0, add node to bucket 0

[0] -> (10, 'A') -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Why: We use the hash to find the bucket index and add the pair there.

Step 2: Insert (20, 'B'): compute hash 20 % 5 = 0, collision at bucket 0, add node at head

[0] -> (20, 'B') -> (10, 'A') -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Why: Collision handled by adding new node at the start of the linked list in bucket 0.

Step 3: Insert (30, 'C'): compute hash 30 % 5 = 0, collision at bucket 0, add node at head

[0] -> (30, 'C') -> (20, 'B') -> (10, 'A') -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Why: Again collision, so add new node at the head of bucket 0's list.

Step 4: Search for key 20: compute hash 20 % 5 = 0, traverse bucket 0 list to find key

[0] -> (30, 'C') -> (20, 'B') -> (10, 'A') -> null

Why: We check each node in bucket 0 until we find key 20.

Step 5: Delete key 30: compute hash 30 % 5 = 0, remove node with key 30 from bucket 0 list

[0] -> (20, 'B') -> (10, 'A') -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Why: Remove the node with key 30 by adjusting pointers in the linked list.

Result:

[0] -> (20, 'B') -> (10, 'A') -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Annotated Code

DSA C++

#include <iostream>
#include <string>
using namespace std;

struct Node {
    int key;
    string value;
    Node* next;
    Node(int k, string v) : key(k), value(v), next(nullptr) {}
};

class HashMap {
    static const int BUCKET_SIZE = 5;
    Node* buckets[BUCKET_SIZE];

    int hash(int key) {
        return key % BUCKET_SIZE; // hash function
    }

public:
    HashMap() {
        for (int i = 0; i < BUCKET_SIZE; i++) {
            buckets[i] = nullptr; // initialize buckets
        }
    }

    void insert(int key, string value) {
        int idx = hash(key); // find bucket
        Node* head = buckets[idx];
        // check if key exists, update value
        for (Node* curr = head; curr != nullptr; curr = curr->next) {
            if (curr->key == key) {
                curr->value = value; // update existing
                return;
            }
        }
        // insert new node at head
        Node* newNode = new Node(key, value);
        newNode->next = head;
        buckets[idx] = newNode;
    }

    string search(int key) {
        int idx = hash(key); // find bucket
        Node* curr = buckets[idx];
        while (curr != nullptr) {
            if (curr->key == key) {
                return curr->value; // found
            }
            curr = curr->next; // move to next node
        }
        return "Not found"; // not found
    }

    void remove(int key) {
        int idx = hash(key); // find bucket
        Node* curr = buckets[idx];
        Node* prev = nullptr;
        while (curr != nullptr) {
            if (curr->key == key) {
                if (prev == nullptr) {
                    buckets[idx] = curr->next; // remove head
                } else {
                    prev->next = curr->next; // bypass curr
                }
                delete curr; // free memory
                return;
            }
            prev = curr;
            curr = curr->next; // move forward
        }
    }

    void print() {
        for (int i = 0; i < BUCKET_SIZE; i++) {
            cout << "[" << i << "] -> ";
            Node* curr = buckets[i];
            while (curr != nullptr) {
                cout << "(" << curr->key << ", '" << curr->value << "') -> ";
                curr = curr->next;
            }
            cout << "null" << endl;
        }
    }
};

int main() {
    HashMap map;
    map.insert(10, "A");
    map.insert(20, "B");
    map.insert(30, "C");
    map.print();
    cout << "Search key 20: " << map.search(20) << endl;
    map.remove(30);
    map.print();
    return 0;
}

int idx = hash(key); // find bucket

compute bucket index using hash function

for (Node* curr = head; curr != nullptr; curr = curr->next) { if (curr->key == key) { curr->value = value; return; } }

check if key exists to update value

Node* newNode = new Node(key, value); newNode->next = head; buckets[idx] = newNode;

insert new node at head of bucket list

while (curr != nullptr) { if (curr->key == key) { return curr->value; } curr = curr->next; }

search linked list in bucket for key

while (curr != nullptr) { if (curr->key == key) { if (prev == nullptr) { buckets[idx] = curr->next; } else { prev->next = curr->next; } delete curr; return; } prev = curr; curr = curr->next; }

remove node with key by adjusting pointers

Output

[0] -> (30, 'C') -> (20, 'B') -> (10, 'A') -> null

[1] -> null

[2] -> null

[3] -> null

[4] -> null

Search key 20: B

[0] -> (20, 'B') -> (10, 'A') -> null

[1] -> null

[2] -> null

[3] -> null

[4] -> null

Complexity Analysis

Time: O(n/k) on average, where n is number of keys and k is bucket count, because each bucket holds about n/k nodes; worst case O(n) if all keys collide.

Space: O(n) because we store all key-value pairs in nodes.

vs Alternative: Compared to a simple list with O(n) search, HashMap offers average O(1) search, insert, and delete by using hashing and chaining.

Edge Cases

Insert duplicate key

Value is updated in existing node instead of adding new node

DSA C++

for (Node* curr = head; curr != nullptr; curr = curr->next) { if (curr->key == key) { curr->value = value; return; } }

Remove key not present

No change, function returns without error

DSA C++

while (curr != nullptr) { if (curr->key == key) { ... } curr = curr->next; }

Search in empty bucket

Returns "Not found"

DSA C++

while (curr != nullptr) { if (curr->key == key) { return curr->value; } curr = curr->next; } return "Not found";

When to Use This Pattern

When you need fast key-value storage with quick insert, search, and delete, and you see keys that can be hashed, use the HashMap pattern with chaining to handle collisions.

Common Mistakes

Mistake: Not handling collisions, overwriting existing nodes or losing data
Fix: Use linked lists (chaining) in buckets to store multiple nodes per bucket.

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

Mistake: Incorrect pointer updates when removing nodes, causing broken lists
Fix: Carefully update previous node's next pointer or bucket head pointer when deleting.

Summary

Stores key-value pairs using a hash function to find buckets and linked lists to handle collisions.

Use when you want fast average-time insert, search, and delete operations by key.

The key insight is using a hash function to jump to a bucket and chaining to handle multiple keys in the same bucket.

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