Когда хеши сталкиваются?

Я думаю, какое приложение вы используете хеш-функцию, является важным отличием. Например, частые конфликты в контейнерах хеширования могут снизить производительность. Частые коллизии в криптографии будут иметь гораздо более разрушительные последствия (см .: криптографическая хеш-функция в Википедии ).

Коллизия происходит относительно легко даже с «приличным» алгоритмом хеширования. Например, в Java

String s = new String(new char[size]);

всегда хешируется до 0. То есть все строки, содержащие только \ 0 хеш-значение в Java.

Что касается «имеет ли значение, какой это будет контейнер?», Опять же, это зависит от приложения. Вы можете создавать хэш-функции, которые будут хешировать «похожие» объекты на близлежащие значения. Это полезно, например, когда вы хотите найти похожие объекты. Просто перемешайте их все и посмотрите, куда они упадут. В этом случае желательны столкновения или близкие к столкновениям объекты, поскольку они группируют похожие объекты.

В других приложениях вы хотите, чтобы даже малейшее изменение объекта приводило к совершенно иному хеш-значению. Так обстоит дело, например, с криптографией, когда вы хотите быть как можно более уверенными в том, что что-то не было изменено. В этом случае гораздо сложнее найти разные объекты, хеширующие одно и то же значение.

Если у вас есть больше элементов для хеширования, чем у вас есть слотов, то у вас будут коллизии хеширования. Но если у вас плохой алгоритм хеширования, вы увидите коллизии, даже если соотношение элементов / слотов очень мало. Хороший алгоритм хеширования (включая большинство из тех, что вы увидите в дикой природе) попытается распределить полученные хеши по всему выходному пространству как можно более равномерно и, таким образом, минимизировать конфликты.

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

Вы увидите, что люди называют MD5 «сломанным» алгоритмом хеширования, хотя на самом деле он просто плохой для использования в качестве криптографического хеша. Он будет лучше, чем тот, который вы построите сами.

В зависимости от вашего приложения криптографические хэши, такие как MDA, SHA1 / 2 и т. Д., Могут быть не идеальным выбором именно потому, что они выглядят как полностью случайные, поэтому давая вам столкновения, как предсказано парадоксом дня рождения. Традиционно одной из причин использования простых хэшей, основанных на операции остатка, является то, что ключи должны были быть серийными номерами или аналогичными, так что операция остатка будет выдерживать меньше коллизий, чем ожидалось случайным образом. Например. если ключи представляют собой целые числа от 1 до 1000, у вас может вообще не быть коллизий в контейнере размером 1009, если ваша хеш-функция - это ключевой мод 1009. Люди иногда вручную настраивали системы, тщательно выбирая размер контейнера и хеш-функцию, чтобы добиться равного раскола.

Конечно, если вам нужно беспокоиться о том, что люди злонамеренно выбирают ключи, которые вызовут у вас трудности, или о том, что вышестоящая система отправляет вам очень предвзятые ключи (потому что, например, у нее есть собственная хеш-таблица и она решает обработать все ключи, хеш-значения которых для X сразу). вы можете использовать хэш, основанный на криптографической хеш-функции с ключом, чтобы защититься от этого.

Смысл хэш-функции состоит в том, чтобы случайным образом распределять элементы по контейнерам. Для любой хорошей хеш-функции не имеет / не должно «иметь значения», какой контейнер какой, поскольку они должны быть неразличимы.

Это не относится к реализациям «идеального хеша», которые пытаются работать лучше, чем случайное распределение - в отличие от упомянутых вами алгоритмов.

Как упоминал Майкл, столкновения происходят ДОЛГО, прежде чем будет столько же предметов, сколько слотов. У вас должна быть изящная обработка конфликтов (или идеальный хеш), если вы хотите справиться с парадоксом дня рождения .