Q on hashing
Printed From: One Stop GATE
Category: GATE Technical Discussions
Forum Name: GATE CS
Forum Discription: General Technical Discussions, Queries, doubts etc. for GATE in CS.
URL: http://forum.onestopgate.com/forum_posts.asp?TID=533
Printed Date: 16Jul2025 at 9:21pm
Topic: Q on hashing
Posted By: balu
Subject: Q on hashing
Date 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 !
|
Replies:
Posted By: manju
Date 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?
|
|