Problem
Suppose that a hash table contains hash_size = 13 entries indexed from 0 through 12 and that the following keys are to be mapped into the table:
10 100 32 45 58 126 3 29 200 400 0
(a) Determine the hash addresses and find how many collisions occur when these keys are reduced by applying the operation % hash_size.
(b) Determine the hash addresses and find how many collisions occur when these keys are first folded by adding their digits together (in ordinary decimal representation) and then applying % hash_size.
(c) Find a hash function that will produce no collisions for these keys. (A hash perfect hash functions function that has no collisions for a fixed set of keys is called perfect.) (d) Repeat the previous parts of this exercise for hash_size = 11. (A hash function that produces no collision for a fixed set of keys that completely fill the hash table is called minimal perfect.)