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

StackOverflow https://stackoverflow.com/questions/1536393

  •  20-09-2019
  •  | 
  •  

Вопрос

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

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

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

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

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

Обновить

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

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

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

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

Это было полезно?

Решение

Одним из потенциальных кандидатов может быть этот.Исправьте нечетное целое число 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.

Другие советы

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

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

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

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

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

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

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

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

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

примечание:если в ваших перестановках могут быть одинаковые числа (например,[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;

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

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

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

таким образом, хэш суммы-продукта будет [32,540]

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top