Есть ли функция, которая принимает два значения, пусть f (x, y) == f (y, x), а выходные данные являются уникальными?

Question

Мне интересно, есть ли способ генерировать ключ на основе отношений между двумя сущностями таким образом, чтобы ключ для отношений a-> b был таким же, как ключ для отношений b-> a.

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

Очевидно, что это можно сделать с помощью чисел (например, добавить (2,3) эквивалентно добавлению (3,2)).Проблема для меня в том, что я не хочу, чтобы add (1,4) равнялся add (2,3).Очевидно, что любая хеш-функция перекрывается, но я имею в виду слабое чувство уникальности.

Моя наивная (и нежелательная производительность) мысль:

function orderIndifferentHash(string val1, string val2)
{
  return stringMerge(hash(val1), hash(val2));
  /* String merge will 'add' each character (with wrapping).
     The pre-hash is to lengthen strings to at least 32 characters */
}

Answer 1

В вашей функции orderIndifferentHash вы можете сначала заказать val1 и val2 по некоторым критериям, а затем применить любую хеш-функцию, которая вам нравится, чтобы получить результат.

function orderIndifferentHash( val1, val2 ) {
  if( val1 < val2 ) {
    first = val1
    second = val2
  }
  else {
    first = val2
    second = val1
  }
  hashInput = concat( first, second )
  return someHash( hashInput )

  // or as an alternative:
  // return concat( someHash( first ), someHash( second ) )
}

Answer 2

Для чисел один из способов достижения этого - для двух чисел x и y взять x-е простое и y-е простое и вычислить произведение этих простых чисел. Таким образом, вы гарантируете уникальность продукта для каждой отдельной пары x и y и независимость от порядка аргументов. Конечно, чтобы сделать это с любой практически значимой эффективностью, вам нужно сохранить таблицу простых чисел для всех возможных значений x и y. Если x и y выбраны из сравнительно небольшого диапазона, это будет работать. Но если диапазон большой, сама таблица становится непрактично непрактичной, и у вас не будет другого выбора, кроме как принять некоторую вероятность коллизии (например, сохранить таблицу разумного размера из N простых чисел и выбрать x% N-го простого для заданного значение x).

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

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

Answer 3

Вы после:

Некоторые функции f(x, y) такие, что

• f(x, y) == f(y, x)
• f(x, y) != f(a, b) => (x == a и y == b)или (x == b и y == a)

Их будет очень много - с рук я могу подумать, что это "отсортированная конкатенация":

1. Сортировка (x, y) по любому порядку
2. Применение хэш-функции u(a) к x и y индивидуально (где u(a) == u(b) подразумевает a == b и длину u(a) является константой)
3. Конкатенация u(x) и u(y).

В этом случае:

Если x == y, то тогда два хэша тривиальното же самое, поэтому без ограничения общности x < y, следовательно:

• f(y, x) = u(x) + u(y) = f(x, y)

Кроме того, если f(x, y) == f(a, b), это означает, что либо:

• u(x) == u(a) и u(y) == u(b) => x == a и y == b, или
• u(y) == u(a) и u(x) == u(b) => y == a и x == b

Короткая версия:

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

Answer 4

Предположим, у вас есть хэш h(x,y).Затем определите f(x,y) = h(x,y) + h(y,x).Теперь у вас есть симметричный хеш.

(Если вы сделаете тривиальный мультипликативный «хеш», то 1 + 3 и 2 + 2 могут хешировать одно и то же значение, но даже что-то вроде h (x, y) = x* y * y этого избежать - просто убедитесь, что есть некоторая нелинейность хотя бы в одном аргументе хеш-функции.)