Студия разработки сайтов и приложений

Netspark.ru

Про парадокс дней рождения

Из примера в предыдущем посте может показаться, что подобные совпадения редки, но это совершенно не так. При достаточно большом количестве тестов они могут встречаться регулярно. Причем это количество — не такое уж и большое на самом деле. У меня например два ложных срабатывания произошли уже на таких числах: 558 tests, 2110 assertions.

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

Этот парадокс относится к «веридическим» (или по-нашему истинным) парадоксам — утверждениям, которые интуитивно кажутся людям парадоксальными, но на деле оказываюстя верными (то есть по сути парадоксами не являются). К таким парадоксам относится например известнейший парадокс Монти Холла про автомобиль за одной из трех дверей.

Если про дни рождения не слышали, то вкратце:

Как вы думаете, сколько людей должно быть в одной комнате, чтобы вероятность того, что у каких-то двух из них совпадет день рождения (число и месяц), превысила 50%? На первый взгляд может показаться, что это какое-то большое число, однако правильный ответ — 23. Всего двадцать три человека.

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

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

Но есть и более продвинутые решения, например библиотека Hashids, генерирующая уникальные хэши. Сейчас ее зачем-то переименовали в Squids , хотя hashids звучит значительно веселее. Рекомендую пользоваться, и генерируя хэши не забывать — случайности не случайны!

Комментарии