# Separate Chaining | Collision Resolution Techniques

Spread the love

## Hashing in Data Structure-

Before you go through this article, make sure that you have gone through the previous article on Hashing.

We have discussed-

• Hashing is a well-known searching technique.
• It minimizes the number of comparisons while performing the search.
• It completes the search with constant time complexity O(1).

In this article, we will discuss about Collisions in Hashing.

## Collision in Hashing-

In hashing,

• Hash function is used to compute the hash value for a key.
• Hash value is then used as an index to store the key in the hash table.
• Hash function may return the same hash value for two or more keys.

 When the hash value of a key maps to an already occupied bucket of the hash table, it is called as a Collision.

## Collision Resolution Techniques-

 Collision Resolution Techniques are the techniques used for resolving or handling the collision.

Collision resolution techniques are classified as-

1. Separate Chaining
2. Open Addressing

In this article, we will discuss about separate chaining.

## Separate Chaining-

To handle the collision,

• This technique creates a linked list to the slot for which collision occurs.
• The new key is then inserted in the linked list.
• These linked lists to the slots appear like chains.
• That is why, this technique is called as separate chaining.

## Time Complexity-

### For Searching-

• In worst case, all the keys might map to the same bucket of the hash table.
• In such a case, all the keys will be present in a single linked list.
• Sequential search will have to be performed on the linked list to perform the search.
• So, time taken for searching in worst case is O(n).

### For Deletion-

• In worst case, the key might have to be searched first and then deleted.
• In worst case, time taken for searching is O(n).
• So, time taken for deletion in worst case is O(n).

## Load Factor (α)-

Load factor (α) is defined as-

If Load factor (α) = constant, then time complexity of Insert, Search, Delete = Θ(1)

## Problem-

Using the hash function ‘key mod 7’, insert the following sequence of keys in the hash table-

50, 700, 76, 85, 92, 73 and 101

Use separate chaining technique for collision resolution.

## Solution-

The given sequence of keys will be inserted in the hash table as-

### Step-01:

• Draw an empty hash table.
• For the given hash function, the possible range of hash values is [0, 6].
• So, draw an empty hash table consisting of 7 buckets as-

### Step-02:

• Insert the given keys in the hash table one by one.
• The first key to be inserted in the hash table = 50.
• Bucket of the hash table to which key 50 maps = 50 mod 7 = 1.
• So, key 50 will be inserted in bucket-1 of the hash table as-

### Step-03:

• The next key to be inserted in the hash table = 700.
• Bucket of the hash table to which key 700 maps = 700 mod 7 = 0.
• So, key 700 will be inserted in bucket-0 of the hash table as-

### Step-04:

• The next key to be inserted in the hash table = 76.
• Bucket of the hash table to which key 76 maps = 76 mod 7 = 6.
• So, key 76 will be inserted in bucket-6 of the hash table as-

### Step-05:

• The next key to be inserted in the hash table = 85.
• Bucket of the hash table to which key 85 maps = 85 mod 7 = 1.
• Since bucket-1 is already occupied, so collision occurs.
• Separate chaining handles the collision by creating a linked list to bucket-1.
• So, key 85 will be inserted in bucket-1 of the hash table as-

### Step-06:

• The next key to be inserted in the hash table = 92.
• Bucket of the hash table to which key 92 maps = 92 mod 7 = 1.
• Since bucket-1 is already occupied, so collision occurs.
• Separate chaining handles the collision by creating a linked list to bucket-1.
• So, key 92 will be inserted in bucket-1 of the hash table as-

### Step-07:

• The next key to be inserted in the hash table = 73.
• Bucket of the hash table to which key 73 maps = 73 mod 7 = 3.
• So, key 73 will be inserted in bucket-3 of the hash table as-

### Step-08:

• The next key to be inserted in the hash table = 101.
• Bucket of the hash table to which key 101 maps = 101 mod 7 = 3.
• Since bucket-3 is already occupied, so collision occurs.
• Separate chaining handles the collision by creating a linked list to bucket-3.
• So, key 101 will be inserted in bucket-3 of the hash table as-

To gain better understanding about Separate Chaining,

Watch this Video Lecture

Next Article- Open Addressing

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Summary
Article Name
Separate Chaining | Collision Resolution Techniques
Description
Collision Resolution Techniques in data structure are the techniques used for handling collision in hashing. Separate Chaining is a collision resolution technique that handles collision by creating a linked list to the bucket of hash table for which collision occurs.
Author
Publisher Name
Gate Vidyalay
Publisher Logo

Spread the love