C Programming Data Structures Collision Handling Chaining Open Addressing Complete Guide

 Last Update:2025-06-23T00:00:00     .NET School AI Teacher - SELECT ANY TEXT TO EXPLANATION.    10 mins read      Difficulty-Level: beginner

Understanding the Core Concepts of C Programming data structures Collision Handling Chaining, Open Addressing

C Programming Data Structures: Collision Handling Methods - Chaining and Open Addressing

Chaining

Chaining is a simple yet effective method to handle collisions in hash tables. The idea behind chaining is to maintain multiple entries for a given hash value by storing them in a linked list. Each index of the hash table points to a node of a linked list containing all the elements that hash to the same value.

Key Components and Implementation:

  • Linked List: Each index in the hash table points to a linked list of elements (nodes) that map to the same hash value.
  • Insertion: Adding a new element involves computing its hash value and inserting it into the corresponding linked list.
  • Search: To search for an element, compute its hash and traverse the linked list starting from the index of the hash value.
  • Deletion: Compute the hash value and remove the element from the linked list.

Advantages:

  • Simple Implementation: Chaining is straightforward to implement using linked lists.
  • Efficient Handling of Collisions: With a good hash function, the linked lists remain short, ensuring efficient operations.
  • Dynamic Allocation: Memory can be dynamically allocated for elements, and the hash table can grow as new elements are added.

Disadvantages:

  • Memory Overhead: Linked lists have more overhead due to storing pointers and additional metadata.
  • Increased Memory Usage: Chaining can lead to higher memory usage due to storing node pointers.

Example:

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

#define SIZE 10

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

struct HashTable {
    struct Node* table[SIZE];
};

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

void insert(struct HashTable* ht, int key) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->key = key;
    newNode->next = NULL;

    unsigned int index = hash(key);

    // Insert at the beginning of the list
    newNode->next = ht->table[index];
    ht->table[index] = newNode;
}

void display(struct HashTable* ht) {
    for (int i = 0; i < SIZE; i++) {
        printf("Index %d: ", i);
        struct Node* temp = ht->table[i];
        while (temp != NULL) {
            printf("%d -> ", temp->key);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    struct HashTable ht = {0};  // Initialize hash table with NULL
    insert(&ht, 15);
    insert(&ht, 11);
    insert(&ht, 27);
    insert(&ht, 8);
    insert(&ht, 34);
    display(&ht);
    return 0;
}

Open Addressing

Open Addressing aims to store all elements directly within the hash table itself by finding another empty slot within the table when a collision occurs. This method does not use any additional data structures like linked lists.

Key Components and Implementation:

  • Probing Mechanism: When a collision occurs (hash value already occupied), the algorithm searches for the next available slot using a probing sequence (e.g., linear probing, quadratic probing, double hashing).
  • Insertion: Similar to chaining, but if the computed index is occupied, the algorithm finds another index based on the probing technique.
  • Search: Compute the hash value and follow the same probing sequence used during insertion to find the element.
  • Deletion: Similar to search, but once the element is found, mark the spot with a special marker indicating the slot is logically vacant but cannot be used for new insertions.

Advantages:

  • No Pointers: No additional pointers are required, resulting in less memory overhead.
  • Cache Efficiency: Elements are stored in contiguous memory locations, enhancing cache performance.

Disadvantages:

  • Clustering: Repeated collisions can cause long sequences of occupied slots, degrading performance.
  • Complexity: Implementing effective probing methods can be complex, especially in scenarios where the hash table is nearly full.

Types of Probing:

  1. Linear Probing: Check the next slot in the table (i.e., (index + 1) % size) until an empty slot is found.
  2. Quadratic Probing: Use a quadratic function to calculate the next slot (i.e., (index + c1i + c2i^2) % size).
  3. Double Hashing: Use a secondary hash function to determine the step size (i.e., (index + i*secondaryHash(key)) % size).

Example:

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

#define SIZE 10

struct HashTable {
    int table[SIZE];
};

void initHashTable(struct HashTable* ht) {
    for (int i = 0; i < SIZE; i++)
        ht->table[i] = INT_MIN;
}

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

unsigned int linearProbe(struct HashTable* ht, unsigned int index) {
    int i = 1;
    while (ht->table[(index + i) % SIZE] != INT_MIN)
        i++;
    return (index + i) % SIZE;
}

void insert(struct HashTable* ht, int key) {
    unsigned int index = hash(key);
    if (ht->table[index] != INT_MIN) {
        index = linearProbe(ht, index);
    }
    ht->table[index] = key;
}

void display(struct HashTable* ht) {
    for (int i = 0; i < SIZE; i++) {
        if (ht->table[i] != INT_MIN)
            printf("Index %d: %d\n", i, ht->table[i]);
        else
            printf("Index %d: EMPTY\n", i);
    }
}

int main() {
    struct HashTable ht;
    initHashTable(&ht);
    insert(&ht, 25);
    insert(&ht, 15);
    insert(&ht, 35);
    insert(&ht, 45);
    insert(&ht, 55);
    display(&ht);
    return 0;
}

Conclusion

Collision handling is a critical aspect of hash tables, essential for ensuring efficient data manipulation. Chaining and Open Addressing offer distinct advantages and trade-offs in terms of implementation complexity, memory usage, and performance. Chaining provides a simple, flexible solution using linked lists, albeit with higher memory overhead. In contrast, Open Addressing avoids pointers but can suffer from performance issues due to clustering. Understanding these methods and their implications empowers developers to choose the best suited technique based on their specific application requirements.

Online Code run

🔔 Note: Select your programming language to check or run code at

💻 Run Code Compiler

Step-by-Step Guide: How to Implement C Programming data structures Collision Handling Chaining, Open Addressing

Collision Handling in Hash Tables

Collision handling is a crucial aspect of hash tables because when you insert a key into a hash table, it might already be occupied by another key, resulting in a collision. There are two primary methods to handle collisions:

  1. Chaining
  2. Open Addressing

Method 1: Collision Handling using Chaining

Chaining is a method where each slot of the hash table points to a linked list (or some other data structure) of entries that have the same hash value.

Example: Implementing Chaining in C

Let's implement a simple hash table with chaining in C:

  1. Define the Node and Hash Table Structures:
#include <stdio.h>
#include <stdlib.h>

#define TABLE_SIZE 10

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

typedef struct HashTable {
    Node* array[TABLE_SIZE];
} HashTable;

// Function to initialize the hash table
void initHashTable(HashTable* table) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        table->array[i] = NULL;
    }
}

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

