std::hash vs crc32

#cpp #linux #gcc #cpp11 #хеширование

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

Ответы

Ответ 1

Основа - 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  

и вот вам абсолютно прекрасное сравнение различных алгоритмов хэширования


Ответ 2

Очевидно, ответ зависит от: типа данных, для которого вычисляется хеш, версии используемой
стандартной библиотеки, разрядности и т.д. Если используешь libstdc++, то для std::string,
попадем в функцию _Hash_bytes отсюда: https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/libsupc%2B%2B/hash_bytes.cc 

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


Ответ 3

Исходя из комментариев, как я понял, std::hash для строк будет использовать алгоритм
хэширования MurmurHashUnaligned2. Для обычных же чисел как такового алгоритма и не
будет - результатом будет непосредственно само число. Поэтому однозначно в случае с
числами std::hash заведомо будет быстрее, чем crc32 и без коллизий в принципе. А вот
со строками несколько иная ситуация. Поэтому догадываюсь, что интересно сравнение MurmurHashUnaligned2
и crc32. Думаю, что исходя из того, что результатом вычислений обоих алгоритмов является
число одинаковой разрядности (как это указано в вопросе), то и вероятность коллизий
будет примерно равна. В целом же неплохое сравнение алгоритмов по скорости и коллизиям
для разных типов данных можно посмотреть здесь. В тесте присутствует и crc32 и murmur2.