Алгоритм и размер std::hash

Я использую C++11 и алгоритм std::hash. Мне было интересно, какая фактическая реализация хэша используется? Я бы предположил MD5 или SHA, но я не могу найти никакой информации в Интернете.

Кроме того, я хотел бы знать фактическую возвращаемую битовую ширину хеша, так как я должен хранить ее в MySQL.

Наконец, предпочтительнее ли использовать std::hash, а не какую-то другую библиотеку, например crypto++?


c++ algorithm hash c++11 stdhash
person Ælex    schedule 19.11.2013    source источник

Ответы (1)


arrow_upward
10
arrow_downward

Алгоритм, выбранный для std::hash, зависит исключительно от реализации. Вероятно, ни MD5, ни SHA не используются, поскольку для своей цели они снижают производительность.

Большая часть реализации будет намного более тривиальной, чем упомянутая выше, поскольку для std::hash нет криптографических требований, а MD5 и SHA были разработаны для криптографических целей.

требования std::hash гораздо менее строгие:

  1. Принимает один параметр типа Key.
  2. Возвращает значение типа size_t, представляющее хэш-значение параметра.
  3. Не генерирует исключений при вызове.
  4. Для двух одинаковых параметров k1 и k2 std::hash<Key>()(k1) == std::hash<Key>()(k2).
  5. Для двух разных параметров k1 и k2, которые не равны, вероятность того, что std::hash<Key>()(k1) == std::hash<Key>()(k2) должна быть очень малой, приближаясь к 1.0/std::numeric_limits<size_t>::max().
person Jack    schedule 19.11.2013
comment
Теперь вы заставили меня беспокоиться о столкновениях. Я широко использую std::hash для создания уникальных идентификаторов. Тогда для GCC будет ли безопасно предположить, что std::hash предлагает компромисс между производительностью и некриптографической безопасностью (уникальностью хэша)? - person Ælex; 19.11.2013
comment
Вы должны понимать, что уникальность, обеспечиваемая std::hash, не имеет ничего общего с криптографической безопасностью. Его реализация в основном используется с ассоциативными неупорядоченными контейнерами, такими как карта. Реализация не заботится о криптографии, она заботится об эффективности при использовании для управления хеш-таблицами. Если вам нужна криптографическая защита, вам действительно следует указать на внешнюю библиотеку, предназначенную для этой цели. - person Jack; 19.11.2013
comment
Да, и, кстати, доказано, что и MD5, и SHA-0/1/256/512 не так уж безопасны в криптографическом контексте, поэтому им тоже не стоит доверять: en.wikipedia.org/wiki/ - person Jack; 19.11.2013
comment
Забудьте, я даже упомянул криптографию. Все, что меня волнует, это уникальность связанных объектов. Вот почему я беспокоюсь, если алгоритм зависит от реализации, как я могу быть спокойным относительно коллизий хэшей для разных объектов/типов, используемых в std::hash? - person Ælex; 19.11.2013
comment
О чем ты говоришь? Ожидается, что коллизии произойдут с любой хеш-таблицей! - person peppe; 19.11.2013
comment
Никакая хэш-функция не может быть полностью защищена от коллизий. Это очевидно, если вы видите, что кодовый домен хеш-функции имеет мощность, которая обычно на несколько порядков меньше, чем его домен. Учитывая, что вы должны доверять реализации о том, что столкновения не часты. Но вы должны позаботиться о возможности коллизии в любом случае и с любой хэш-функцией. - person Jack; 19.11.2013
comment
Я широко использую std::hash для создания уникальных идентификаторов. Я понимаю это так: я хочу, чтобы библиотека генерировала UUID. Это не std::hash. - person peppe; 19.11.2013
comment
@peppe, нет, я не это имею в виду. Я сопоставляю объекты на основе их хэша, сгенерированного определенными членами. Хотя я понимаю, что никакая хэш-функция не может быть свободна от коллизий, я спрашиваю, несколько безопасно ли это делать с использованием std::hash - person Ælex; 19.11.2013
comment
@Алекс, @пеппе. Я согласен, вам нужен тип UID, такой как определенный стандартами UUID, реализованный в нескольких библиотеках, включая boost::uuid. - person Charles L Wilcox; 19.11.2013
comment
@Alex, UUID реализуют хэши SHA и MD5 строковых данных, а также генерируются полностью псевдослучайно, если вам интересно. Ознакомьтесь с UUID. - person Charles L Wilcox; 19.11.2013
comment
Если вы хотите взглянуть на реализацию (помните, что она может измениться в любое время), хэш libstdc++ сопоставляет 1) интегралы друг с другом 2) указатели сами по себе 3) MurmurHash для float, double, std::strings и в качестве реализации по умолчанию см. здесь и здесь. - person peppe; 19.11.2013
comment
@peppe Это не одно и то же столкновение, потому что два значения имеют одинаковый хэш, и столкновение, потому что два значения попадают в одно и то же ведро. Второй зависит исключительно от bucket_count. Два разных хэша могут оказаться в одном сегменте из-за модульной арифметики hash % bucket_count. Любой тип T с sizeof(T) <= sizeof(std::size_t) имеет вероятность столкновения хэшей 0, поэтому он сопоставляется сам с собой. - person Peregring-lk; 31.08.2019
comment
@peppe Gcc, например, всегда использует bucket_count, которое является простым числом. Поскольку простые числа распределены неравномерно, вероятность того, что два значения имеют один и тот же модуль из одного и того же простого числа, всегда ниже, чем для любого другого числа (или я так думаю). Кроме того, в случае повторного хэширования два значения, находящиеся в одном сегменте (равные или кратные некоторому простому числу), гарантированно окажутся в разных сегментах после повторного хеширования. - person Peregring-lk; 31.08.2019