The GATE Grind

GATE 2023 CS – Question 20

Algorithms · Searching, Sorting and Hashing · 1 mark · Multiple choice

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?

  1. Division method, i.e., use the hash function h(k) = k mod m.
  2. Multiplication method, i.e., use the hash function $h(k)=\lfloor m(kA-\lfloor kA\rfloor)\rfloor$, where A is a carefully chosen constant.
  3. Universal hashing method.
  4. If k is a prime number, use Division method. Otherwise, use Multiplication method.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) Universal hashing method.

Explanation

Any fixed hash function can be attacked by an adversary. Universal hashing picks the function randomly from a family, so the expected number of collisions stays small.