Q10

MCQ1 mark, −0.33

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 \bmod m$ .

(B)

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.

(C)

Universal hashing method.

(D)

If $k$ is a prime number, use Division method. Otherwise, use Multiplication method.

Loading…