Question

#3 [3 points]

Sketch a hash table of size N=11, where the hash function is hash(key) = key mod N and quadratic probing is used to resolve collisions, after the following elements are inserted:

20, 42, 45, 49, 62, 72, 95.

The probes are based on this equation: (H+c1∗i+c2∗i2)mod(N) and c1=1, c2=1.

0 1 23 4 5 6 78 9 10

If direct hashing was used to store the same elements as the previous problems (20, 42, 45, 49, 62, 72, 95), what should be the minimum size of the hash table?

Answer 1

42

45

95

49

72

62

20

0 1 2 3 4 5 6 7 8 9 10

Size of the table = 11

Hash function : Key mod N

In case of collision Quadratic Probing is used

Formula for quadratic probing

$(H+c_{1}\times i\,+\,c_{2}\times i^{2})\,\,\mathbf{mod}\,N$

Sequence of keys given

20, 42, 45, 49, 62, 72, 95

H(20) = 20 mod 11 = 9

So 20 is placed at index 9 in the hash table

H(42) = 42 mod 11 = 9

But there is already a key at position 9, so there is a collision

To resolve collision, we use Quadratic probing

(H + c1∗i + c2∗i² )mod (N)

(9 + 1*1 + 1*1) mod 11 = 11 mod 11 = 0

So 42 is placed at index 0 in the hash table

H(45) = 45 mod 11 = 1

So 45 is placed at index 1 in the hash table

H(49) = 49 mod 11 = 5

So 49 is placed at index 5 in the hash table

H(62) = 62 mod 11 = 7

So 62 is placed at index 7 in the hash table

H(72) = 72 mod 11 = 6

So 72 is placed at index 6 in the hash table

H(95) = 95 mod 11 = 7

But there is already a key at position 7, so there is a collision

To resolve collision, we use Quadratic probing

(H + c1∗i + c2∗i² )mod (N)

(7 + 1*1 + 1*1) mod 11 = 9 mod 11 = 9

But there is collision at index 9 because 20 is present there

(7 + 1*2 + 1*4) mod 11 = 13 mod 11 = 2

So 95 is placed at index 2 in the hash table

If direct hashing was used, every key would have its place fixed in the hashing table. Every key is placed at the position equal to its key value

So following will be the hashing

H(20) = 20

H(42) = 42

H(45) = 45

H(49) = 49

H(62) = 62

H(72) = 72

H(95) = 95

Thus the minimum table size will be 96 (including index 0)