How to Handle Collision in Hash Table in C: Simple Fixes

In C, collisions in a hash table happen when two keys map to the same index. To handle this, use chaining by storing collided items in a linked list at that index, or use open addressing by finding another free slot using probing methods like linear probing.

Why This Happens

Collisions occur because a hash function maps multiple keys to the same index in the hash table. Without handling collisions, inserting a new key that hashes to an occupied slot will overwrite existing data or cause errors.

c

#include <stdio.h>
#define SIZE 5

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

int main() {
    int hashTable[SIZE] = {0};
    int keys[] = {1, 6}; // Both keys hash to index 1

    for (int i = 0; i < 2; i++) {
        int index = hash(keys[i]);
        hashTable[index] = keys[i]; // Overwrites previous value
    }

    for (int i = 0; i < SIZE; i++) {
        printf("Index %d: %d\n", i, hashTable[i]);
    }
    return 0;
}

Output

Index 0: 0
Index 1: 6
Index 2: 0
Index 3: 0
Index 4: 0

The Fix

Use chaining to handle collisions by storing collided keys in a linked list at the same index. This way, multiple keys can share one slot without overwriting each other.

c

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

#define SIZE 5

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

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

// Insert key into hash table with chaining
void insert(Node* hashTable[], 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 = hashTable[index];
    hashTable[index] = newNode;
}

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

int main() {
    Node* hashTable[SIZE] = {NULL};
    int keys[] = {1, 6, 11}; // All hash to index 1

    for (int i = 0; i < 3; i++) {
        insert(hashTable, keys[i]);
    }

    printTable(hashTable);
    return 0;
}

Output

Index 0: NULL
Index 1: 11 -> 6 -> 1 -> NULL
Index 2: NULL
Index 3: NULL
Index 4: NULL

Prevention

To avoid collision problems, choose a good hash function that distributes keys evenly. Also, keep the load factor (number of keys / table size) low by resizing the table when it gets full. Use chaining or open addressing methods consistently to handle collisions.

• Use linked lists for chaining.
• Use probing (linear, quadratic) for open addressing.
• Resize and rehash when load factor exceeds 0.7.

Related Errors

Common related errors include:

• Overwriting data without collision handling.
• Infinite loops in open addressing if no free slot is found.
• Memory leaks when not freeing linked list nodes in chaining.

Fix these by implementing proper collision handling, checking for full tables, and freeing memory.

Key Takeaways

Collisions happen when multiple keys map to the same index in a hash table.

Use chaining with linked lists or open addressing with probing to handle collisions.

Choose a good hash function and keep the load factor low to reduce collisions.

Always check for full tables and free memory to avoid errors and leaks.