GATE CSE 2023 | Question: 10

Question

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.

Comments

Question was about how to minimize collision from an attacker with $n$ keys and $m$ slots.

Options were

A. modulo remainder

B. multiplication method

C. If m is prime, modulo, otherwise multiplication method.

---

D.using universal hashing function

---

@Sachin Mittal 1 Sir, please add the options.

Answer 1

Answer should be using universal hashing as it randomly chooses hashing function from range of function.
Reference:
CLRS 3^rd version:chap:11, page no.265

Answer 2

Universal hashing refers to selecting a hash function at random from a family of hash functions with a certain mathematical property. This guarantees a low number of collisions in expectation, even if the data is chosen by an adversary. It implements uniform hashing.

ANSWER) C

https://en.wikipedia.org/wiki/Universal_hashing

 

Answer 3

(C.) Universal hashing method ,In universal hashing, at the beginning of the execution, we choose a hash function randomly from a carefully designed family of functions. This guarantees that no single input would result in the worst-case situation. Since the hash functions are random, the behavior would be different for for each execution which would yield average case performance on each input.