Ищите хэш-функцию промежуточной силы

Question

У меня есть статический набор из ~ 35000 уникальных текстовых строк ASCII размером от 20 до 60 байтов каждая. Я хочу ввести в них уникальный индекс. Просто нумерация была бы нежелательна по разным причинам.

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

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

Answer 1

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

Если вам позже понадобится изменить набор строк и захотите легкую, простую хеш-функцию, вы можете рассмотреть возможность использования прокручиваемой хеш-функции Рабина-Карпа . Он может быть вычислен для строки длины n с использованием O (n) сложений, умножений и модулей и гарантирует, что каждые две строки имеют попарно независимые значения хеш-функции. Более того, вы, вероятно, могли бы написать код примерно через полчаса, чтобы проверить, работает ли он лучше, чем контрольная сумма Адлера.

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

Answer 2

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

      Max entries before X chance of collision
Bits  10e−18   10e−15   10e−12   10e−9    10e−6    0.1%     1%       25%      50%      75%
----------------------------------------------------------------------------------------------
16    2        2        2        2        2        11       36       1.9e2    3.0e2    4.3e2
32    2        2        2        2.9      93       2.9e3    9.3e3    5.0e4    7.7e4    1.1e5
64    6.1      1.9e2    6.1e3    1.9e5    6.1e6    1.9e8    6.1e8    3.3e9    5.1e9    7.2e9
128   2.6e10   8.2e11   2.6e13   8.2e14   2.6e16   8.3e17   2.6e18   1.4e19   2.2e19   3.1e19
256   4.8e29   1.5e31   4.8e32   1.5e34   4.8e35   1.5e37   4.8e37   2.6e38   4.0e38   5.7e38
384   8.9e48   2.8e50   8.9e51   2.8e53   8.9e54   2.8e56   8.9e56   4.8e57   7.4e57   1.0e58
512   1.6e68   5.2e69   1.6e71   5.2e72   1.6e74   5.2e75   1.6e76   8.8e76   1.4e77   1.9e77

То есть со строкой 35000 (3.5e4),64-битный хеш, это дает вам шанс между 10e ^ -12 и 10e ^ -9 шансом на столкновение.Это может показаться не очень высоким, но когда дело доходит до хеширования, довольно легко попасть в 1 из миллиарда.

Увеличивая до 128 бит, вы уменьшаетесь до значительно меньше 1 из (миллиарда * миллиардов).).

Answer 3

Устанавливается на 64-битной MurmurHash64B . Дополнительные очки за мурлыкающее имя.

Answer 4

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

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

Answer 5

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

Чтобы получить четыре разные хеш-функции, я бы использовал шаг предварительной обработки, который каким-то образом изменяет входные данные для хеш-функции, которые не коммутируют со значениями в хеш-функции. Одним из способов будет использование 256-байтовой таблицы поиска для перенумерации байтов. Другим может быть умножение каждого байта на X mod 257, заменяя все, что дает 256 = -1 mod 257, на -X mod 257, потому что иначе это не произойдет. Обратите внимание, что (a * 256 + b) мод 257 является модом + b 257.