1
$\begingroup$

We have $1000$ elements with key=1 to 1000, and a hashing function $$ h(i)=i^3 \mbox{ mod } 10 $$ for an array with length $10$ (array index from $0$ to $9$) with chaining method.

What is the probability of two arbitrary keys mapping two different elements to one array index ( i means probability of collision two elements in one array slot)?

i try to solve it, but my last answer is : 0.02. i dont know it's correct or not. but need anyone help me in solving such a question. thanks.

$\endgroup$
  • $\begingroup$ Could you be a little more detailed about how the hashing works? The objects are numbers $1...1000$, the keys are numbers $0...9$, but what does "two keys map two elements to one index" mean? $\endgroup$ – Jack M Aug 31 '14 at 17:01
  • $\begingroup$ Dear @JackM, i means collision. $\endgroup$ – Okh. Pij Aug 31 '14 at 17:06
1
$\begingroup$

Since $gcd(3,10)=1$, than each key from 1 to 10 maps in different bin, and keys $n, m$ (1 to 1000) maps to same bin iff $n=m$ (mod 10). That means there are exactly 100 keys mapping to each bin.

Probability to have two different elements mapped to one given bin (e.g. bin 4) is $$p = \frac {100 \choose 2} {1000 \choose 2} = \frac{11}{1110}.$$

Probability to have two different elements mapped to same bin is $10*p = \frac{11}{111}$.

$\endgroup$
  • $\begingroup$ Dear Ante, the question is: the probability is close to a) 0.1 b) 0.2 c) 0.01 d) 0.02. at this time which of them is true?? $\endgroup$ – Okh. Pij Sep 1 '14 at 11:08
  • $\begingroup$ @Okh.Pij 11/111 is very close to 0.1. $\endgroup$ – Ante Sep 1 '14 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.