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.
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}$.