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.