Collision Handling Using Chaining in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of inserting keys in a chained hash table

What is the printed state of the hash table after inserting keys 10, 22, 31, 4, 15, 28, 17, 88, 59 using chaining with hash function h(key) = key % 10?

DSA C

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

Node* hashTable[10] = {NULL};

void insert(int key) {
    int index = key % 10;
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

void printTable() {
    for (int i = 0; i < 10; i++) {
        printf("%d: ", i);
        Node* temp = hashTable[i];
        while (temp) {
            printf("%d -> ", temp->key);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    int keys[] = {10, 22, 31, 4, 15, 28, 17, 88, 59};
    int n = sizeof(keys)/sizeof(keys[0]);
    for (int i = 0; i < n; i++) {
        insert(keys[i]);
    }
    printTable();
    return 0;
}

A

0: 10 -> NULL
1: 31 -> 41 -> NULL
2: 22 -> NULL
3: NULL
4: 4 -> NULL
5: 15 -> NULL
6: NULL
7: 17 -> NULL
8: 88 -> 28 -> NULL
9: 59 -> NULL

B

0: 10 -> NULL
1: 31 -> NULL
2: 22 -> NULL
3: NULL
4: 4 -> NULL
5: 15 -> NULL
6: NULL
7: 17 -> NULL
8: 28 -> 88 -> NULL
9: 59 -> NULL

C

0: 10 -> NULL
1: 31 -> NULL
2: 22 -> NULL
3: NULL
4: 4 -> NULL
5: 15 -> NULL
6: NULL
7: 17 -> NULL
8: 88 -> 28 -> NULL
9: 59 -> NULL

D

0: 10 -> NULL
1: 31 -> NULL
2: 22 -> NULL
3: NULL
4: 4 -> NULL
5: 15 -> NULL
6: NULL
7: 17 -> NULL
8: 88 -> NULL
9: 59 -> NULL

💡 Hint

Remember that new nodes are inserted at the head of the linked list for each bucket.

The hash function is key % 10. Each key is inserted at the head of the linked list at the computed index. For example, 28 and 88 both hash to 8. Since 88 is inserted after 28, it becomes the new head, so the list at index 8 is 88 -> 28 -> NULL.

🧠 Conceptual

intermediate

Number of items in a chained hash table bucket

If a hash table uses chaining and the hash function distributes keys uniformly, what is the expected number of items in each bucket after inserting n keys into a table with m buckets?

A m / n

B n / m

C n * m

D n + m

💡 Hint

Think about how keys are spread evenly across buckets.

If keys are uniformly distributed, each bucket gets about n/m keys on average.

🔧 Debug

advanced

Identify the bug in chaining insertion code

What error will this code cause when inserting keys into a chained hash table? Code snippet: void insert(int key) { int index = key % 10; Node* newNode = (Node*)malloc(sizeof(Node)); newNode->key = key; newNode->next = NULL; if (hashTable[index] == NULL) { hashTable[index] = newNode; } else { Node* temp = hashTable[index]; while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; } } Assume hashTable is an array of Node* initialized to NULL.

A No error; code inserts at the end of the chain correctly.

B Memory leak due to not freeing nodes.

C Segmentation fault due to uninitialized hashTable array.

D Infinite loop in while condition.

💡 Hint

Check how the linked list is traversed and where the new node is added.

The code correctly inserts new nodes at the end of the linked list for the bucket. The hashTable array is assumed initialized to NULL, so no segmentation fault. No infinite loop occurs because the loop stops at last node. Memory leak is unrelated to insertion logic.

❓ Predict Output

advanced

Output after deleting a key from chained hash table

Given the hash table with chaining below, what is the printed state after deleting key 15? Initial state: 0: 10 -> NULL 1: 31 -> NULL 2: 22 -> NULL 3: NULL 4: 4 -> NULL 5: 15 -> 25 -> NULL 6: NULL 7: 17 -> NULL 8: 88 -> 28 -> NULL 9: 59 -> NULL Deletion code removes the first occurrence of key 15 in the chain at index 5.

DSA C

void deleteKey(int key) {
    int index = key % 10;
    Node* temp = hashTable[index];
    Node* prev = NULL;
    while (temp != NULL && temp->key != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return; // key not found
    if (prev == NULL) {
        hashTable[index] = temp->next;
    } else {
        prev->next = temp->next;
    }
    free(temp);
}

// After calling deleteKey(15), printTable() is called.

A 5: 15 -> 25 -> NULL

B 5: NULL

C 5: 25 -> 15 -> NULL

D 5: 25 -> NULL

💡 Hint

Deleting key 15 removes the first node with key 15 in the chain.

Key 15 is at the head of the chain at index 5. After deletion, the head points to the next node with key 25.

🧠 Conceptual

expert

Why chaining is preferred over open addressing in high load factor scenarios

Why is chaining often preferred over open addressing when the hash table load factor is high (close to or greater than 1)?

A Chaining allows unlimited number of elements per bucket, avoiding clustering and performance degradation.

B Open addressing uses linked lists internally, which are slower than arrays.

C Chaining requires less memory than open addressing at high load factors.

D Open addressing cannot handle collisions at all.

💡 Hint

Think about how collisions are handled and how performance changes as table fills up.

Chaining stores collided keys in linked lists, so it can handle many keys per bucket without performance dropping drastically. Open addressing suffers from clustering and long probe sequences at high load factors.