Hashing

Question

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?

 

2)What is the expected number of slots that are being nonempty?

Comments

1) $\left ( \frac{k-1}{k} \right )$ⁿ ?

Answer 1

I hope this helps.....
1)What is the probability that the first slot of hash table will be empty?

   => 1st element has the probability of getting a slot is 1/k . not getting a slot is (k-1)/k

     .: The probability that first slot being empty after n keys are hashed is (k-1)/k  *  (k-1)/k * (k-1)/k *.........n times = ((k-1)/k) ^ n

 2) What is the expected number of slots that are being nonempty?

 Ans: we can have k non empty slots,if keys go into the all slots of the table.

       similarly we can have k-1,k-2,k-3,.....,1.

              we can have any number from 1 to k-1 being non empty..

Comments

for the second question answer given as

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

how