The Gateway to Computer Science Excellence
0 votes
910 views

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 

  1. Less than $1$
  2. Less than $lg n$
  3. Greater than $1$
  4. Greater than $lg n$ 
in DS by Boss (30.1k points)
recategorized by | 910 views

2 Answers

+1 vote

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

by Loyal (7.2k points)
0 votes
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.
by Boss (25.5k points)
0

what does lgn mean in option D ? is it log n ?

0
Yup
0

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.

0
Can you explain ??

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,648 questions
56,429 answers
195,208 comments
99,921 users