Question 6: Hash tables [10]

Suppose we want to create a hash table where the keys to the table will be social insurance numbers (i.e. 9-digit numbers), and we expect to enter roughly 10,000 records into the table.

Analyze the strengths and weaknesses of each of the proposed hashing techniques described below:

• Use the entire 9-digit number as the index into the table, with a table of size 1000000000.

• Use the last 4 digits of the number as the index, with a table size of 10000.

• Use the number mod 5003 (a prime number) as the index, with a table size of 5003.