Sum of weighted integers.

Question

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.

Answer 1

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.

Answer 2

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.