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.