Неуникальная уникальность, и при чем тут дни рождения

– Ведь в мире их еще миллиарда четыре! А быть может и пять, как знать? –

tl;dr

Почему 2^32 вариантов — не так много, как кажется?
Немного математики о коллизиях и обманчивой уникальности.

Наткнулся на днях на интересное понятие - Парадокс дней рождений (birthday paradox). Это ситуация, когда интуиция нас подводит в оценке вероятностей.

В чём суть

Классический пример - кажется, что, раз в году 365 дней, то чтобы с вероятностью 50% у кого‑то в группе совпали дни рождения, то понадобится (на глазок) что-то около половины от 365 - то есть под две сотни человек. Но математика говорит другое: достаточно всего 23 человека, чтобы вероятность совпадения хотя бы у двоих была примерно 50,7%.

Так происходит потому, что сравнивается не “один человек со всеми датами”, а все пары людей между собой.

Для 23 человек пар будет: 23 * 22 / 2 = 253 пары

У каждой пары есть шанс совпасть. И чем больше таких пар, тем быстрее растёт вероятность, что хотя бы в одной из них случится совпадение.
Почему об этом важно помнить в типовых задачах? 

Зачастую мы генерируем всякие уникальные значения: UUID, slug, реферальный код и прочие идентификаторы каким-нибудь эдаким способом:

substr(sha1($orderKeyString), 0, 8)

Разберём

Один hex-символ хранит 4 бита. Значит 8 hex-символов - это 32 бита. А это, на минуточку, 2^32, примерно 4,29 млрд возможных значений. Дофига, не правда ли? На первый взгляд много, но из-за парадокса коллизии становятся вероятными намного раньше.

Вероятность хотя бы одной коллизии можно приблизительно оценить по формуле: p ≈ 1 - exp(-n(n - 1) / (2 × 2^32)).

Оценочно:
10 000 значений -> ~1.2% шанс хотя бы одной коллизии
50 000 значений -> ~25%
77 000 значений -> ~50%
100 000 значений -> ~69%

То есть проблема не в том, что 4 млрд быстро закончатся, а в том, что при случайном распределении два значения могут получить один и тот же 8-символьный slug уже на десятках тысяч записей.

Как исправить

Увеличить пространство значений, чтобы сделать коллизию практически невозможной.

Например, 16 hex-символов — это уже 64 бита. Для 100 000 записей вероятность коллизии составляет примерно 0,000000027%.

А если идентификатор обязан быть уникальным, то никакая теория вероятностей не заменит UNIQUE на поле и обработку коллизии при генерации.

—

Дурацкая математика! Вечно портит красивые решения!

#php #коллизии #хеширование #birthdayparadox #backend #web #разработка