GATE CS 2023 Q.20: Hash Tables and Collision Resolution

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?

Division method, i.e., use the hash function $h(k) = k \bmod m$ .

Multiplication method, i.e., use the hash function $h(k) = \lfloor m(kA - \lfloor kA \rfloor) \rfloor$ , where $A = (\sqrt{5} - 1)/2$ .

Universal hashing, i.e., choose a hash function randomly from a collection of universal hash functions.

Open addressing with double hashing.

Official answer and solution

Official answer: C
From: Official GATE 2023 answer key

Solution

Recall hashing methods designed to provide worst-case guarantees against an adversarial key generator.

If a fixed hash function is chosen (such as division method or multiplication method), an adversary who knows the algorithm can deliberately choose keys that all hash to the same slot, resulting in $\Theta(n)$ search time per operation.

To counteract this, Universal Hashing selects a hash function chosen uniformly at random from a carefully designed family of universal hash functions at runtime. Because the hash function is unknown to the adversary in advance, no fixed set of keys can reliably trigger worst-case collisions, ensuring an expected search time of $O(1)$ regardless of the keys chosen.

Final answer

Option (C)

Common trap

Assuming the multiplication method protects against adversaries; any deterministic hash function is vulnerable if known.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2023 Computer Science and Information Technology (CS)
Question: 20 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source