Home » Data Structure

Hashing | Separate chaining for collision resolution

Separate chaining for collision resolution: In this article, we will discuss how we can use separate chaining method for collision resolving?
Submitted by Radib Kar, on July 01, 2020

Prerequisite: Hashing data structure

Separate chaining

In separate chaining, we maintain a linked chain for every index in the hash table. So whenever there is a Collison the linked list is extended for that particular location of the hash table.

We can visualize the separate chaining method with the following example,

Key set: {123, 456, 763, 656, 908, 238, 231}
Hash function: f(x) = x%10

Step 1: Inserting 123 in the hash map. So, location is 3.

Index	keys
0	NULL
1	NULL
2	NULL
3	123->NULL
4	NULL
5	NULL
6	NULL
7	NULL
8	NULL
9	NULL

Step 2: Inserting 456 in the hash map. So, location is 3.

Index	keys
0	NULL
1	NULL
2	NULL
3	123->NULL
4	NULL
5	NULL
6	456->NULL
7	NULL
8	NULL
9	NULL

Step 3: Inserting 763 in the hash map. So, location is 3.

Index	keys
0	NULL
1	NULL
2	NULL
3	123->763->NULL
4	NULL
5	NULL
6	456->NULL
7	NULL
8	NULL
9	NULL

Step 4: Inserting 656 in the hash map. So, location is 6.

Index	Keys
0	NULL
1	NULL
2	NULL
3	123->763->NULL
4	NULL
5	NULL
6	456->656->NULL
7	NULL
8	NULL
9	NULL

Step 5: Inserting 908 in the hash map. So, location is 8.

Index	Keys
0	NULL
1	NULL
2	NULL
3	123->763->NULL
4	NULL
5	NULL
6	456->656->NULL
7	NULL
8	908->NULL
9	NULL

Step 6: Inserting 238 in the hash map. So, location is 8.

Index	Keys
0	NULL
1	NULL
2	NULL
3	123->763->NULL
4	NULL
5	NULL
6	456->656->NULL
7	NULL
8	908->238->NULL
9	NULL

Step 7: Inserting 231 in the hash map. So, location is 8.

Index	Keys
0	NULL
1	231->NULL
2	NULL
3	123->763->NULL
4	NULL
5	NULL
6	456->656->NULL
7	NULL
8	908->238->NULL
9	NULL

So, the above thing is called as separate chaining as we have chained the collided elements within the hash table.

Performance analysis:

Load factor = n/m, 
    n = number of keys inserted, 
    m = number of indices in the hash table() size of hash table

Search complexity = O(load factor)
Insertion complexity = O(1)
Deletion complexity = O(load factor)

Advantage and disadvantages of separate chaining

Advantages are,

• We can add as many keys as we want to add
• It's simpler than open addressing to implement

Disadvantages are,

• It uses extra spaces for links
• If the collision rate is high, the search complexity increases as load factor increases

C++ implementation of separate chaining

//separate chaining
#include <bits/stdc++.h>
using namespace std;

class node {
public:
    int data;
    node* next;

    node()
    {
        data = 0;
        next = NULL;
    }
    node(int x)
    {
        data = x;
        next = NULL;
    }
};

node* add(node* head, int data)
{
    if (head == NULL) {
        head = new node(data);
        return head;
    }

    node* temp = head;
    while (temp->next) {
        temp = temp->next;
    }
    temp->next = new node(data);
    return head;
}

void print(node* head)
{

    if (!head) {
        cout << "NULL\n";
        return;
    }
    node* temp = head;
    while (temp) {
        cout << temp->data << "->";
        temp = temp->next;
    }
    cout << "NULL\n";
}

int main()
{
    //set of input numbers
    vector<int> arr{ 123, 456, 763, 656, 908, 238, 231 };

    //initialize the hash table
    //each entry of the hash table is a linkedlist
    vector<node*> hash(10); //size of hashtable is 10

    //using hash function f(x)=no of digits in x
    for (int a : arr) {
        hash[a % 10] = add(hash[a % 10], a);
    }

    cout << "Hash table is:\n";
    for (int i = 0; i < 10; i++) {
        cout << i << "---- ";
        print(hash[i]);
    }

    return 0;
}

Output:

Hash table is:
0---- NULL
1---- 231->NULL
2---- NULL
3---- 123->763->NULL
4---- NULL
5---- NULL
6---- 456->656->NULL
7---- NULL
8---- 908->238->NULL
9---- NULL