1
$\begingroup$

I'm searching for good hash-function for N-dimensional vector of M-bit integer numbers with a property that any permutation of the coordinates gives the same result.

e.g. $ h(x,y,z) = h(x,z,y) = h(y,x,z) = h(y,z,x) = h(z,x,y) = h(z,y,x) $

by good hash-function I mean following:

  1. good avalanche properties - There is minimum correlation between values of arguments and values of resulting hash. To avoid mapping of similar arguments to the same hash.
  2. good statistical properties - results are uniformly distributed. ( to minimize statistical probability of collision = mapping different arguments to the same hash )
  3. fast to compute on computer - i.e. use just operation like bitwise and, or, xor, not, bit-shift, aritmetical addition, subtraction, multiplication, maybe modulo

NOTE 1

I certainly do not require perfect hash function (which is bijective; without any collisions ) since I want to use it for dimensionality reduction. The resulting hash should has less bits than the original vector.


NOTE 2

hash function like

$h(x,y,z)= x + y + z$

$h(x,y,z)= x\ \mathrm{XOR} \ y\ \mathrm{XOR}\ z$

has permutation symmetry, but does not have very good statistical properties and avalanche properties. They have too much correlation between arguments and results, therefore for some sets of arguments gives too much collisions.

$\endgroup$
1
$\begingroup$

Just hash each element independently using the same hash function, and take the sum.

$\endgroup$
  • $\begingroup$ heh, on first look I would think that it would not be very good hash (with respect to 1. avalanche 2. statistical properties ), but actually why I don't see any specific problem why not. Perhaps you are right. $\endgroup$ – Prokop Hapala Apr 18 '16 at 11:22
2
$\begingroup$

The obvious solution is to sort the components and then use any of-the-shelf hashing function. By sorting them you effectively map the vector space into itself in a way that is invariant under permutations of the components.

Actually applying any mapping $\phi$ that is invariant under permutation combined with any hash function $\chi$ (or any other function) would result in a (hash) function that is invariant under permutations.

$\endgroup$
  • $\begingroup$ That is certainly a solution. But I was thinking that by design of hash function It would be possible to avoid this, I consider sorting is slower and more complex algorithm than computation of hash. $\endgroup$ – Prokop Hapala Mar 11 '16 at 10:26

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.