Списки хэш-функции

Question

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

Например, вот что я хочу:
f ((1 2 3)) = f ((1 3 2)) = f ((2 1 3)) = f ((2 3 1)) = f ((3 1 2)) = f ((3 2 1)).

Любая идея, как я могу решить эту проблему? Я попытался сделать сумму квадратов всех элементов, но оказалось, что есть столкновения, например, f ((2 2 5)) = 33 = f ((1 4 4)), что неправильно, так как списки не являются тот же самый.

Я ищу простой подход, если он есть.

Answer 1

Сортировка списка и затем:

list.each do |current_element|
  hash = (37 * hash + current_element) % MAX_HASH_VALUE
end

Answer 2

Возможно, вам не повезло, если вы действительно не хотите столкновений.Есть N, выберите k наборов размера k с элементами в 1..N (и хуже, если вы разрешите повторы).Итак, представьте, что у вас N = 256, k = 8, тогда N выберите k ~ 4 x 10 ^ 14.Вам понадобится очень большое целое число, чтобы отчетливо хэшировать все эти наборы.

Возможно, у вас есть N, k, чтобы вы могли все еще работатьУдачи.

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

Answer 3

Итак, вы ищете что-то, обеспечивающее эти свойства,

1. If h(x1) == y1, then there is an inverse function h_inverse(y1) == x1

2. Because the inverse function exists, there cannot be a value x2 such that x1 != x2, and h(x2) == y1.

Мультипликативный метод Кнута

В книге Кнута «Искусство компьютерного программирования», раздел 6.4, aмультипликативная схема хеширования представлена ​​как способ написания хеш-функции.Ключ умножается на золотое отношение 2 ^ 32 (2654435761) для получения результата хеширования.

hash(i)=i*2654435761 mod 2^32

Так как 2654435761 и 2 ^ 32 не имеют общих общих факторов, умножение производит полное отображениеключ к хеш-результату без наложения.Этот метод работает очень хорошо, если ключи имеют небольшие значения.Плохие результаты хеширования получаются, если ключи меняются в старших битах.Как и во всех умножениях, вариации старших цифр не влияют на нижние цифры результата умножения.

96-битная функция микширования Роберта Дженкинса

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

Все источники в этой статье написаны как методы Java, где оператор «>>>» представляет концепцию без знакасдвиг вправо.Если источник должен быть переведен в C, то тип данных Java 'int' должен быть заменен типом данных C 'uint32_t', а тип данных Java 'long' должен быть заменен типом данных C 'uint64_t'.

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

int mix(int a, int b, int c)
{
  a=a-b;  a=a-c;  a=a^(c >>> 13);
  b=b-c;  b=b-a;  b=b^(a << 8); 
  c=c-a;  c=c-b;  c=c^(b >>> 13);
  a=a-b;  a=a-c;  a=a^(c >>> 12);
  b=b-c;  b=b-a;  b=b^(a << 16);
  c=c-a;  c=c-b;  c=c^(b >>> 5);
  a=a-b;  a=a-c;  a=a^(c >>> 3);
  b=b-c;  b=b-a;  b=b^(a << 10);
  c=c-a;  c=c-b;  c=c^(b >>> 15);
  return c;
}

Подробности можно прочитать по здесь

Answer 4

Наивный подход к решению существенной проблемы (сравнение списков без учета порядка) заключается в преобразовании всех списков, которые сравниваются, в набор (установленный в Python или HashSet в Java).Это более эффективно, чем создание хеш-функции, поскольку идеальный хеш-код кажется существенным для вашей проблемы.Для почти любого другого подхода столкновения неизбежны в зависимости от ввода.

Answer 5

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

[...], но оказалось, что есть коллизии

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

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

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

Например:

2 1 3

отсортировано становится

1 2 3

Обрабатывать это как простое числоpowers дает

2^1.3^2.5^3

, который создает

2.9.125 = 2250

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

Answer 6

Комбинировать хеш-значения сложно, я нашел этот способ (без объяснения, хотя, возможно, кто-то его узнает) в пределах Boost :

template <class T>
void hash_combine(size_t& seed, T const& v)
{
  seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

Это должно быть быстро, так как происходят только сдвиги, добавления и xor (кроме фактического хеширования).

Однако требование, касающееся порядка списка, не влияет на конечный результат, означало бы, что сначала нужно отсортировать его, что является операцией O (N log N), поэтому он может не соответствовать.

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

Answer 7

Если все элементы являются числами и имеют максимум, это не так уж сложно, вы сортируете эти элементы, а затем складываете их один за другим в основании вашего максимума + 1.

Трудно описать словами ... Например, если ваш максимум равен 9 (это легко понять), вы получите:

f (2 3 9 8) = f (3 8 9 2) = 2389

Если бы максимум был 99, вы бы получили:

f (16 2 76 8) = (0) 2081676

В вашем примере с 2,2 и 5, если вы знаете, что никогда не получите ничего больше 5, вы можете «составить» результат в базе 6, так что это будет:

f (2 2 5) = 2 * 6 ^ 2 + 2 * 6 + 5 = 89 f (1 4 4) = 1 * 6 ^ 2 + 4 * 6 + 4 = 64