Data Structures and Algorithms - Old Questions

9. State collision resolution techniques in hashing. Explain double hashing and quadratic probing techniques.

Collision resolution techniques

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

    1.Chaining

    2.Open addressing (linear probing)

    3.Quadratic probing

    4.Double hashing

    5.Rehashing

Quadratic Probing:

Quadratic probing operates by taking the original hash value and adding successive values of an arbitrary quadratic polynomial to the starting value. This method uses following formula:

where m can be table size or any prime number

For e.g. If we have to insert following elements in the hash table with table size 10:

37, 90, 55, 22, 11, 17

37 % 10 = 7 

90 % 10 = 0 

55 % 10 = 5 

22 % 10 = 2 

11 % 10 = 1

Now if we want to place 17 a collision will occur as 17%10 = 7 and  bucket 7 has already an element 37. Hence we will apply  quadratic probing to insert this record in the hash table.

Consider i = 0 then

(17 + 0 ² ) % 10 = 7

(17 + 1² ) % 10 = 8, when i =1

The bucket 8 is empty hence we will place the element at index 8.

Double Hashing

Double hashing is technique in which a second hash function is applied to the key when a collision occurs. By applying the second hash function we will get the number of positions from the point of collision to insert. There are two important rules to be followed for the second function:

it must never evaluate to zero.

must make sure that all cells can be probed.

The formula to be used for double hashing is

where M is a prime number smaller than the size of the table.

Consider the following elements to be placed in the hash table of size 10

37, 90, 45, 22, 17

Initially insert the elements using the formula for H1(key).

Insert 37, 90, 45, 22 

H1(37) = 37 % 10 = 7

H1(90) = 90 % 10 = 0

H1(45) = 45 % 10 = 5

H1(22) = 22 % 10 = 2

H1(49) = 49 % 10 = 9

Now if 17 to be inserted then

Here M is prime number smaller than the size of the table. Prime number smaller than table size 10 is 7

Hence M = 7

That means we have to insert the element 17 at 4 places from 37. In short we have to take 4 jumps. Therefore the 17 will be placed at index 1.