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 hash map after inserting keys 1, 2, and 3 with values 'A', 'B', and 'C' respectively?

DSA C

typedef struct Node {
    int key;
    char value;
    struct Node* next;
} Node;

#define SIZE 5

Node* hashMap[SIZE] = {NULL};

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

void insert(int key, char value) {
    int index = hash(key);
    Node* newNode = malloc(sizeof(Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = hashMap[index];
    hashMap[index] = newNode;
}

void printHashMap() {
    for (int i = 0; i < SIZE; i++) {
        printf("Bucket %d: ", i);
        Node* temp = hashMap[i];
        while (temp) {
            printf("(%d -> %c) -> ", temp->key, temp->value);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    insert(1, 'A');
    insert(2, 'B');
    insert(3, 'C');
    printHashMap();
    return 0;
}

A

Bucket 0: NULL
Bucket 1: (1 -> A) -> NULL
Bucket 2: (2 -> B) -> NULL
Bucket 3: (3 -> C) -> NULL
Bucket 4: NULL

B

Bucket 0: NULL
Bucket 1: (1 -> A) -> NULL
Bucket 2: NULL
Bucket 3: (3 -> C) -> NULL
Bucket 4: (2 -> B) -> NULL

C

Bucket 0: NULL
Bucket 1: (1 -> A) -> NULL
Bucket 2: (2 -> B) -> NULL
Bucket 3: NULL
Bucket 4: (3 -> C) -> NULL

D

Bucket 0: NULL
Bucket 1: NULL
Bucket 2: (2 -> B) -> NULL
Bucket 3: (3 -> C) -> NULL
Bucket 4: (1 -> A) -> NULL

💡 Hint

Remember the hash function is key % SIZE, and SIZE is 5.

The hash function places keys 1, 2, and 3 into buckets 1, 2, and 3 respectively. Each bucket contains one node with the inserted key and value.

❓ Predict Output

intermediate

Collision Handling in HashMap

What is the printed state of the hash map after inserting keys 1, 6, and 11 with values 'X', 'Y', and 'Z' respectively?

DSA C

typedef struct Node {
    int key;
    char value;
    struct Node* next;
} Node;

#define SIZE 5

Node* hashMap[SIZE] = {NULL};

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

void insert(int key, char value) {
    int index = hash(key);
    Node* newNode = malloc(sizeof(Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = hashMap[index];
    hashMap[index] = newNode;
}

void printHashMap() {
    for (int i = 0; i < SIZE; i++) {
        printf("Bucket %d: ", i);
        Node* temp = hashMap[i];
        while (temp) {
            printf("(%d -> %c) -> ", temp->key, temp->value);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    insert(1, 'X');
    insert(6, 'Y');
    insert(11, 'Z');
    printHashMap();
    return 0;
}

A

Bucket 0: NULL
Bucket 1: (11 -> Z) -> (6 -> Y) -> (1 -> X) -> NULL
Bucket 2: NULL
Bucket 3: NULL
Bucket 4: NULL

B

Bucket 0: NULL
Bucket 1: (1 -> X) -> NULL
Bucket 2: (6 -> Y) -> NULL
Bucket 3: (11 -> Z) -> NULL
Bucket 4: NULL

C

Bucket 0: NULL
Bucket 1: (6 -> Y) -> (11 -> Z) -> (1 -> X) -> NULL
Bucket 2: NULL
Bucket 3: NULL
Bucket 4: NULL

D

Bucket 0: NULL
Bucket 1: (1 -> X) -> (6 -> Y) -> (11 -> Z) -> NULL
Bucket 2: NULL
Bucket 3: NULL
Bucket 4: NULL

💡 Hint

All keys hash to the same bucket because of the modulo operation.

Keys 1, 6, and 11 all hash to bucket 1 (1 % 5 = 1, 6 % 5 = 1, 11 % 5 = 1). New nodes are inserted at the head, so the last inserted key appears first.

🔧 Debug

advanced

Find the Bug in HashMap Search Function

What error will occur when running this search function in the hash map implementation?

DSA C

char search(int key) {
    int index = hash(key);
    Node* temp = hashMap[index];
    while (temp != NULL) {
        if (temp->key == key) {
            return temp->value;
        }
        temp = temp->next;
    }
    return '\0';
}

A Runtime crash due to null pointer dereference

B Compilation error due to invalid pointer usage

C No error, returns the correct value if key found

D Infinite loop due to assignment in if condition

💡 Hint

Check the if condition inside the while loop carefully.

The if condition uses assignment (=) instead of comparison (==). This causes the condition to always be true (except when key is 0), leading to incorrect behavior or infinite loop.

❓ Predict Output

advanced

Output After Deleting a Key from HashMap

What is the printed state of the hash map after inserting keys 2, 7, 12 with values 'P', 'Q', 'R' and then deleting key 7?

DSA C

typedef struct Node {
    int key;
    char value;
    struct Node* next;
} Node;

#define SIZE 5

Node* hashMap[SIZE] = {NULL};

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

void insert(int key, char value) {
    int index = hash(key);
    Node* newNode = malloc(sizeof(Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = hashMap[index];
    hashMap[index] = newNode;
}

void delete(int key) {
    int index = hash(key);
    Node* temp = hashMap[index];
    Node* prev = NULL;
    while (temp) {
        if (temp->key == key) {
            if (prev == NULL) {
                hashMap[index] = temp->next;
            } else {
                prev->next = temp->next;
            }
            free(temp);
            return;
        }
        prev = temp;
        temp = temp->next;
    }
}

void printHashMap() {
    for (int i = 0; i < SIZE; i++) {
        printf("Bucket %d: ", i);
        Node* temp = hashMap[i];
        while (temp) {
            printf("(%d -> %c) -> ", temp->key, temp->value);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    insert(2, 'P');
    insert(7, 'Q');
    insert(12, 'R');
    delete(7);
    printHashMap();
    return 0;
}

A

Bucket 0: NULL
Bucket 1: NULL
Bucket 2: (7 -> Q) -> (12 -> R) -> (2 -> P) -> NULL
Bucket 3: NULL
Bucket 4: NULL

B

Bucket 0: NULL
Bucket 1: NULL
Bucket 2: (2 -> P) -> (12 -> R) -> NULL
Bucket 3: NULL
Bucket 4: NULL

C

Bucket 0: NULL
Bucket 1: NULL
Bucket 2: (12 -> R) -> (2 -> P) -> NULL
Bucket 3: NULL
Bucket 4: NULL

D

Bucket 0: NULL
Bucket 1: NULL
Bucket 2: (12 -> R) -> NULL
Bucket 3: NULL
Bucket 4: NULL

💡 Hint

Remember the hash function and that new nodes are inserted at the head.

Keys 2, 7, and 12 all hash to bucket 2. Insertions add nodes at the head, so order before deletion is 12 -> 7 -> 2. Deleting key 7 removes the middle node, leaving 12 -> 2.

🧠 Conceptual

expert

Why Use Linked Lists for Collision Handling in HashMap?

Which is the main reason linked lists are used to handle collisions in a hash map implementation?

A Linked lists improve the hash function's speed by sorting keys automatically.

B Linked lists allow storing multiple key-value pairs in the same bucket efficiently without fixed size limits.

C Linked lists prevent collisions by changing the hash function dynamically.

D Linked lists reduce memory usage by storing keys as indexes instead of values.

💡 Hint

Think about what happens when two keys hash to the same bucket.

Linked lists allow multiple nodes to be chained in the same bucket, handling collisions by storing all collided key-value pairs without a fixed size limit.

Practice

1. What is the main purpose of a hash function in a HashMap implementation?

easy

A. To sort the keys in ascending order

B. To store values in a linked list

C. To convert a key into an index for storing the value

D. To delete keys from the HashMap

Solution

1. Step 1: Understand the role of a hash function

   A hash function takes a key and converts it into a number (index) that tells where to store the value in the HashMap's internal array.

2. Step 2: Compare other options

   Sorting keys or deleting keys are not the job of the hash function. Storing values in a linked list is a collision handling method, not hashing.

3. Final Answer:

   To convert a key into an index for storing the value -> Option C

4. Quick Check:

   Hash function = key to index [OK]

Hint: Hash function maps keys to array indexes fast [OK]

Common Mistakes:

• Thinking hash function sorts keys
• Confusing hash function with collision handling
• Believing hash function deletes keys

2. Which of the following is the correct way to declare a simple HashMap structure in C that stores integer keys and values?

easy

A. typedef struct { int key; int value; } HashNode;

B. typedef struct { char* key; int value; } HashMap;

C. typedef struct { int key; int value; } HashMap;

D. typedef struct { int key; int value; HashNode* next; } HashMap;

Solution

1. Step 1: Identify the basic node structure

   A HashMap stores key-value pairs. A node with int key and int value is a basic unit, so HashNode struct is correct.

2. Step 2: Check other options

   typedef struct { char* key; int value; } HashMap; uses char* key which is not integer keys. typedef struct { int key; int value; } HashMap; names the struct HashMap but it's actually a node. typedef struct { int key; int value; HashNode* next; } HashMap; adds a pointer for chaining but names it HashMap, which is confusing.

3. Final Answer:

   typedef struct { int key; int value; } HashNode; -> Option A

4. Quick Check:

   Node struct with int key and value = typedef struct { int key; int value; } HashNode; [OK]

Hint: Node struct holds key and value pairs [OK]

Common Mistakes:

• Confusing node and map struct names
• Using wrong key types
• Missing pointer for chaining in basic struct

3. Given the following code snippet for inserting keys into a HashMap with size 5, what will be the index for key 12?

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

int index = hash(12);
printf("%d", index);

medium

A. 4

B. 2

C. 3

D. 1

Solution

1. Step 1: Apply the hash function to key 12

   The hash function returns key % 5. For key 12, 12 % 5 = 2.

2. Step 2: Confirm the printed index

   The code prints the index, which is 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   12 % 5 = 2 [OK]

Hint: Modulo operator gives index in hash function [OK]

Common Mistakes:

• Calculating 12 % 5 incorrectly
• Confusing modulo with division
• Ignoring hash function logic

4. Consider this buggy code snippet for inserting a key-value pair into a HashMap with chaining:

void insert(HashNode** table, int size, int key, int value) {
    int index = key % size;
    HashNode* newNode = malloc(sizeof(HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = NULL;

    if (table[index] == NULL) {
        table[index] = newNode;
    } else {
        table[index]->next = newNode;
    }
}

What is the main problem in this code?

medium

A. It overwrites the existing chain instead of appending correctly

B. It does not handle memory allocation failure

C. It uses wrong hash function

D. It does not set the key and value fields

Solution

1. Step 1: Analyze insertion logic for chaining

   If the bucket is empty, it sets the new node. Otherwise, it sets table[index]->next = newNode, which overwrites the existing next pointer, losing the chain.

2. Step 2: Identify correct chaining method

   To append, it should traverse to the last node in the chain and then add the new node, not overwrite the first node's next pointer.

3. Final Answer:

   It overwrites the existing chain instead of appending correctly -> Option A

4. Quick Check:

   Chaining requires appending, not overwriting [OK]

Hint: Traverse chain to append new node, don't overwrite next [OK]

Common Mistakes:

• Ignoring chain traversal
• Assuming single node per bucket
• Not checking for NULL before insertion

5. You want to implement a HashMap from scratch in C that supports integer keys and values, handles collisions using chaining, and dynamically resizes when load factor exceeds 0.7. Which of the following steps is NOT necessary for this implementation?

hard

A. Resize the internal array and rehash all keys when load factor is high

B. Create linked lists at each bucket to handle collisions

C. Implement a hash function to convert keys to indexes

D. Sort the keys in each bucket to speed up search

Solution

1. Step 1: Understand necessary components of HashMap

   A hash function, chaining with linked lists, and resizing with rehashing are all essential for correct and efficient HashMap behavior.

2. Step 2: Evaluate sorting keys in buckets

   Sorting keys in buckets is not required because chaining uses linked lists and search is done by traversing nodes. Sorting adds unnecessary overhead.

3. Final Answer:

   Sort the keys in each bucket to speed up search -> Option D

4. Quick Check:

   Sorting buckets is unnecessary in chaining [OK]

Hint: Chaining uses linked lists; sorting buckets is extra work [OK]

Common Mistakes:

• Thinking sorting improves chaining search
• Ignoring rehashing on resize
• Skipping collision handling