One Stop GATE Forum: Q on hashing

Message

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

(a) What is the probability that bucket number 1 is empty after the Kth insertion? 
(b) What is the probability that no collision has occurred in any of the K insertisons? 
(c) What is the probability that the first collision occurs at the Kth insertions? 

please explain ! 

Author	Message
balu Senior Member Joined: 20Feb2007 Online Status: Offline Posts: 236	Topic: Q on hashing Posted: 22Feb2007 at 2:25pm
	CS 1997 Q12. Consider a hash table with n buckets, where external (overflow) chaining is used to resolve collisions. The hash function is such that the probability that a key value is hashed to a particular bucket is 1/n. The hash table is initially empty and K distinct values are inserted in the table. (a) What is the probability that bucket number 1 is empty after the Kth insertion? (b) What is the probability that no collision has occurred in any of the K insertisons? (c) What is the probability that the first collision occurs at the Kth insertions? please explain ! Post Resume: Click here to Upload your Resume & Apply for Jobs

	IP Logged

manju Senior Member Joined: 20Feb2007 Online Status: Offline Posts: 221	Posted: 22Feb2007 at 2:27pm
	1)probability=nCk (1/n)^0 * (1-1/n)^k by binomial distribution 2)1st element van be in any of n buckets 2nd element can be in (n-1) buckets 3rd element can be in any of (n-2)buckets . . . nth element can be in any of (n-k+1) bucket again we can distribute the k values in k! ways.... so probability is n(n-1)(n-2)...(n-k+1)/k! am i right?
	IP Logged


One Stop GATE Forum : GATE Technical Discussions : GATE CS

Topic: Q on hashing