Question

Consider the keys given below:

200   15   8   22   28   30   31

If we were to store the above keys into the hash table, which of the following three Hash Function is the best:

•   Function 1:    Key % 22
•   Function 2:    Key % 10
•   Function 3:    (Key – R) % R    where R is the greatest prime number less than the smallest key

Give solid reason to support your answer. A correct answer with an incorrect logic o will result in ZERO marks.

C++ code is NOT required for this question. Along with the answer, you should however explain how you came up with the answer to your question:

Answer 1

The keys are given as

200 15 8 22 28 30 31

For hash Function 1: Key % 22 , the index valuse are calculated as

[ex:200 % 22 = 2]

2, 15, 8, 0, 6, 8, 9 which can be arrenged as 0, 2, 6, 8, 8, 9, 15

there is one collision.

For hash Function 2: Key % 10 , the index valuse are calculated as

0, 5, 8, 2, 8, 0, 1 clearly there are 2 collisions.

For hash Function 3: (Key - R)% R,

For the given key values the smallest key is 8.

Hence,

the greatest prime number less than the smallest key is 7

the index valuse are calculated as [ for ex: (200-7) % 7 = 4 ]

4, 1, 1, 1, 0, 2, 3

so there are 3 collisions

Therefore, the number of collision is minimal for hash Function 1. Hence the perfect hash function for the given set of keys is hash Function 1:   Key % 22