# 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

Insertion complexity = O(1)
```

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

• 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;
}
};

{
}

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

{

cout << "NULL\n";
return;
}
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
```