recategorized
1,889 views
2 votes
2 votes

If $h$ is chosen from a universal collection of hash functions and is used to hash $n$ keys into a table of size $m$, where $n \leq m$, the expected number of collisions involving a particular key $x$ is less than __________.

  1. $1$
  2. $1/n$
  3. $1/m$
  4. $n/m$
recategorized

6 Answers

0 votes
0 votes

option A) If h is any hashing function and is used to hash n keys into a table of size m, where n<=m, the expected number of collisions involving a particular key x is less than 1.

0 votes
0 votes
Let X1 be a random variable that defines as follows:-

x is the particular key and X is the random variable

X1=1 if  x collide with another key y

X1=0 if it does not collide.

Now single pair collide with probability 1/m as m is the number of slots.

now E(X1)=1* 1/m +0 * (m-1)/m

E(X1)=1/m.

Now X2,X3,..Xn be the random variable define same as

Xi = 1 if x collide with key c[i]

     =0 otherwise.

E(X1+X2+...+Xn)= E(X1)+E(X2)+...+E(Xn)            [ as all event are independent]

                            =1/m+1/m+….+1/m                      [(n-1) times as x already inserted one place]

                            =(n-1)/m

now n<=m

so E(X) <=1.

So option A.
Answer:

Related questions

1 votes
1 votes
7 answers
6
go_editor asked Mar 24, 2020
1,520 views
Which of the following is a valid heap? $a$$b$$c$$d$
0 votes
0 votes
4 answers
8
go_editor asked Mar 24, 2020
992 views
Match the following :$\begin{array}{llll} & \textbf{List – I} & {} & \textbf{List – II} \\ \text{a.} & \text{Absurd} & \text{i.} & \text{Clearly impossible being con...