// Function to insert a key in the hash table
void insert(HashTable* table, int key) {
    int index = hash(key);
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = key;
    newNode->next = table->array[index];
    table->array[index] = newNode;
}

// Function to search for a key in the hash table
Node* search(HashTable* table, int key) {
    int index = hash(key);
    Node* temp = table->array[index];
    while (temp) {
        if (temp->data == key) {
            return temp;
        }
        temp = temp->next;
    }
    return NULL;
}

// Function to delete a key from the hash table
void delete(HashTable* table, int key) {
    int index = hash(key);
    Node* temp = table->array[index];
    Node* prev = NULL;
    
    while (temp) {
        if (temp->data == key) {
            if (prev) {
                prev->next = temp->next;
            } else {
                table->array[index] = temp->next;
            }
            free(temp);
            return;
        }
        prev = temp;
        temp = temp->next;
    }
}

// Function to display the hash table
void display(HashTable* table) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        printf("Index %d: ", i);
        Node* temp = table->array[i];
        while (temp) {
            printf("%d -> ", temp->data);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    HashTable table;
    initHashTable(&table);

    insert(&table, 10);
    insert(&table, 20);
    insert(&table, 15); // Collision! (same hash as 10)
    insert(&table, 33);
    insert(&table, 25); // Collision! (same hash as 15)

    display(&table);

    Node* result = search(&table, 15);
    if (result) {
        printf("Key 15 found\n");
    } else {
        printf("Key 15 not found\n");
    }

    delete(&table, 15);
    result = search(&table, 15);
    if (result) {
        printf("Key 15 found\n");
    } else {
        printf("Key 15 not found\n");
    }

    display(&table);

    return 0;
}

Method 2: Collision Handling using Open Addressing

Open Addressing is a method where all elements are stored in the hash table itself. If the desired position for a key is occupied, the hash function is applied again to find another position.

There are different variations of open addressing:

  • Linear Probing: Move to the next slot, then the next, and so on until you find an empty slot.
  • Quadratic Probing: Move to the next slot by adding 1^2, then 2^2, then 3^2, and so on.
  • Double Hashing: Use a second hash function to calculate the step size.

Example: Implementing Linear Probing in C

Let's implement a simple hash table with linear probing in C:

  1. Define the Hash Table Structure:
#include <stdio.h>
#include <stdlib.h>

#define TABLE_SIZE 10

typedef struct HashTable {
    int array[TABLE_SIZE];
} HashTable;

// Function to initialize the hash table
void initHashTable(HashTable* table) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        table->array[i] = -1; // Mark as empty
    }
}

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

// Linear Probing function
int linearProbe(HashTable* table, int key) {
    int index = hash(key);
    for (int i = 1; i < TABLE_SIZE; i++) {
        if (table->array[index] == -1) return index; // Found an empty slot
        index = (index + 1) % TABLE_SIZE; // Linear probing
    }
    return -1; // Hash table is full
}

// Function to insert a key in the hash table
void insert(HashTable* table, int key) {
    int index = linearProbe(table, key);
    if (index != -1) {
        table->array[index] = key;
    } else {
        printf("Hash Table Full\n");
    }
}

