Chaining in Hashing in C: What It Is and How It Works

In C, chaining is a method to handle collisions in hashing by storing multiple elements in a linked list at the same hash index. When two keys hash to the same slot, chaining keeps them in a list so all can be accessed without overwriting.

How It Works

Imagine you have a set of keys and you want to store them in boxes labeled by numbers. Hashing assigns each key a box number using a function. Sometimes, two keys get the same box number, causing a collision.

Chaining solves this by turning each box into a small chain (linked list) where all keys with the same box number are linked together. Instead of one key per box, you have a chain of keys. When you want to find a key, you go to its box and check each key in the chain until you find it.

Example

This example shows a simple hash table using chaining with linked lists in C. It inserts keys and prints the chains for each index.

c

#include <stdio.h>
#include <stdlib.h>

#define TABLE_SIZE 5

// Node for linked list
typedef struct Node {
    int key;
    struct Node* next;
} Node;

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

// Insert key into hash table
void insert(Node* table[], int key) {
    int index = hash(key);
    Node* newNode = malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    newNode->key = key;
    newNode->next = table[index];
    table[index] = newNode;
}

// Print hash table chains
void printTable(Node* table[]) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        printf("Index %d:", i);
        Node* temp = table[i];
        while (temp) {
            printf(" -> %d", temp->key);
            temp = temp->next;
        }
        printf(" -> NULL\n");
    }
}

int main() {
    Node* hashTable[TABLE_SIZE] = {NULL};

    insert(hashTable, 12);
    insert(hashTable, 7);
    insert(hashTable, 22);
    insert(hashTable, 17);
    insert(hashTable, 5);

    printTable(hashTable);

    return 0;
}

Output

Index 0: -> NULL
Index 1: -> 17 -> NULL
Index 2: -> 22 -> NULL
Index 3: -> NULL
Index 4: -> 12 -> 7 -> 5 -> NULL

When to Use

Use chaining in hashing when you expect collisions and want a simple way to store multiple keys at the same index without losing data. It is useful in situations like symbol tables in compilers, caching, or databases where quick lookup and insertion are needed.

Chaining is preferred when the number of collisions is moderate and memory for linked lists is affordable. It keeps operations efficient and easy to implement.

Key Points

• Chaining uses linked lists to handle collisions in hash tables.
• Multiple keys with the same hash index are stored in a chain.
• It allows efficient insertion and search even with collisions.
• Simple to implement and flexible for dynamic data.

Key Takeaways

Chaining stores collided keys in linked lists at the same hash index.

It prevents data loss by allowing multiple keys per slot in a hash table.

Chaining is easy to implement and works well for moderate collisions.

Use chaining when you need efficient lookup and insertion with collisions.

Each hash table index points to a chain of keys, not just one key.