Algorithms: Design and Analysis, Part 1 - Problem Set 6 - Question 4

Problem:

Which of the following is not a property that you expect a well-designed hash function to have?

Solution:

(Option 1) The hash function should "spread out" most (i.e., "non-pathological") data sets (across the buckets/slots of the hash table).
Yes - if that is not the case we are screwed - spreading out is the whole point for hashing.

(Option 2) The hash function should be easy to store (constant space or close to it).
This would be nice, if we take certain size of space to store the hash function itself, it will not be fast to run the hash function either, so yes, we want it to be small.

(Option 3) The hash function should be easy to compute (constant time or close to it).
This would be nice, if it take long time to compute then we might want to use search tree instead. So yes, we want it to be small.

(Option 4) The hash function should "spread out" every data set (across the buckets/slots of the hash table).
This is impossible to expect, an adversary knowing the hash function can always cherry pick a data set so that all data goes to the same bucket for the hash function.