Types of Hashing in Data Structure

We discussed the Hashing in Data Structure in previous data structure tutorial. In this tutorial we will learn about various types of hashing in data structure.

Hashing based questions are asked in GATE and UGC NET exam are also explained in this tutorial. After reading this tutorial students will be able to attempt the hashing problems asked in previous year GATE Exam.

Let’s start with Types of Hashing or hash techniques.

Two types of hashing in data structure are there

1.Open Hashing (Closed addressing)

Open Hashing is used to avoid collision and this method use an array of linked list to resolve the collision. This method is also known as closed addressing based hashing.

In open hashing it is important to note that each cell of array points to a list that contains collisions. Hashing has produced same index for all item in the linked list.

2.Closed hashing (Open addressing)

In this case there are three methods to resolve the collision which are discussed

Linear probing.
Quadratic probing.
Double hashing.

Chaining in Hashing

Let’s understand the chaining method with the help of one example.

Example: Use division method and closed addressing technique to store these values.

Given Keys=3, 2, 9, 6, 11, 13, 7, 12 and Bucket size is 10.

Solution:

key 11 will be stored in 5^th position, but we already have key 6 in 5^th position. This is the case of collision. In closed addressing technique, we’ll use chaining method, i.e. a linked list will be created and the key 11 will be stored there as shown in the hash table above.

Again at 9^th position we already have key 3. Hence we have to use a linked list at 9^th position to store key 13.

Linear Probing in Hashing

In case of linear probing, we’ll simply search for the location and if the location is available, we’ll store the key into that location.

Let’s understand the linear probing method with the help of one example.

Example: Use division method and open addressing technique to store these values.

Given Keys=3, 2, 9, 6, 11, 13, 7, 12 and Bucket size is 10.

Solution

When we use open addressing technique to store keys into hash tables, by default we need to use linear probing method to resolve collision.

A step wise step solution to deal with collision issue in the above problem is explained here.

Key 11 will be stored in 5^th position, but we already have key 6 in 5^th position. This is the case of collision. In case of linear probing method, we’ll simply search for the next location available.

Here 6^th location is available, hence we’ll store the key 11 in 6^th location. For key 11 we had to search the location 2 times, hence probes=2.

Again at 9^th position we already have key 3. Hence 9^th location is not available. Now we have to search linearly for the next location available which is 0^th location. Hence key 13 will be stored in 0^th location.

Again at 7^th position we already have key 2. Hence 7^th location is not available. Now we have to search linearly for the next location available which is 8^th location. Hence key 7 will be stored in 8^th location.

Again at 7^th position we already have key 2. Hence 7^th location is not available. Now we have to search linearly for the next location available which is 2^ndlocation. Hence key 12 will be stored in 2^nd location.