A good hash function mimics the gold standard of a random function for all practical purposes



Hashing is a basic computer science technique used in many different contexts, from dictionary data structures to load balancing and symmetry breaking, to cryptography and complexity theory.

In the next few lectures we will study the following:

• Desirable properties of hash families

• Constructions of hash families with these properties

• Applications of hash functions in various contexts

So, consider the completely random hash function: for each e ∈ S, we choose a uniformly random location in [M], and set h(e) to be that location. Clearly, this has great properties

• Low collision probability: Prh[h(a) = h(b)] = 1/M for any a 6= b, since having fixed where a

maps to, there is a 1/M chance that b is mapped to the same location.

• In fact, even conditioned on knowing where any set of elements A ⊆ S maps to, the position

of any e ∈ S \ A is still random:

Prh[h(e) = α | ∧a∈Ah(a) = αa] = 1/M.

Therefore, the correct option is 1/n.

Leave a Comment

Your email address will not be published. Required fields are marked *