GATE CS 2023 (Forenoon) — Question 20

AlgorithmsSearching, Sorting, Hashing MechanismsMCQ1 mark · −1/3 if wrongMedium

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. A
    Division method, i.e., use the hash function \( h(k) = k \bmod m \).
  2. B
    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. C
    Universal hashing method.
  4. D
    If \( k \) is a prime number, use Division method. Otherwise, use Multiplication method.
Practise the full 2023-FN paper
Challenge a friend: WhatsApp Telegram
Recommended book · affiliate linkIntroduction to Algorithms (CLRS)The standard reference behind most GATE algorithm questions.
Practise more on Searching, Sorting, Hashing MechanismsTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group