UGC NET CSE | June 2014 | Part 3 | Question: 64

Question

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 $K$ is 

• A. Less than $1$
• B. Less than $lg n$
• C. Greater than $1$
• D. Greater than $lg n$ 

Answer 1

This is a theorem in Universal Hashing -

"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<=m, the expected number of collisions involving a particular key x is less than 1."

ref: https://gateoverflow.in/45237/hashing

Hence ans is A

Answer 2

n - m(1-(m-1)/m)^n)

For a slot collision doesn't occur given by following probability ..

1-((m-1)/m)^n

Expectation for m slot collision doesn't occur...

m((1-((m-1)/m)^n -------------- equation A

So for n keys expected number of times collision occur is ...

n - equation A

Take n= 32 and m=32 it will gives 11.58

So ans should be D.

Comments

Don't you think most of the time option D and C will give you the same answer . one is contained in another .

for example option D says greater then logn lets consider this log2base 2 =1  means greater then 1  and option C says the same thing greater then 1.

---

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 m, the expected number of collisions involving a particular key x is less than 1.

---

Can you explain ??