retagged by
671 views
0 votes
0 votes
Consider a Hash table containing ‘n’ keys and ‘k’ slots. Each key will hash into a slot in the given Hash table. (Assume collisions are resolved by chaining).
1)What is the probability that the first slot of hash table will be empty?
retagged by

1 Answer

0 votes
0 votes
1st one will be empty.So every key has to be placed in other k-1 slots.As insertion of every element is independent.

so probability will be ((k-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
2
Rahul_Rathod_ asked Dec 28, 2018
413 views
A) (1-(N / K)) ^ r b) (1-(K / N)) ^ r c) (1+(N / K)) ^ r-1 d) (1-(K / N)) ^ r-1
1 votes
1 votes
0 answers
3
hrcule asked Aug 9, 2018
500 views
Suppose we used a hash fu action H(n) to hash n distinct elements (key) into an array T of length m. What is expected number of collision, if simple uniform hashing is us...