Separate Chaining Collision Technique

Separate Chaining is a collision resolution technique used in hash tables. When two different keys hash to the same index (collision), separate chaining handles this by storing all elements that hash to the same value in a linked list at that index.

Think of it like a parking lot where each parking spot can hold multiple cars by stacking them vertically you can always add more cars to the same spot without moving others.

Key Concept

• Each slot of the hash table is a pointer to a linked list.
• This linked list contains all key-value pairs that are hashed to the same location.
• It is otherwise called as direct chaining or simply chaining.

How Separate Chaining Handles Collisions

1. When a collision occurs, this technique creates a linked list for that slot.
2. The new key is then inserted into the linked list.
3. These linked lists attached to the slots appear like chains.
4. That is why this technique is called separate chaining.

How Separate Chaining Works?

Using the hash function h(key) = key mod 7, insert the following sequence of keys into a hash table: 50, 700, 76, 85, 92, 73, 101

Step 1: Initialize the Hash Table

• For the given hash function key mod 7, the possible range of hash values is [0, 6].
• Draw an empty hash table consisting of 7 buckets (index 0 to 6).

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

Step 2: Insert Key 50

• Calculate hash: 50 mod 7 = 1
• Bucket 1 is empty → Insert 50 directly.

Index 0: NULL
Index 1: 50 → NULL
Index 2: NULL
Index 3: NULL
Index 4: NULL
Index 5: NULL
Index 6: NULL

Step 3: Insert Key 700

• Calculate hash: 700 mod 7 = 0
• Bucket 0 is empty → Insert 700 directly.

Index 0: 700 → NULL
Index 1: 50 → NULL
Index 2: NULL
Index 3: NULL
Index 4: NULL
Index 5: NULL
Index 6: NULL

Step 4: Insert Key 76

• Calculate hash: 76 mod 7 = 6
• Bucket 6 is empty → Insert 76 directly.

Index 0: 700 → NULL
Index 1: 50 → NULL
Index 2: NULL
Index 3: NULL
Index 4: NULL
Index 5: NULL
Index 6: 76 → NULL

Step 5: Insert Key 85 (Collision Occurs!)

• Calculate hash: 85 mod 7 = 1
• Bucket 1 is already occupied by 50 → Collision!
• Separate chaining handles this by creating a linked list at bucket 1.
• Insert 85 at the beginning or end of the chain (we'll insert at the beginning for simplicity).

Index 0: 700 → NULL
Index 1: 85 → 50 → NULL   (85 added to the chain)
Index 2: NULL
Index 3: NULL
Index 4: NULL
Index 5: NULL
Index 6: 76 → NULL

Step 6: Insert Key 92 (Another Collision)

• Calculate hash: 92 mod 7 = 1
• Bucket 1 already has a chain → Insert 92 at the beginning.

Index 0: 700 → NULL
Index 1: 92 → 85 → 50 → NULL
Index 2: NULL
Index 3: NULL
Index 4: NULL
Index 5: NULL
Index 6: 76 → NULL

Step 7: Insert Key 73

• Calculate hash: 73 mod 7 = 3
• Bucket 3 is empty → Insert 73 directly.

Index 0: 700 → NULL
Index 1: 92 → 85 → 50 → NULL
Index 2: NULL
Index 3: 73 → NULL
Index 4: NULL
Index 5: NULL
Index 6: 76 → NULL

Step 8: Insert Key 101 (Collision at Bucket 3)

• Calculate hash: 101 mod 7 = 3
• Bucket 3 already has 73 → Insert 101 at the beginning of the chain.

Index 0: 700 → NULL
Index 1: 92 → 85 → 50 → NULL
Index 2: NULL
Index 3: 101 → 73 → NULL
Index 4: NULL
Index 5: NULL
Index 6: 76 → NULL

Final Hash Table

The final hash table with separate chaining looks like this:

Index 0: 700 → NULL
Index 1: 92 → 85 → 50 → NULL
Index 2: NULL
Index 3: 101 → 73 → NULL
Index 4: NULL
Index 5: NULL
Index 6: 76 → NULL

Algorithm for Separate Chaining

Insertion Algorithm

Algorithm: ChainedHashInsert(T, key)
Input:  T - Hash table (array of linked lists)
        key - Key to insert
Output: None

Step 1: START
Step 2: index = h(key)    // Compute hash value
Step 3: Create a new node with the key
Step 4: Insert the new node at the beginning of T[index]
Step 5: END

Search Algorithm

text

Algorithm: ChainedHashSearch(T, key) Input:  T - Hash table (array of linked lists)        key - Key to search Output: True if key found, False otherwise Step 1: START Step 2: index = h(key)    // Compute hash value Step 3: Traverse the linked list at T[index] Step 4: IF key found in the list THEN Step 5:     RETURN True Step 6: RETURN False Step 7: END

Implementation in C Programming

#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 7

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

// Hash table (array of pointers to Node)
Node* hashTable[TABLE_SIZE];

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

// Insert key using separate chaining
void insert(int key) {
    int index = hashFunction(key);
    
    // Create new node
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = key;
    newNode->next = NULL;
    
    // If the bucket is empty, insert directly
    if (hashTable[index] == NULL) {
        hashTable[index] = newNode;
    } else {
        // Insert at the beginning of the chain
        newNode->next = hashTable[index];
        hashTable[index] = newNode;
    }
    printf("Inserted %d at index %d (chain)\n", key, index);
}

// Search for a key
int search(int key) {
    int index = hashFunction(key);
    Node* current = hashTable[index];
    int position = 0;
    
    while (current != NULL) {
        if (current->data == key) {
            printf("Key %d found at index %d, position %d in chain\n", key, index, position);
            return index;
        }
        current = current->next;
        position++;
    }
    printf("Key %d not found\n", key);
    return -1;
}

// Display the hash table
void display() {
    printf("\nHash Table (Separate Chaining):\n");
    for (int i = 0; i < TABLE_SIZE; i++) {
        printf("Index %d: ", i);
        Node* current = hashTable[i];
        while (current != NULL) {
            printf("%d → ", current->data);
            current = current->next;
        }
        printf("NULL\n");
    }
}

int main() {
    // Initialize hash table with NULL
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable[i] = NULL;
    }
    
    // Insert keys
    int keys[] = {50, 700, 76, 85, 92, 73, 101};
    int n = sizeof(keys) / sizeof(keys[0]);
    
    for (int i = 0; i < n; i++) {
        insert(keys[i]);
    }
    
    display();
    
    // Search for a key
    search(85);
    search(100);
    
    return 0;
}

