Hashing

Question

Let $H$ be a finite collection of hash functions that map a universe $U$ of keys to $\{0,1,2, \ldots ,m-1\}$.

$H$ is said to be universal if for each pair of distinct keys, $(k, i) \in U$, the number of hash functions $h\in H$ for which $h(k)=n(i)$ is at most ________

 

• A. $\dfrac{∣H∣}{m^2}$
   
• B. $\dfrac{1}{m^2 \log m}$
   
• C. $\dfrac{∣H∣}{m^2}$
   
• D. $\dfrac{∣H∣}{m}$

Answer 1

Go through this link once :

http://www.mi.fu-berlin.de/wiki/pub/Main/GunnarKlauP1winter0708/discMath_klau_hash_II.pdf

Comments

but whats the answer?

---

That's the definition of universal - option D.