# Sum of weighted integers.

I have to calculate hash value for an array of integers. The array has $8$ integers always, and the integers are a permutation of the integers from $1$ to $8$. For example, the array can be like this: $\{1,2,3,4,5,6,7,8\}$ and any permutation of it.

So to calculate hash value of it, I am thinking of a hash function that gives me the sum of the integers multiplied with their indices. For example, the hash value of $\{1,2,3,4,5,6,7,8\}$ is $(1\times1) + (2\times2) + (3\times3) + (4\times4) + (5\times5) + (6\times6) + (7\times7) + (8\times8)$. Formally for the sequence $a$, its hash value $hash(a)$ is defined as summation of $i*a[i]$ for all $i$ from $1$ to $8$.

Now my question is, can two different permutation can have the same hash value? If not, then what is the proof? It might be a silly question, but I am scratching my head over this one for a while.

the proof is that the pigeonhole, has a consequence that no hash function ( by the way they work), no matter how good will always have collisions. you have 8! permutations the range of the sums is 120 to 204 . So, you are trying to fit 40320 permutations, into a range of 84 sums ( okay 85 since I forgot one endpoint), their will be roughly 480 permutations per sum on average, if I did my math correctly.

• How to calculate the the range of sums? Can you please describe how did you calculate the range? – Redwanul Sourav Sep 6 '17 at 11:34
• simple the smallest one is $8\cdot 1+7\cdot 2+6\cdot 3+5\cdot 4+4\cdot 5+3\cdot 6+2\cdot 7+1\cdot 8 = 120$ the largest is $1^2+2^2+3^2+4^2+5^2+6^2+7^2+8^2 = 204$ – user451844 Sep 6 '17 at 11:36

The number of possible hash is $< 8^3$ because $$\sum{i*a[i]} < \sum{8*8}=8^3$$ where as the number of permutation is $8!$.

Since $8! > 8^3$ there are two permutions which have the same hash.

If you want an example : $[1,2,3,5,4,6,7,8]$ and $[1,2,4,3,5,6,7,8]$ will have the same hash.

• Why the number of possible hash is < 8^3 ? – Redwanul Sourav Sep 6 '17 at 11:30
• @RedwanulSourav edited – stity Sep 6 '17 at 11:39
• Note: if you want a hash without collision, chose $$\sum{10^ia[i]}$$ or $$\sum{9^ia[i]}$$ – stity Sep 6 '17 at 11:40