Collision Handling Using Chaining in DSA C - Build from Scratch

Collision Handling Using Chaining

📖 Scenario: Imagine you are building a simple phone book application that stores names and phone numbers. To quickly find a phone number by name, you use a hash table. Sometimes, two names might get the same spot in the table (a collision). To handle this, you will use chaining, which means each spot in the table holds a list of entries.

🎯 Goal: You will create a hash table with chaining to store and handle collisions of phone book entries. You will add entries and then print the table to see how collisions are handled.

📋 What You'll Learn

Create a hash table with 3 buckets using an array of linked lists

Define a struct for phone book entries with name and phone number

Implement a simple hash function that maps names to bucket indices

Insert entries into the hash table using chaining for collisions

Print the hash table showing all entries in each bucket

💡 Why This Matters

🌍 Real World

Hash tables with chaining are used in many applications like databases, caches, and phone books to quickly find data even when collisions happen.

💼 Career

Understanding collision handling is important for software engineers working on efficient data storage, retrieval systems, and performance optimization.

1

Create the phone book entry struct and hash table array

Define a struct called Entry with char name[20], char phone[15], and a pointer next to another Entry. Then create an array called hashTable of size 3 that holds pointers to Entry.

DSA C

// Define struct Entry and create hashTable array
// Your code here

Hint

Use typedef struct Entry to define the entry. Initialize hashTable with NULLs.

2

Create a hash function to map names to bucket indices

Write a function called hash that takes a char* called name and returns an int. The function should sum the ASCII values of the characters in name and return the sum modulo 3.

DSA C

#include 
#include 
#include 

typedef struct Entry {
    char name[20];
    char phone[15];
    struct Entry* next;
} Entry;

Entry* hashTable[3] = {NULL, NULL, NULL};

// Write the hash function below
// Your code here

Hint

Loop through each character in name, add its ASCII value to sum, then return sum % 3.

3

Insert entries into the hash table using chaining

Write a function called insert that takes char* name and char* phone. It should create a new Entry, copy the name and phone, compute the bucket index using hash, and insert the new entry at the start of the linked list in hashTable at that index.

DSA C

#include 
#include 
#include 

typedef struct Entry {
    char name[20];
    char phone[15];
    struct Entry* next;
} Entry;

Entry* hashTable[3] = {NULL, NULL, NULL};

int hash(char* name) {
    int sum = 0;
    for (int i = 0; name[i] != '\0'; i++) {
        sum += name[i];
    }
    return sum % 3;
}

// Write the insert function below
// Your code here

Hint

Create a new entry with malloc, copy the strings, find the bucket with hash, and insert at the front of the list.

4

Print the hash table showing all entries in each bucket

Write a function called printHashTable that loops over each bucket index from 0 to 2. For each bucket, print Bucket i: and then traverse the linked list printing each entry as name -> phone. Finally, call insert to add these entries: ("Alice", "123"), ("Bob", "456"), ("Clara", "789"), ("David", "321"), and then call printHashTable.

DSA C

#include 
#include 
#include 

typedef struct Entry {
    char name[20];
    char phone[15];
    struct Entry* next;
} Entry;

Entry* hashTable[3] = {NULL, NULL, NULL};

int hash(char* name) {
    int sum = 0;
    for (int i = 0; name[i] != '\0'; i++) {
        sum += name[i];
    }
    return sum % 3;
}

void insert(char* name, char* phone) {
    Entry* newEntry = (Entry*)malloc(sizeof(Entry));
    strcpy(newEntry->name, name);
    strcpy(newEntry->phone, phone);
    int index = hash(name);
    newEntry->next = hashTable[index];
    hashTable[index] = newEntry;
}

// Write printHashTable function and main calls below
// Your code here

Hint

Loop through each bucket, print the bucket number, then print each entry in the linked list. Insert the given entries before printing.