Output:

Inserted 50 at index 1 (chain)
Inserted 700 at index 0 (chain)
Inserted 76 at index 6 (chain)
Inserted 85 at index 1 (chain)
Inserted 92 at index 1 (chain)
Inserted 73 at index 3 (chain)
Inserted 101 at index 3 (chain)

Hash Table (Separate Chaining):
Index 0: 700 → NULL
Index 1: 92 → 85 → 50 → NULL
Index 2: NULL
Index 3: 101 → 73 → NULL
Index 4: NULL
Index 5: NULL
Index 6: 76 → NULL

Key 85 found at index 1, position 1 in chain
Key 100 not found

Time and Space Complexity Analysis

Time Complexity

Where α (load factor) = n / m

• n = number of elements
• m = table size

Explanation: In the average case, keys are distributed uniformly, so each chain has approximately α elements. Searching requires scanning the chain, which takes O(α) time. If α is kept small (typically < 1), operations are effectively O(1).

Space Complexity

• O(n + m) where n is the number of elements and m is the table size.
• Extra space is required for the linked list pointers.

Advantages of Separate Chaining

1. Simple Implementation: Easy to understand and implement.
2. Handles Any Number of Collisions: Can store unlimited elements (as long as memory allows).
3. No Clustering: Unlike open addressing, there is no primary or secondary clustering.
4. Efficient for Variable Data: Works well when the number of elements is unknown in advance.
5. Easy Deletion: Deleting an element simply removes it from the linked list.

Disadvantages of Separate Chaining

1. Extra Memory: Requires additional memory for pointers in each node.
2. Cache Inefficiency: Linked lists are not cache-friendly; scattered memory access.
3. Worst-Case Performance: If hash function is poor, all keys may map to the same index, degrading to O(n).
4. Overhead: Traversing linked lists can be slower than open addressing for small loads.

When to Use Separate Chaining

• When memory is not a constraint.
• When the number of elements is highly dynamic (frequent insertions and deletions).
• When you want simple implementation without complex probing logic.
• When the hash function is expected to distribute keys uniformly.

Comparison with Open Addressing

Practice Questions

1. What is separate chaining in hashing? Explain with a suitable example.
2. Compare separate chaining with open addressing. Which is better and why?
3. A hash table has m = 10 slots and uses the hash function h(k) = k mod 10. Insert the following keys using separate chaining: 12, 44, 13, 88, 23, 94, 11, 39, 20, 16.
4. Given a hash table of size m = 7, and the following keys: 50, 700, 76, 85, 92, 73, 101 Using the hash function h(k) = k mod 7, calculate the total number of collisions that occur when using separate chaining.
5. Consider a hash table of size m = 9, with the hash function h(k) = k mod 9. Keys: 18, 41, 22, 44, 59, 32 are inserted using separate chaining.
   1. Find the chain where key 59 is located.
   2. How many comparisons are required to search for 59?