# Hashing With Chaining Collision

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.

• 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? – Jack M Aug 31 '14 at 17:01
• Dear @JackM, i means collision. – Okh. Pij Aug 31 '14 at 17:06

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