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