Question

Consider inserting values 15, 22 and 29 in the order given into a hash table of size 7 with hash function h(x) = x mod 7. What will be the locations be the respective locations for 15, 22 and 29 in the hash table if quadratic probing is used to resolve colisions?

	a.	1, 2, 4
	b.	1, 2, 3
	c.	1, 2, 0
	d.	1, 1, 1

Answer 1

Quadtratic Probing:

If h(x)=x mod 7 is already occupied then we insert at the entry h(x)=(x + 1*1)mod 7 .

If h(x)=(x + 1*1) is already occupied then we insert at the entry h(x)=(x + 2*2)mod 7

At the i'th iteration we insert at h(x)=(x+i²)mod 7

Now look at solution.

15 mod 7= 1 so 15 will be at hash value 1

22 mod 7=1 here 1 is already occupied so apply quadratic probing and find new hash value for 22.

(22+1*1) mod 7=2 so 22 will be at hash value 2

29 mod 7=1 we know that 1 is already occupied so recalculate the hash value

(29 + 1*1)mod 7=2 we know that 2 is already occupied so recalculate the hash value for 29

(29+2*2)mod 7=5 so 29 will be stored at hash value 5.

There is no option correct.