Skip to content
GATEiit

GATE CSE 2023 Q20: Hashing strategy against an adversary maximising collisions

Question

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 kk be the number of keys, mm be the number of slots in the hash table, and k>mk > m.

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

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 1/3 mark in GATE.
Show answer and explanation

Answer: C (official GATE 2023 final answer key)

Concept used: Any fixed hash function can be attacked; choosing the function at random from a universal family cannot.

First step: Ask whether the adversary can predict which slot each key goes to under each strategy.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2023 CS question paper and final answer key, organised by IIT Kanpur. Question paper · Answer key

More Programming and Data Structures PYQs

PracticePractise Programming and Data Structures questions →Full paperAll GATE CSE 2023 questions →