Bird
Raised Fist0
CDebug / FixBeginner · 4 min read

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.