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

Question

У меня есть числа в определенном диапазоне (обычно от 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'ов вместе
• 286 различных хешей для умножения
• 3003 различных хешей для (R + 2e) и умножения, как предлагал abc (используя 1779033703 для R)

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

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

Answer 1

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

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

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

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

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

3376724311/2 = 1688362155.

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

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

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

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

Answer 5

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

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

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

псевдо-код:

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;

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

Answer 6

Мне нравится использовать строковый хеш-код по умолчанию (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]);

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

Answer 7

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

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