Discussion
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 \gt m\).
Which one of the following is the best hashing strategy to counteract the adversary?
Answer: C
The best strategy is the universal hashing method.
Any single fixed hash function can be defeated: an adversary who knows it can choose k keys that all hash to the same slot, giving \(\Theta(k)\) time per lookup. Universal hashing chooses the hash function at random, at run time, from a family in which any two distinct keys collide with probability at most 1/m. Since the adversary picks keys without knowing which function was drawn, the expected number of collisions for any key is at most about k/m, whatever keys were chosen.
The division method and the multiplication method are both fixed, deterministic functions, so each can be attacked as above. Switching between them on whether k is prime is still deterministic, and the adversary controls the keys anyway.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development