Хорошая хеш-функция для перестановок?

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

Это полезно только в том случае, если вы получаете множество нежелательных коллизий потому что хеш, который вы сейчас делаете, слишком плох. Если столкновения почти не возникают, значит, метод, который вы используете, подходит

I would suggest this: 1. Check if the lengths of permutations are the same (if not - they are not equal)

2. Sort only 1 array. Instead of sorting another array iterate through the elements of the 1st array and search for the presence of each of them in the 2nd array (compare only while the elements in the 2nd array are smaller - do not iterate through the whole array).

note: if you can have the same numbers in your permutaions (e.g. [1,2,2,10]) then you will need to remove elements from the 2nd array when it matches a member from the 1st one.

pseudo-code:

if length(arr1) <> length(arr2) return false;
sort(arr2);
for i=1 to length(arr1) {
elem=arr1[i];
j=1;
while (j<=length(arr2) and elem<arr2[j]) j=j+1;
if elem <> arr2[j] return false;
}
return true;

the idea is that instead of sorting another array we can just try to match all of its elements in the sorted array.

Мне нравится использовать хэш-код строки по умолчанию (Java, C # не уверен в других языках), он генерирует довольно уникальные хэш-коды. поэтому, если вы сначала отсортируете массив, а затем сгенерируете уникальную строку с использованием некоторого разделителя.

, чтобы вы могли сделать следующее (Java):

    int[] arr = selectRandomNumbers();
    Arrays.sort(arr);
    int hash = (arr[0] + "," + arr[1] + "," + arr[2] + "," + arr[3]).hashCode();

если производительность является проблемой, вы можете изменить предлагаемую неэффективную конкатенацию строк, чтобы использовать StringBuilder или String.format

   String.format("{0},{1},{2},{3}", arr[0],arr[1],arr[2],arr[3]);

Хеш-код строки, конечно, не гарантирует, что две разные строки имеют разные хеш-коды, но с учетом этого предлагаемого форматирования коллизии должны быть крайне редкими

Вы можете хранить локальные копии требуемых значений внешних объектов. Затем процедура доступа сравнивает локальную копию с внешним значением и выполняет пересчет только при изменении.

Доступ к свойствам внешних объектов также может вызвать возможную переоценку этих свойств, поэтому система должна поддерживать себя в актуальном состоянии автоматически, но пересчитывать только тогда, когда это необходимо. Я не знаю, нужно ли вам предпринимать шаги, чтобы избежать циклических зависимостей.

Это увеличивает пространство, необходимое для каждого объекта, но удаляет шаблон наблюдателя. Он также откладывает все вычисления до тех пор, пока они не потребуются, вместо того, чтобы выполнять вычисление каждый раз, когда изменяется параметр источника. Надеюсь, это актуально для вашей системы.

Суммирование элементов - это уже одна из самых простых вещей, которые вы можете сделать. Но я не думаю, что это особенно хорошая хеш-функция в отношении псевдослучайности.

Если вы отсортируете свои массивы перед их сохранением или вычислением хешей, подойдет любая хорошая хеш-функция.

скорость: Вы измерили узкое место? Если ваша хеш-функция дает вам много коллизий, и вам приходится тратить большую часть времени на побитовое сравнение массивов, хеш-функция, очевидно, не подходит для того, что она должна делать. Решением может стать сортировка и лучший хэш.