i) A data structure called a hash table sends data to one of many locations at r

Question

i) A data structure called a hash table sends data to one of many locations at random (with the hope that the randomness spreads things evenly). If there are 50 locations in the hash table, and I add 2 pieces of data, what is the probability they land in the same location? (Notice that there are 50 locations where this could happen...)

ii) Suppose now that I add 3 pieces of data to my "hash table," sending each piece of data to one of 50 locations at random. What is the probability that all three land in different locations?

Explanation / Answer

1) Probability of landing at same location -

There are 50 locations where this can happen. Let first particle land at any location X

Probability of second particle landing at X = 1/N where N is the number of locations = 1/50

2)P(Land at 3 different) = 50*49*48/50^3 = 2352/2500=0.9408

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.