605 views
1 votes
1 votes
How do i prove that : : : In hashing n items into a hash table with k locations, the expected number of collisions is $n - k + k( 1-\frac{1}{k})^n$ ??

1 Answer

3 votes
3 votes
We have n items to insert and size of hash table of is K .

so the probability A location is empty after first insertion =  (1-probabilty of filling that location)=(1-(1/k))

so probability of A location is empty after n insertion = (1-(1/k))^n

Possible no of empty location  = k*(1-(1/k))^n

Expected No of collision = n - occupied location

                                    = n - (total location - empty location)

                                    = n- (k - k*(1-1/k)^n)

                                    =n- k + k*(1-1/k)^n

Related questions

1 votes
1 votes
1 answer
1
s_dr_13 asked Mar 6, 2019
960 views
Consider an open address hash table with uniform hashing. Out of 10 locations, 8 are occupied. What are the expected number of probes in an unsuccessful and successful se...
0 votes
0 votes
0 answers
3
HeadShot asked Nov 30, 2018
812 views
Anyone please give a solution to solve such question as it is difficult in one go.
0 votes
0 votes
2 answers
4
altamash asked Nov 5, 2018
2,549 views
can any one explain double hashing example