Data Structures and Algorithms - Old Questions

8. What is Hashing? What collision means? State collision resolution techniques. Explain one of them in brief.

Hashing is a well-known technique to search any particular element among several elements. It minimizes the number of comparisons while performing the search. 

In hashing, an array data structure called as Hash table is used to store the data items. Hash table is a data structure used for storing and retrieving data very quickly. Insertion of data in the hash table is based on the key value. Hence every entry in the hash table is associated with some key. Using the hash key the required piece of data can be searched in the hash table by few or more key comparisons.

    Fig: Hashing Mechanism

Hash function is a function which is used to put the data in the hash table. Hence one can use the same hash function to retrieve the data from the hash table. Thus hash function is used to implement the hash table. The integer returned by the hash function is called hash key.

Collision

The situation in which the hash function returns the same hash key for more than one record is called collision. For e.g.

Consider a hash function:

H(key) = recordkey%10 having the hash table size of 10

The record keys to be placed are: 131, 44, 43, 78, 19, 36, 57 and 77

131%10= 1

44%10=4

43%10=3

78%10=8

19%10=9

36%10=6

57%10=7

77%10=7

Now if we try to place 77 in the hash table then we get the hash key to be 7 and at index 7 already the record key 57 is placed. This situation is called collision. 

Collision resolution techniques

If collision occurs then it should be handled by applying some techniques. Such a technique is called collision handling technique. Some collision resolution techniques are:

    1.Chaining

    2.Open addressing (linear probing)

    3.Quadratic probing

    4.Double hashing

    5.Rehashing

Chaining:

In collision handling method chaining is a concept which introduces an additional field with data i.e. chain. A separate chain table is maintained for colliding data. When collision occurs then a linked list(chain) is maintained at the key. For e.g.

Consider the keys to be placed in their hash key are 131, 3, 4, 21, 61, 7, 97, 8, 9 then we will apply a hash function as

H(key) = key % D  Where D is the size of table. The hash table will be:

Here D = 10

A chain is maintained for colliding elements. for instance 131 has a home bucket (key) 1. similarly key 21 and 61 demand for home bucket 1. Hence a chain is maintained at index 1.