Best Hash Function for 10-Digit Phone Numbers

Which hash function would be best appropriate where the keys (k) are 10-digit phone numbers and the hash table is of size 10000?

A. k MULT 1000

B. k DIV 10000

C. k EXP 100000

D. k MOD 10000

E. LOG (base 10000) k

F. k FACTORIAL

Answer:

The best hash function for this case would be D. k MOD 10000.

The hash table has a size of 10000, so we want a hash function that will distribute the keys (phone numbers) as evenly as possible over the hash table. Option D, k MOD 10000, does this by taking the remainder of dividing the phone number by 10000. This ensures that no two phone numbers will have the same hash value, and that each hash value will be used for approximately the same number of phone numbers.

The other options are not as good choices. Option A, k MULT 1000, will not distribute the keys evenly, as some phone numbers will have a remainder of 0 when divided by 10000, and will all hash to the same bucket.