32-битный алгоритм контрольной суммы лучшего качества, чем CRC32? - PullRequest
5 голосов
/ 06 декабря 2011

Существует ли какой-либо 32-битный алгоритм с контрольной суммой:

  • Меньшая вероятность коллизии хеша для размеров входных данных <1 КБ?</li>
  • Удары столкновений с более равномерным распределением.

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

Есть идеи?Благодарю.(Мне нужна конкретная реализация, лучше в C, но C ++ / C # или что-то еще для начала тоже нормально).

Ответы [ 2 ]

4 голосов
/ 06 декабря 2011

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

0 голосов
/ 06 декабря 2011

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

...