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 n distinct values are inserted in the table. A. What is the probability that bucket number 1 is empty after the n-th insertion? B. What is the probability that no collision has occurred in any of the n insertions? C. What is the probability that the first collision occurs at the k-th insertion?
GATE 1997 · Programming and Data Structures · Hashing · medium
Answer: A: ((n-1)/n)^n | B: n!/n^n | C: (n-1)(n-2)...(n-k+2)*(k-1) / n^(k-1)
- Part A: Probability bucket 1 is empty after n insertions: Each of the n inserted keys independently avoids bucket 1 with probability (n-1)/n. Since insertions are independent: P = ((n-1)/n)^n. For large n this approaches e^(-1) ≈ 0.368.
- Part B: Probability of no collision in any of the n insertions: Insertion 1: trivially no collision (any bucket free), P=1. Insertion 2: must land in one of the n-1 remaining empty buckets, P=(n-1)/n. Insertion k: must avoid the k-1 already occupied buckets, P=(n-k+1)/n. Multiply all: (n * (n-1) * (n-2) * ... * 1) / n^n = n! / n^n.
- Part C: Probability first collision occurs at exactly the k-th insertion: For the first collision to occur exactly at insertion k: insertions 1 through k-1 must all be collision-free (each lands in a new bucket), AND insertion k must land in one of the already-occupied k-1 buckets. P(insertions 1..k-1 collision-free) = product_{i=1}^{k-2} (n-i)/n = (n-1)(n-2)...(n-k+2) / n^(k-2). P(insertion k collides) = (k-1)/n. Combined: [(n-1)(n-2)...(n-k+2) / n^(k-2)] * [(k-1)/n].