Пересмотрено , август 2014
В ответ на недавний комментарий Arnaud Bouchez и с учетом других ответов и комментариев я признаю, что первоначальный ответ необходимо изменить или сделать его менее квалифицированным. Я оставил оригинал как есть, в конце, для справки.
Во-первых, и, возможно, наиболее важно, правильный ответ на вопрос зависит от предполагаемого использования хеш-кода : что означает «хороший» [хэш-функция ...]? Где / как будет использоваться хеш? (например, предназначен ли он для хеширования относительно короткого ключа ввода? Для целей индексации / поиска, для создания дайджестов сообщений или для других целей? Сколько времени занимает сам желаемый хэш-код, все 32 бита [CRC32 или его производных], больше биты, меньше ... и т. д.
Для вопросов ОП требуется « a быстрее универсальная хеш-функция », поэтому основное внимание уделяется СКОРОСТИ (что-то менее интенсивное использование ЦП и / или что-то, что может использовать параллельную обработку различной природы). Здесь мы можем отметить, что время вычисления для самого хеш-кода часто является лишь частью проблемы при применении хеш-кода (например, если размер хеш-кода или его внутренние характеристики приводят ко многим коллизиям, которые требуют дополнительных циклов для обработки с). Также требование «общего назначения» оставляет много вопросов относительно возможных применений.
Имея это в виду, короткий и лучший ответ может быть:
Да , аппаратные реализации CRC32C на более новых процессорах Intel могут использоваться для создания более быстрых хэш-кодов; однако следует помнить, что в зависимости от конкретной реализации хэша и его применения общие результаты могут быть неоптимальными из-за частоты коллизий, необходимости использовать более длинные коды. Кроме того, наверняка, криптографическое использование хэша должно быть тщательно проверено, потому что сам алгоритм CRC32 очень слаб в этом отношении.
В первоначальном ответе цитировалась статья Брета Малви об оценке хэш-функций и, как указано в ответе Mdlg, заключение этой статьи ошибочно в отношении CRC32 , поскольку реализация CRC32, на которой он основывался, была багги / недостатки. Несмотря на эту серьезную ошибку в отношении CRC32, статья предоставляет полезные рекомендации относительно свойств алгоритмов хеширования в целом. URL этой статьи теперь не существует; Я нашел его в archive.today , но я не знаю, есть ли у автора в другом месте, а также обновил ли он его.
Другие ответы здесь приводят CityHash 1.0 в качестве примера хеш-библиотеки, которая использует CRC32C. По-видимому, это используется в контексте некоторых более длинных (более 32 бит) хеш-кодов, но не для самой функции CityHash32 (). Кроме того, использование CRC32 функциями City Hash относительно невелико по сравнению со всеми операциями сдвига и тасования и другими операциями, выполняемыми для создания хэш-кода. (Это не критика CityHash, для которой у меня нет практического опыта. Я перейду к краткому обзору исходного кода, который показывает, что функции CityHash дают хорошие результаты, например, ell-распределенные коды, но не намного быстрее чем другие хеш-функции.)
Наконец, вы также можете найти понимание этой проблемы в квазидубликатном вопросе по SO .
Оригинальный ответ и редактирование (апрель 2010 г.)
A priori , это звучит как плохая идея! .
CRC32 был , а не , предназначенным для целей хеширования, и его распределение, вероятно, будет неравномерным, что делает его относительно плохим хеш-кодом. Кроме того, его «скремблирующая» мощность относительно невелика, что создает очень плохой односторонний хэш, что может быть использовано в криптографических приложениях.
[BRB: я ищу онлайн-ссылки на этот счет ...]
Первое попадание Google [ключевые слова = распределение CRC32], кажется, подтверждает это:
Оценка CRC32 для хеш-таблиц
Редактировать : Приведенная выше страница и, действительно, полная статья предоставляет хорошую основу для поиска в хэш-функциях .
Чтение[быстро] эта статья подтвердила общее утверждение о том, что в целом CRC32 не следует использовать в качестве хэша, однако, и в зависимости от конкретной цели хеширования, возможно, будет возможно использовать, по крайней мере, вчасть, CRC32 как хеш-код.
Например, младшие (или более высокие, в зависимости от реализации) 16 битов кода CRC32 имеют относительно равномерное распределение, и при условии, что никто не заботится оКриптографические свойства хеш-кода (то есть, например, тот факт, что подобные ключи производят очень похожие коды), может быть возможно создать хеш-код, который использует, скажем, конкатенацию младших [или более высоких] 16 битов для двух кодов CRC32производится с двумя половинками (или любым другим делением) исходного ключа.
Нужно запустить тесты, чтобы проверить эффективность встроенногоИнструкция CRC32 относительно альтернативных хеш-функций будет такой, что накладные расходы на двойной вызов команды, объединение кода и т. Д. Не приведут к общей более медленной функции.