Which of the following 3 choices would make the best hash function for an 11-dig

Question

Which of the following 3 choices would make the best hash function for an 11-digit account number (assuming a random digit between 0 and 9 is assigned for each of the 11 positions)? Briefly, justify your answer by analyzing and comparing the 3 hash functions given below: hi(k). We’ll use open addressing with 1000 array cells, and we’ll use linear probing to resolve collisions. There are 250 keys to hash.

a) Hash function h1(k) = floor(sqrt(k)) % 1000

b) Take the 4 digits in the positions 2, 4, 6, and 8 (offsets start at 0, like a C++ array); call them a, b, c, and d, respectively; concatenate them; and then compute h2(k) = (abcd) % 1000. Note: abcd does not mean a*b*c*d.

c) h3(k) = ((the number of zeroes in k) + (the number of ones in k) + (the number of twos in k) + ... + (the number of nines in k)) % 1000.

Explanation / Answer

Correct Answer is Part a)

Explanation:

While choosing a hash function we need to take take that the number of collisions are reduced as much as possible. The hash function with minimum number of collisions is best hash function.

So, In given question Option c is worst choice on hash function, because each key will be matched to 11, the reason is ((the number of zeroes in k) + (the number of ones in k) + (the number of twos in k) + ... + (the number of nines in k)) is always equal to 11. Hence all keys will be mapped to 11, so this is not good Hash function.

In Option b, the hash value is dependent on positions 2, 4, 6, and 8 only. This will create a lot of collisions. i.e all the numbers of the form XX1X1X1X1XX will be mapped to same hashcode. i.e 10^7 keys will be mapped to same hashcode.

And now option a is the best choice amongst all 3. Because each digit position contributes towards finding the floor(sqrt(k)). And hence number of collisions will be lesser.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.