How to write a good hashCode () for permutations?

Question

In my program, I process many lists of size n, which are all permutations [1, ..., n]. My problem is that I put these permutations in HashMapand HashSets, and I need a good hashCode()one that avoids too many conflicts.

All the solutions that I thought of lead either to a large number of collisions, or to overflow. How to write a good hash code for permutations?

Answer 1

Have you tried the spinning hash ? You can adjust the amount of rotation of the trunk to see if the hash value matters.

Answer 2

See the link in karmakaze's answer. It shows a spinning shift in much more accurate code and discusses common details (and problems) with various main hashes.

---

Overflow is not bad. Just put the module back in :-) Consider a simple shift with XOR and feed the overflow back into the stream?

Consider the value of i for each element, where h is long:

h ^= i;          // XOR in new data
h <<= 11;        // shift with a relatively long cycle
h ^= (h >>> 32); // feed the "overflow" back into the input
h &= 0xFFFF;     // throw out "overflow"

Happy coding.

Answer 3

n

int hash = 0;
for(int i = 0; i<n;i++){
    hash +=  perm[i]*prime[i];//really unique will be hash +=Math.pow(prime[i],perm[i]) but will be to computationally heavy
}

, ,