Question 11542 – Algorithms
November 21, 2023Hashing
November 21, 2023Hashing
| Question 10 |
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) = ⌊m(kA − ⌊kA⌋)⌋, where A is a carefully chosen constant. | |
| Universal hashing method. | |
| If k is a prime number, use Division method. Otherwise, use Multiplication method. |
Correct Answer: C