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?
@Sachin Mittal 1 Sir, please add the options.
Answer should be using universal hashing as it randomly chooses hashing function from range of function. Reference: CLRS 3rd version:chap:11, page no.265
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
(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.
64.3k questions
77.9k answers
244k comments
80.0k users