Страницы

Поиск по вопросам

пятница, 12 октября 2018 г.

std::hash vs crc32

Какая функция используется для создания хэша в std::hash и насколько она предпочтительнее, чем обычный crc32? Предпочтениями являются меньшее число коллизий, более быстрый расчет. Основа - 32-х битная система. Выдержки из стандарта в качестве ответа не приветствуются.


Ответ

Основа - 32-х битная система.
Вы понимаете, что crc32 и разрядность вашей системы никак не соотносятся? crc32 использовался и в 16-битных ОС типа MS-DOS. И 32 - это просто размер итогового хэша в битах.
Какая функция используется для создания хэша в std::hash
std::hash это не функция, а шаблон, поэтому для хэширования различных типов он будет использовать разные алгоритмы хэширования, например, std::hash для int 1 вернет 1, поскольку хэш для числа - это само число.
Кроме того, вы не сказали, какую именно реализацию стандартной библиотеки C++ вы используете. В теории можно представить себе библиотеку, которая для всего хэширования использует crc32 (и работает очень плохо).
crc32 используется для небольших данных, зато быстрый. md5 в медленней, зато гораздо труднее нарваться на коллизию (32 бита < 128 бит в md5)
ответ на комментарии:
Я соотносил crc32 с хэшем c++11, а он в свою очередь зависит от битности оси. И для корректного сравнения они должны быть одной разрядности
зависит от стандарта ISO, потом от разработчика компилятора. как он реализует хэширование - его собственное дело, если не прописано в стандарте, и да, именно std::hash зависит от разрядности системы, вы правы.
The actual hash functions are implementation-dependent а это значит что и clang и msvc и gcc и все остальные могут реализовать их по-разному. Разве я спрашивал про md5 и его скорость? Он устарел. И там где мне необходимы хэши с минимальными коллизиями я его не буду использовать.
вот это новость. md5 уязвим к намеренным атакам (вы можете создать коллизию специально), поэтому он устарел как криптографический хэш (спасибо @D-side за правку) , но как функция хэширования - нет. (хорошее сравнение md5/sha1)
дефолтная функция для хэширования строк в gcc - MurmurHashUnaligned2
и вот вам абсолютно прекрасное сравнение различных алгоритмов хэширования

Комментариев нет:

Отправить комментарий