MD5 хэширует 4-байтовые и 8-байтовые ключи в 16-байтовые значения;какова вероятность столкновения?

Question

У меня есть 2 ³² 4-байтовые ключи, которые я хэширую; какова вероятность столкновения?

Что, если у меня есть 2 ⁶⁴ 8-байтовые ключи (на самом деле не хранится каждая клавиша, но я хочу знать худший случай)?

Answer 1

За на странице Википедии о проблеме дня рождения , хорошее приближение первого порядка можно найти с помощью 1-e^(-(n^2)/d).График этого для ваших значений дает этот график (логарифмическая горизонтальная ось, я увеличил, где вероятность начинает расти).Обратите внимание, что это только приблизительное значение, и его следует рассматривать консервативно (т. Е. Реальная вероятность может быть несколько выше, но она должна быть в правой точке).

Answer 2

Что вы делаете с хэш-кодами? Если вы используете их для определения того, совпадают ли два фрагмента данных, хеш MD5 довольно хорош, хотя только если вы работаете с данными, которые не создаются злонамеренными объектами. (Для криптографических целей нужны лучшие алгоритмы хеширования именно для того, чтобы справиться с проблемой «злоумышленника».)

Если вы используете их для построения карты (т. Е. Вы создаете хеш-таблицу), обычно лучше использовать дешевый хеш и придумать способ уменьшить стоимость столкновения (например, повесив связанный список из хеш-таблицы и изменение размера / перестроение, когда средний вес становится слишком большим).