edited by
21,818 views
49 votes
49 votes

Consider a hash table with $100$ slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first $3$ slots are unfilled after the first $3$ insertions?

  1. $(97 \times 97 \times 97) / 100^3$
  2. $(99 \times 98 \times 97) / 100^3$
  3. $(97 \times 96 \times 95) / 100^3$
  4. $(97 \times 96 \times 95 / (3! \times 100^3)$
edited by

3 Answers

Best answer
122 votes
122 votes
We have $100$ slots each of which are picked with equal probability by the hash function (since hashing is uniform). So, to avoid first $3$ slots, the hash function has to pick from the remaining $97$ slots. And repetition is allowed, since chaining is used- meaning a list of elements are stored in a slot and not a single element.

So, required probability $= \frac{97}{100} \times  \frac{97}{100} \times  \frac{97}{100}$

$= (97 \times 97 \times 97)/100^3$

Correct Answer: $A$
edited by
21 votes
21 votes
for the first insertion we have (4-100) 97 slots out of 100 slots for the second insertion also we have (4-100) 97 slots out of 100 because here chaining is used to resolve collision it means 2nd element may also get the slot where the first element already have and 3rd  insertion also have  (4-100) 97 slots out of 100 slots it means 3rd element may also get the slot  first and second elements already have. it is just like repetitions.  so answer should be       97/100 * 97/100 * 97/100
7 votes
7 votes

Simple Uniform hashing function is a hypothetical hashing function that evenly distributes items into the slots of a hash table. Moreover, each item to be hashed has an equal probability of being placed into a slot, regardless of the other elements already placed. (Source: https://en.wikipedia.org/wiki/SUHA_%28computer_science%29).

Probability that the first 3 slots are unfilled after the first 3 insertions = 
                (probability that first item doesn't go in any of the first 3 slots)*
                (probability that second item doesn't go in any of the first 3 slots)*
                (probability that third item doesn't go in any of the first 3 slots)

                 = (97/100) * (97/100) * (97/100) 
Answer:

Related questions

35 votes
35 votes
5 answers
4
go_editor asked Sep 28, 2014
8,744 views
Let $S$ be a sample space and two mutually exclusive events $A$ and $B$ be such that $A \cup B = S$. If $P(.)$ denotes the probability of the event, the maximum value of ...