How to write a good hashCode() for permutations?

Question

In my program, I handle a lot of lists of size n that all are permutations of [1,...,n]. My problem is that I put these permutations in HashMaps and HashSets, and I need a good hashCode() that avoids too many collisions.

All the solutions I have thought of lead to either a lot of collisions or an overflow. How can I write a good hashCode for permutations ?

Answer 1

Have you tried a 'rotating hash'? You could adjust the barrel rotate amount to see if it makes much difference to the hash distribution.

Answer 2

Please see link in karmakaze's answer. It shows a rotating shift in much neater code, and discusses the general details (and issues) with different basic hashes.

---

An overflow isn't bad. Just modulus it back in :-) Consider just a simple shift with an XOR and feed the "overflow" back into the stream?

Consider, for each element, with value i, where h is a 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

you can take the first n primes and do

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
}

the overflow is a pretty good thing as you'll then be sure to have all bits engaged in the hash