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

У меня есть числа в определенном диапазоне (обычно от 0 до 1000). Алгоритм выбирает некоторые числа из этого диапазона (от 3 до 10 чисел). Этот выбор выполняется довольно часто, и мне нужно проверить, была ли выбрана перестановка выбранных номеров.

например, один шаг выбирает [1, 10, 3, 18] и еще один [10, 18, 3, 1], тогда второй выбор может быть отброшен, потому что это перестановка.

Мне нужно сделать эту проверку очень быстро. Прямо сейчас я помещаю все массивы в хэш-карту и использую пользовательскую хеш-функцию: просто суммируем все элементы, поэтому 1 + 10 + 3 + 18 = 32, а также 10 + 18 + 3 + 1 = 32. Для равных я использую битрейт, чтобы быстро проверить, находятся ли элементы в обоих наборах (мне не нужна сортировка при использовании битового набора, но она работает только тогда, когда диапазон чисел известен и не слишком большой).

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

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

UPDATE

Я сделал небольшой тест: сгенерировал все комбинации чисел в диапазоне от 0 до 6 и длину массива от 1 до 9. Есть 3003 возможных перестановки, и хороший хэш должен сгенерироваться рядом с этим множеством разных хэшей (я использую 32-битные номера для хэша):

41 хеши для просто добавления (так много конфликтов)
8 разных хэшей для значений XOR'ing вместе
286 различных хэшей для умножения
Было предложено 3003 различных хэша для (R + 2e) и умножено на abc (используя 1779033703 для R)

Таким образом, abc hash может быть рассчитан очень быстро и намного лучше, чем все остальные. Спасибо!

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

Ответ 1

Одним из потенциальных кандидатов может быть это. Зафиксируем нечетное целое число R. Для каждого элемента e вы хотите хэш вычислить коэффициент (R + 2 * e). Затем вычислите произведение всех этих факторов. Наконец, разделите произведение на 2, чтобы получить хэш.

Фактор 2 в (R + 2e) гарантирует, что все факторы нечетны, поэтому избегая что продукт когда-либо станет 0. Деление на 2 в конце происходит из-за того, что продукт всегда будет нечетным, поэтому деление просто удаляет постоянный бит.

например. Я выбираю R = 1779033703. Это произвольный выбор, некоторые эксперименты должны показать, является ли данный R хорошим или плохим. Предположим, что ваши значения - [1, 10, 3, 18]. Продукт (рассчитанный с использованием 32-битных ints) -

(R + 2) * (R + 20) * (R + 6) * (R + 36) = 3376724311

Следовательно, хэш будет

3376724311/2 = 1688362155.

Ответ 2

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

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

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

Ответ 3

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

Алгебраическая причина, почему это имеет место, состоит в том, что операция ИЛИ является коммутативной. Это относится и к другим полукольцам.

Ответ 4

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

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

Ответ 5

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

чтобы вы могли сделать следующее (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]);

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

Ответ 6

Я бы предложил следующее: 1. Проверьте, одинаковы ли длины перестановок (если нет - они не равны)

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

Примечание: если вы можете иметь одинаковые номера в своих перестановках (например, [1,2,2,10]), вам нужно будет удалить элементы из второго массива, когда он соответствует члену из первого.

псевдокода:

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;

идея состоит в том, что вместо сортировки другого массива мы можем просто попытаться сопоставить все его элементы в отсортированном массиве.

Ответ 7

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

1 * 10 * 3 * 18 = 540 и 10 * 18 * 3 * 1 = 540

так что хэш-сумма суммарного произведения будет [32,540]

вам все равно нужно что-то делать с коллизиями, когда они происходят, хотя