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 \bmod m$.
- Multiplication method, i.e., use the hash function $h(k)=\lfloor m(k A-\lfloor k A\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.