edited by
1,442 views
5 votes
5 votes

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 ________

 

  1. $\dfrac{∣H∣}{m^2}$
     
  2. $\dfrac{1}{m^2 \log m}$
     
  3. $\dfrac{∣H∣}{m^2}$
     
  4. $\dfrac{∣H∣}{m}$
edited by

1 Answer

Related questions

0 votes
0 votes
0 answers
1
rsansiya111 asked Mar 12, 2022
361 views
Canadian postal codes have the format LDL DLD, where L is always a letter (between A-Z), D is always a digit (0-9), and is always a single space. For example, the postal ...
0 votes
0 votes
1 answer
3
Ram Swaroop asked Jan 27, 2019
1,263 views
Consider the hashing table with 'm' slots and 'n' keys. If the expected number of probes in unsuccessful search is 3. The expected number of probes in a successful search...