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





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.