Как написать хороший hashCode () для перестановок?

Question

В моей программе я обрабатываю множество списков размером n , которые все являются перестановками [1, ..., n ]. Моя проблема в том, что я помещаю эти перестановки в HashMap с и HashSet с, и мне нужен хороший hashCode(), который позволяет избежать слишком большого количества столкновений.

Все решения, о которых я думал, приводят либо к большим коллизиям, либо к переполнению. Как я могу написать хороший хэш-код для перестановок?

Answer 1

Вы пробовали ' вращающийся хеш '? Вы можете отрегулировать величину поворота ствола, чтобы увидеть, насколько это сильно влияет на распределение хэшей.

Answer 2

Пожалуйста, смотрите ссылку в ответе Кармаказе.Он показывает вращающийся сдвиг в гораздо более аккуратном коде и обсуждает общие детали (и проблемы) с различными базовыми хешами.

---

Переполнение неплохо.Просто смоделируйте его обратно :-) Рассмотрим простой сдвиг с помощью XOR и верните «переполнение» обратно в поток?

Рассмотрим для каждого элемента значение i, где h - это 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"

Счастливого кодирования.

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
}

переполнение - очень хорошая вещь, так как тогда вы будете уверены, что все биты включены в хэш