An algorithm has to store several keys generated by an adversary in a hash…
GATE · 2023 · CS · Computer Science & IT
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?
- A.
Division method, i.e., use the hash function h(k) = k mod m.
- B.
Multiplication method, i.e. use the hash function h(k) = ⌊m(kA − ⌊kA⌋)⌋, where A is a carefully chosen constant.
- C.
Universal hashing method.
- D.
If k is a prime number, use Division method. Otherwise, use Multiplication method.
Attempted by 499 students.
Show answer
Correct answer: C
Explore the full course: Iocl Engineers Officers Grade A Paper 2
Loading lesson…