GATE Overflow Test Series | Algorithms | Test 1 | Question: 12

Question

Suppose that you store $6$ records in a hash table of size $8$ by chaining, and suppose that you have a good hash function so that the probability that a key is hashed into any of the $8$ slots is $1/8.$ For a particular slot in the hash table, what is the probability that this slot is empty, that is, none of the $6$ keys hashes into this slot?

• A. $0.125^6$
• B. $0.875^6$
• C. $0.166^8$
• D. $0.833^8$

Answer 1

We want all the $n$ keys to go to $m-1$ locations only. Probability for this will be $\dfrac{(m-1)^n}{m^n} \implies (1-0.125)^6 = 0.875^6 $

Comments

Probability that a key is not hashed into any of the 8 slots is 1-1/8= 7/8= 0.875.

 So Probability that  none of the 6 keys hashed into particular slot= (7/8)^6= (0.875)^6

---

Why is this question not solved in the same manner as this one?

---

bcoz both uses diff. hashing technique as one use chaining and other uses open addressing.