Ищем хэш-функцию

Я ищу хеш-функцию со следующими свойствами

  1. Он отображает произвольную строку равномерно между 0 и 1
  2. Вывод хэш-функции не зависит от длины строки
  3. Хеш-функция принимает случайное начальное число
  4. Для данного случайного начального числа отображение строки в (0,1) является детерминированным, что означает, что если Алиса и Боб вычисляют хэш для данной строки и случайного начального числа, они оба получат одно и то же значение.
  5. Я не беспокоюсь о безопасности. Меня не волнует, сможет ли кто-то в теории восстановить набор строк, учитывая случайное начальное число и хеш-значение.

Было бы здорово получить некоторые идеи.


random hash math random-seed hash-function
person Kilian Scheltat    schedule 03.05.2020    source источник
comment
Можете ли вы уточнить, что nr. 2 на самом деле означает? Вы имеете в виду, что длина строки не влияет на вывод? Как насчет производительности по отношению к длине?   -  person Lasse V. Karlsen    schedule 03.05.2020
comment
Какой язык программирования вы используете?   -  person Peter O.    schedule 03.05.2020
comment
Я использую кучу языков программирования, поэтому я больше ищу псевдокод.   -  person Kilian Scheltat    schedule 04.05.2020
comment
На самом деле я не беспокоюсь о производительности вообще. Я специалист по данным, поэтому мы не запускаем код в производстве. ВАШЕ утверждение верно. Я ищу отображение f(string) -> [0,1], чтобы функция не зависела от длины строки.   -  person Kilian Scheltat    schedule 04.05.2020
comment
Это не кажется слишком сложным. Например, возьмем любую хеш-функцию H(x), которая равномерно отображает строки, скажем, в 64-битное целое число. Тогда H(r || x)/2**64, где r — случайное число, будет хэш-функцией с 5 перечисленными вами свойствами.   -  person President James K. Polk    schedule 04.05.2020

Ответы (1)


arrow_upward
-1
arrow_downward

Если вам не нравится это «решение», объясните, почему, и вы получите лучшие ответы.

Возьмите таблицу кодов ASCII и выбросьте коды для несимволов, таких как «звонок», у вас останется примерно 100 символов.

Сделайте сопоставление 1:1 между символами и двузначными числами, например, вы можете начать с

space <-> 00
! <-> 01
A <-> 33
...
Z <-> 58
...
a <-> 65

Я ожидаю, что вы получите картину. Теперь закодируйте первые 32 (или любые другие) символа в вашей строке очевидным способом, например

`Aa aa` -> `3365006565`

и дополните любые строки короче 32 символов 00. (Мне не терпелось напечатать все 00 для примера.)

Сгенерируйте случайное число в диапазоне [1,64] и используйте его, чтобы повернуть числовую строку, оставленную на это количество мест.

Поставьте десятичную точку перед тем, что осталось, и вы получите искомое действительное число.

Я считаю, что это удовлетворяет вашим требованиям.

person High Performance Mark    schedule 03.05.2020
comment
Мне нравится твоя идея! Проблема в том, что это нарушает номер 2, а именно то, что вывод не зависит от длины строки. Потому что, когда вы заполняете свою последовательность нулями, а затем случайным образом вращаете их, чем короче строка, тем больше нулей и, следовательно, более вероятно, что 0 будут впереди. Мне интересно, можете ли вы решить это, просто не заполняя. - person Kilian Scheltat; 04.05.2020
comment
Это не будет работать очень хорошо для неанглийских наборов символов. - person Jim Mischel; 05.05.2020
comment
Кроме того, число с плавающей запятой двойной точности содержит от 15 до 17 значащих цифр. Таким образом, строки, которые идентичны в первых 8 или 9 символах, будут иметь одинаковое значение. Маловероятно, что эта хеш-функция приведет к равномерному распределению. - person Jim Mischel; 05.05.2020