Perfect Hash Functions

Question

I was recently given a homework that asked whether given a list of keys it would be possible to make a hash function that doesnt have any collisions. Doing some research, I found out that given a preordered list of keys, perfect hash functions are possible.

However, I'm not quite sure what to say beyond that. Could anyone give me some advice on how perfect hash functions are made, or what exactly giving a predefined list does to a hash function creator that allows for a perfect function?

Thanks for any help.

Answer 1

The only way to have no collisions is to have a 1-to-1 relationship between the key and the hash value. The range of hash values must be at least as large as the number of keys, and the mapping function must transform each key to a unique value. Much more info here: http://en.wikipedia.org/wiki/Perfect_hash