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?
Division method, i.e., use the hash function h(k) = k mod m.
Multiplication method, i.e., use the hash function $h(k)=\lfloor m(kA-\lfloor kA\rfloor)\rfloor$, where A is a carefully chosen constant.
Universal hashing method.
If k is a prime number, use Division method. Otherwise, use Multiplication method.
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.
More Searching, Sorting and Hashing questions
GATE 2022 CS Q16– Suppose we are given n keys, m hash table slots, and two simple uniform hash functions h 1…
GATE 2021 CS (CS1) Q19– Consider the following array: [23, 32, 45, 69, 72, 73, 89, 97]. Which algorithm out of the…
GATE 2019 CS Q30– An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot…
GATE 2019 CS Q50– Consider the following statements: I. The smallest element in a max-heap is always at a…
GATE 2015 CS (CS1) Q14– Which one of the following is the recurrence equation for the worst case time complexity…
GATE 2016 CS (CS1) Q23– The worst case running times of Insertion sort, Merge sort and Quick sort, respectively,…