Question

Consider a has function with n buckets where external (overflow) chaining is used to resolve collisions. The hash function is such that the probability the key value is hashed to a particular bucket is 1/n. The hash table is initially empty and k distinct values are inserted into hash table.

(a) What is the probability the bucket number 1 is empty after kth insertion?

Answer 1

(b) What is a probability that no collision has occurred in any of the k insertions?

Answer 2

(c) What is a probability that the 1st collision occurs at the kth insertion?

Answer 3

for a) probability that the hash fun mapping a key to a bucket number 1= 1/n
and probability that the hash fun not mapping a key to a bucket number 1= 1-(1/n)
probability that the bucket no. 1 is empty=none of these k keys mapped to bucket no. 1
=(n-1/n) (n-1/n) (n-1/n)...k times
=(n-1/n)^k