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