32-битный алгоритм контрольной суммы лучшего качества, чем CRC32?

Есть ли какой-либо 32-битный алгоритм контрольной суммы с одним из:

  • Меньшая вероятность хеш-коллизии для размеров входных данных ‹1 КБ?
  • Столкновения с более равномерным распределением.

Эти относительно CRC32. На первое свойство я практически не рассчитываю из-за ограничения объема памяти 32 бита. Но во втором ... кажется, могут быть улучшения.

Любые идеи ? Спасибо. (Мне нужна конкретная реализация, лучше на C, но C ++ / C # или что-то еще для начала тоже в порядке).


c checksum hash crc32
person Agnius Vasiliauskas    schedule 06.12.2011    source источник
comment
Используете ли вы его как контрольную сумму в системе исправления ошибок, или вы используете его как хеш-функцию, чтобы, вероятно, обнаружить, что два ввода различны, сравнивая их хэши? Коды с исправлением ошибок и хэш-функции имеют разные желаемые свойства. В случае CRC32 он специально разработан для обнаружения ошибок того типа, который вы ожидаете на зашумленной линии (разница в один или несколько битов, не знаю, какие именно).   -  person Steve Jessop    schedule 06.12.2011
comment
Я использую его как хеш-функцию для сравнения двух кусков небольших данных. (‹1КБ). Но я вынужден использовать 32-битный хеш.   -  person Agnius Vasiliauskas    schedule 06.12.2011

Ответы (2)


arrow_upward
4
arrow_downward

Как насчет MurmurHash? сказано, что этот хеш имеет хорошее распределение (проходит тесты хи-квадрат) и хороший лавинный поток. эффект. Также очень хорошая скорость вычислений.

person werewindle    schedule 06.12.2011

arrow_upward
0
arrow_downward

Не по первому критерию. Любая хорошо спроектированная хеш-функция с 32-битным выходом имеет вероятность столкновения 1 из 2 ^ 32 для любой пары входов. Второй критерий не очень хорошо определен, хотя, безусловно, есть некоторые статистические тесты, которые можно было бы использовать, и я уверен, что кто-то это сделал (хи-квадрат для интервалов столкновений?). Что касается необходимости реализации, я настоятельно рекомендую вам не принимать какой-либо предлагаемый код для хеш-функции, который не является реализацией хорошо известного хеш-кода, поскольку существует высокий риск проблем с безопасностью или низкой производительности при развертывании собственного хеш-кода или шифрования. . Хорошо известная, но плохая хеш-функция лучше, чем та, которую вы разработали самостоятельно, даже если последняя хорошо тестирует и имеет «хорошее» распределение коллизий просто потому, что первая привлекает внимание.

person Dan    schedule 06.12.2011
comment
Является ли CRC32 хорошо продуманной хэш-функцией по этому определению? Он предназначен для обнаружения определенных видов ошибок, поэтому я ожидаю, что входные данные с определенными видами различий будут иметь большую вероятность обнаружения (то есть разные значения CRC) за счет других видов различий. - person Steve Jessop; 06.12.2011