0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How to calculate the the range of sums? Can you please describe how did you calculate the range? $\endgroup$ – Redwanul Sourav Sep 6 '17 at 11:34
  • $\begingroup$ 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$ $\endgroup$ – user451844 Sep 6 '17 at 11:36
1
$\begingroup$

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.

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

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.