// Function to search for a key in the hash table
int search(HashTable* table, int key) {
    int index = hash(key);
    for (int i = 1; i < TABLE_SIZE; i++) {
        if (table->array[index] == key) return index; // Key found
        if (table->array[index] == -1) return -1;  // Key not found
        index = (index + 1) % TABLE_SIZE; // Linear probing
    }
    return -1; // Key not found
}

// Function to delete a key from the hash table
void delete(HashTable* table, int key) {
    int index = search(table, key);
    if (index != -1) {
        table->array[index] = -1; // Mark as deleted
    } else {
        printf("Key not found\n");
    }
}

// Function to display the hash table
void display(HashTable* table) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        if (table->array[i] == -1) {
            printf("Index %d: Empty\n", i);
        } else {
            printf("Index %d: %d\n", i, table->array[i]);
        }
    }
}

int main() {
    HashTable table;
    initHashTable(&table);

    insert(&table, 10);
    insert(&table, 20);
    insert(&table, 15); // Collision! (same hash as 10)
    insert(&table, 33);
    insert(&table, 25); // Collision! (same hash as 15)

    display(&table);

    int index = search(&table, 15);
    if (index != -1) {
        printf("Key 15 found at index %d\n", index);
    } else {
        printf("Key 15 not found\n");
    }

    delete(&table, 15);
    index = search(&table, 15);
    if (index != -1) {
        printf("Key 15 found at index %d\n", index);
    } else {
        printf("Key 15 not found\n");
    }

    display(&table);

    return 0;
}

Explanation

  1. Chaining Example:

    • Structures: Node for linked list elements and HashTable for storing pointers to linked lists.
    • Functions: initHashTable, hash, insert, search, delete, and display.
    • Hash Function: Simple modulo operation based on the key.
    • Collision Handling: If a collision occurs (same hash value), a new node is added to the linked list at that index.

  2. Linear Probing Example:

    • Structures: HashTable for storing key values.
    • Functions: initHashTable, hash, linearProbe, insert, search, delete, and display.
    • Hash Function: Simple modulo operation based on the key.
    • Collision Handling: If a collision occurs, the probing shifts to the next index until an empty slot is found.

Top 10 Interview Questions & Answers on C Programming data structures Collision Handling Chaining, Open Addressing

1. What is a Hash Table in C?

Answer: A hash table is a data structure that maps keys to values for efficient data retrieval. In C, a hash table is typically implemented using an array where each element points to a linked list (in case of chaining) or stores data directly (in case of open addressing).

2. What is Chaining in Hash Tables?

Answer: Chaining is a collision resolution technique where each bucket in the hash table is a linked list (or another data structure). If two keys hash to the same bucket, they are stored in the same linked list sequentially.

3. How is Chaining implemented in C?

Answer: In C, chaining can be implemented using an array of pointers to linked list nodes. Here’s a simple example:

#define TABLE_SIZE 10

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

Node* hashTable[TABLE_SIZE];

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

4. What is Open Addressing in Hash Tables?

Answer: Open addressing is a collision resolution scheme where all keys are stored in the hash table itself. When a collision occurs, the hash table is probed for the next available slot according to a probing sequence.

5. What are the types of Open Addressing in Hash Tables?

Answer: The main types of open addressing include:

  • Linear Probing: Checks the next slot sequentially.
  • Quadratic Probing: Checks slots quadratic distances apart.
  • Double Hashing: Uses a secondary hash function to determine the interval between probes.

6. How is Linear Probing implemented in C?

Answer: Linear probing checks the next slot sequentially. Here’s a simple example:

void insertLinearProbing(int key) {
    int index = key % TABLE_SIZE;
    int originalIndex = index;

    do {
        if (hashTable[index] == NULL) {
            Node* node = (Node*)malloc(sizeof(Node));
            node->key = key;
            node->next = NULL;
            hashTable[index] = node;
            return;
        }
        index = (index + 1) % TABLE_SIZE;
    } while (index != originalIndex);
}

7. What is the difference between Chaining and Open Addressing?

Answer: Chaining deals with collisions by using linked lists at each bucket, while open addressing stores all entries in the hash table itself by probing for the next available slot.

8. What are the advantages of using Chaining?

Answer: Advantages of chaining include simple implementation, efficient insertions and deletions, and the ability to handle an arbitrary number of collisions.

9. What are the advantages of using Open Addressing?

Answer: Advantages of open addressing include less space overhead (no need for pointers for linked lists), and it can be cache-friendly as it stores all elements in a contiguous block of memory.

10. What are the use cases for choosing Chaining over Open Addressing?

Answer: Chaining is preferred when:

  • The number of keys is significantly large or unpredictable.
  • The memory overhead for pointers is acceptable.
  • Efficient dynamic resizing of the hash table is needed.

You May Like This Related .NET Topic

📥 Download Code ▶️ Watch Online 📖 Read Description

Login to post a comment.