GATE CS 2023 Q10 — Searching, Sorting, Hashing

To counteract a malicious adversary who tries to maximize collisions, we must avoid using any fixed, deterministic hash function.

Why deterministic methods fail:

• If we use a fixed hash function (such as the Division method in Option A or the Multiplication method in Option B), the adversary can easily compute the hash values for a large set of keys.
• Since the number of keys $k$ is greater than the number of slots $m$ ($k > m$), the adversary can select $k$ keys that all map to the exact same slot, resulting in a worst-case search time of $\Theta(k)$.

Why Universal Hashing succeeds:

• In Universal Hashing (Option C), the hash function is selected at random at runtime from a carefully designed family of hash functions.
• Because the specific hash function is chosen randomly and is unknown to the adversary beforehand, the adversary cannot choose a set of keys that guarantees worst-case collisions.
• The expected number of collisions for any subset of $k$ keys is mathematically bounded to at most $\frac{k}{m}$, ensuring optimal average-case performance regardless of the inputs chosen by the adversary.

Therefore, Universal hashing method is the best strategy to counteract the adversary.