Hashing

Question

A hash table of length 100 uses chaining. WHat is the probability that all the values are hashed inti the same slot after 5 intersections?

• A. 5/100$^5$
• B. 1/100$^4$
• C. 1/100$^5$
• D. None of these

Answer 1

(C) 1/100⁴ is the right answer.

EXPLANATION :

For the first element, the probability to be hashed to any location is 1

Since the hash function is k mod 100.

For the upcoming 4 key values, all should hash to the same slot, probability of which is 1/100 for each.

So, probability that all the values are hashed to the same slot will be

P = (1)*(1/100)* (1/100)* (1/100)* (1/100)

   =(1/100⁴)

Answer 2

Now. consider the simple case. In how many ways can I map all the 5 points(A,B,C,D,E) to point '1' ? Only 1 way.

SImilarly, to the point '2' ? Only 1 way.

So, for each point in codomain, there is only 1 way in which all the points in domain get mapped to it.

So, considering all the ways, there 100 ways/cases in which we can map all the points in domain to any single point in codomain.

Now, lets consider the sample space.

How many functions can we have? We can have $100^{5}$.

So, answer = 100/$100^{5}$ = 1/$100^{4}$