Хэширование UUID без необходимости упорядочения

У меня есть два UUID. Я хочу идеально хешировать их, чтобы получить одно уникальное значение, но с ограничением, что f(m,n) и f(n,m) должны генерировать один и тот же хеш. .

  • UUID — это 128-битные значения.
  • хэш-функция не должна иметь коллизий — все возможные входные пары должны генерировать уникальные хеш-значения.
  • f(m,n) и f(n,m) должны генерировать один и тот же хэш, то есть порядок не важен.
  • Я работаю в Go, поэтому результирующее значение должно умещаться в 256-битном int
  • хеш не обязательно должен быть обратимым

Кто-нибудь может помочь?


uuid hash hash-function hashcode
person cachvico    schedule 19.04.2015    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Сначала соедините их с меньшим.

person user2357112 supports Monica    schedule 19.04.2015
comment
Это не дает ответа на вопрос. Чтобы подвергнуть критике или запросить разъяснения у автора, оставьте комментарий под его публикацией. - person MZaragoza; 19.04.2015
comment
@MZaragoza: Нет, это так. Это соответствует всем требованиям вопроса. - person user2357112 supports Monica; 19.04.2015
comment
можешь объяснить как это сделать. сделать это немного более ясным - person MZaragoza; 19.04.2015
comment
@MZaragoza: неясно, как OP работает со 128-битными или 256-битными числами в ходу, поэтому неясно, как предоставить пример кода, но предположим, что вы хотите хэшировать пары 2-значных десятичных чисел в одно 4-значное десятичное число. числа. Тогда это решение будет хэшировать (05, 22) в 0522 или (53, 40) в 4053. - person user2357112 supports Monica; 19.04.2015
comment
Обратите внимание, что отсутствие требования упорядочения означает, что результаты хеширования должны быть одинаковыми, если UUID меняются позициями, а не то, что мы не можем численно сравнивать UUID как часть хэша. - person user2357112 supports Monica; 19.04.2015
comment
Спасибо за объяснение - person MZaragoza; 19.04.2015
comment
@user2357112 user2357112 хорошая идея объединиться с численно меньшим, чтобы решить проблему упорядочения. Можете ли вы предложить, какую хорошую хеш-функцию использовать для результирующего 48-байтового ввода, учитывая, что он должен быть без коллизий? - person cachvico; 19.04.2015
comment
@cachvico: Что в результате получается 48-байтным вводом? Вы не упомянули об этом в своем вопросе. - person user2357112 supports Monica; 19.04.2015
comment
Я указал, что на входе два 128-битных UUID, что означает, что после объединения мы имеем дело со 128 * 3 битами = 48 байтами. - person cachvico; 19.04.2015
comment
@cachvico: Э... разве это не должно быть 128 * 2 бита? - person user2357112 supports Monica; 19.04.2015
comment
У меня есть два UUID. UUID — это 128-битные значения. Итак, у меня есть 2 * 128 = 256 бит для начала. Вы предлагаете объединить меньший, чтобы устранить проблему с порядком, поэтому у меня есть три UUID = 128 * 3 = 384 бита. 384/8 = 48 байт, вводимые в функцию хеширования. - person cachvico; 20.04.2015
comment
@cachvico: меньший, объединенный с большим, составляет 256 бит. Я не знаю, почему вы думаете, что здесь 3 UUID. - person user2357112 supports Monica; 20.04.2015
comment
Хорошо, понял. Жаль, что я был на другой планете. Итак, вы просто говорите, заказывайте сначала самые маленькие. Итак, какую хорошую хэш-функцию использовать? - person cachvico; 20.04.2015
comment
@cachvico: Вот и все. Это твой хэш. Если вам нужны другие свойства вашего хэша, которые вы не указали в своем вопросе, такие как лавинность или устойчивость к столкновениям ведра, вам, возможно, придется применить еще одну функцию поверх этого, но не зная, какие свойства вам нужны, я могу' не предложить один. Попробуйте просмотреть список хэш-функций в Википедии. - person user2357112 supports Monica; 20.04.2015

arrow_upward
1
arrow_downward

Чтобы развить блестящее решение user2357112 и сократить цепочку комментариев, давайте рассмотрим ваши требования один за другим (и не по порядку):

  • Нет столкновений

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

К счастью, вы говорите:

  • Два входа UUID m и n
  • UUID имеют длину 128 бит каждый.
  • Выходные данные f(m,n) должны быть 256 бит или меньше.

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

  • f(m,n) и f(n,m) должны генерировать один и тот же хеш.

Чтобы выполнить это последнее требование, примите решение о порядке конкатенации по некоторому внутреннему значению двух UUID. Предлагаемый вариант меньшего размера работает просто отлично. Тем не мение...

  • Хэш не обязательно должен быть обратимым

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

person Patrick M    schedule 22.04.2015