GATE 2023 CS Q.20: solution and answer

GATE 2023 · CSQ.20 · 1 mark · MCQ

An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let $k$ be the number of keys, $m$ be the number of slots in the hash table, and $k > m$ .

Which one of the following is the best hashing strategy to counteract the adversary?

(A)
Division method, i.e., use the hash function $h (k) = k mod m$ .
(B)
Multiplication method, i.e., use the hash function $h (k) = ⌊ m (k A - ⌊ k A ⌋)⌋$ , where $A$ is a carefully chosen constant.
(C)
Universal hashing method.
(D)
If $k$ is a prime number, use Division method. Otherwise, use Multiplication method.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The best hashing strategy to counteract an adversary who chooses keys to maximize collisions is (C) Universal hashing method.

Official answer: CSource: Official answer key, GATE 2023 CS (IIT Kanpur)

The division method h(k) = k mod m and the multiplication method h(k) = ⌊m(kA − ⌊kA⌋)⌋ are both single, fixed functions once m (and A) are chosen — and this choice is known in advance to the adversary.
Since k > m keys must be placed into m slots under a known, fixed function, the pigeonhole principle guarantees the adversary can choose k keys that all map to the same slot (e.g. all keys congruent mod m), forcing Θ(k) collisions in the worst case. The same vulnerability applies to the multiplication method once A is fixed.
Option D only switches between these two still-fixed, still-predictable functions based on whether k is prime — a public, adversary-knowable rule — so it inherits the same weakness and offers no real protection.
Universal hashing instead selects the hash function uniformly at random, at run time, from a carefully designed family of functions — a choice made independently of, and unknown to, the adversary, who must fix the keys before the function is drawn.
Because the adversary cannot know which function will be used when choosing the keys, no fixed set of k keys can be guaranteed in advance to collide under the eventually-drawn function.
The standard guarantee for a universal family is that, for any fixed set of n distinct keys, the expected number of pairwise collisions is O(n/m) — a probabilistic guarantee that holds regardless of how the adversary chose the keys.
Hence Universal hashing (option C) is the hashing strategy that provably counteracts an adversary who chooses keys to maximize collisions.

KEY IDEA

Any fixed (deterministic) hash function can be defeated by an adversary who knows it in advance: since $k > m$ , by pigeonhole the adversary can always choose $k$ keys that all map to the same slot under a known fixed function, forcing worst-case $Θ (k)$ collisions. Universal hashing defeats this by choosing the hash function randomly at run time from a well-designed family, independent of and unknown to the adversary when the keys are chosen — giving a provable expected-collision guarantee no matter what keys are picked.

WATCH OUT FOR

Assuming that any single, fixed hash function (division method, multiplication method, or a rule like option D that just switches between two fixed functions based on a property of k) is safe merely because it "spreads keys well on average" — an adversary who knows the fixed function in advance can always construct k > m keys that collide, regardless of how good the function looks statistically.

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 18 Sorting & hashing questions, with notes

GATE 2023 CS Q.20: solution and answer

Answer and solution

More Sorting & hashing questions