Носки, дни рождения и коллизии хэш-функций
Предположим у вас есть огромная куча, в которой смешаны белые, черные, зеленые и красные носки, примерно с одинаковым количеством каждого цвета. Вы случайным образом выбираете пару носков из этой кучи. Какова вероятность, что вы вытащите пару носков одинакового цвета?
Существует шестнадцать комбинаций выбора пары носков: ББ, БЧ, БЗ, БК, ЧБ, ЧЧ, … И из этих шестнадцати пар, только четыре пары будут одного цвета. Т.е. вероятность выбора пары носков одного цвета составляет 25%.
Предположим, вы берете три носка. Какова вероятность, что среди выбранных носков будет существовать хотя бы одна пара носков одного цвета?
Мы уже знаем, что вероятность выбора пары носков одного цвета, если вы достанете двое носков, составляет 25%. Если вы уже вытянули пару одинаковых носков – отлично. Если нет, значит, у вас в руках есть двое носков разного цвета, один из которых может совпасть. Т.е. в этом случае шансы возрастают.
Существует 64 способа вытянуть три носка: БББ, ББЧ, … и т.д. Из этих 64 возможных комбинаций, у 40 комбинаций есть пара носков одного цвета, поэтому вероятность вытянуть пару носков одного цвета составляет примерно 63%.
Предположим, вы вытягиваете четыре носка. Существует 256 возможных комбинаций, 232 из которых содержат хотя бы одну пару одинаковых носков, т.е. вероятность вытянуть пару одного цвета составляет 91%.
Конечно, если мы будем вытягивать пять носков, то шансы вытянуть пару одинакового цвета будут равны 100%. Пять носков, четыре цвета, пара носков одного цвета будет обязательно.
Может показаться, что мы допустили некоторые ошибки при расчете вероятностей, поскольку после того, как мы вытянули белый носок, вероятность того, что мы вытянем не белый носок немного возрастает, поскольку белых носков в куче остается меньше. Но если куча достаточно велика, то этой погрешностью мы вполне можем пренебречь.
Теперь давайте назовем вытянутую пару носков одного цвета «коллизией».
Кажется очевидным, что при увеличении количества цветов носков, мы уменьшаем вероятность получения коллизии на заданном размере выборки. И при увеличении размера выборки, увеличивается вероятность коллизии внутри выборки.
Предположим у нас есть носки 365 различных цветов и предположим, что каждый носок пронумерован в соответствии с номером цвета, так что мы можем отличить их друг от друга; и у нас есть куча из шести миллиардов носков, приблизительно с одинаковым количеством носков каждого цвета. Какова вероятность коллизии, когда мы вытащим два случайных носка из кучи? Конечно, она равна одному из 365. Трех носков? Чуть больше, чем удвоенное значение. И так далее. Чтобы найди точные вероятности, мы должны определить количество вероятных комбинаций и количество комбинаций, которые содержат хотя бы одну коллизию.
Оказывается, что точка, при которой вы получаете вероятность коллизии более 50%, составляет 23 носка. Это тот самый знаменитый «парадокс дней рождения». Если вместо 365 носков разного цвета мы рассмотрим 365 возможных дней рождения (игнорируя високосные годы и тот факт, что в определенные дни рождаются больше людей, чем в другие и т.п.) и возьмем большую группу людей случайным образом. Если группа будет насчитывать не менее 23 человек, то шансы того, что два человека будут иметь день рождения в один день, составит пятьдесят на пятьдесят. В группе из 50 человек, эта вероятность будет около 97%.
Это может быть отличным фокусом на вечернике, собравшей от 30 до 50 гостей: если вы обойдете комнату и спросите день рождения каждого, то будут все шансы на то, что у двух людей день рождения придется на один день. Но что из этого следует?
Предположим у вас есть более четырех миллиардов возможных цветов носков и просто огромная куча носков, с примерно одинаковым количество носков каждого цвета. Вы начинаете доставать носки из кучи. Какова вероятность коллизии в зависимости от количества вытянутых носков? Четыре миллиарда – это чрезвычайно огромное число по сравнению с 4 или 365. Как вы думаете, какая вероятность коллизии при этом? Через какое время вам стоит начать беспокоиться?
Не так долго, как вы могли бы думать. Я решил эту задачу и вывел результаты в виде удобного графика с двумя логарифмическими осями:
Разве может быть что-то лучше прямой линии на графике с логарифмическими осями?
В любом случае, вы получаете 1% процент вероятности коллизий после приблизительно 9300 попыток и 50% после 77000 попыток. Когда количество попыток достигнет середины шестизначного числа, на практике, вы где-нибудь гарантированно получите коллизию.
Вот почему, использование 32-разрядного хэш-значения в качестве «уникального» идентификатора является плохой идеей. Хэш-значения не являются случайными по определению, но при хорошем распределении они вполне подойдут для этих целей. Вы можете подумать: «Ну да, конечно же, хэш-значения не могут быть абсолютно уникальными, поскольку существует более четырех миллиардов возможных значений, а доступны только четыре миллиарда хэш-значений. Но с таким количеством возможных хэш-значений, вероятность получения уникального значения действительно высока». Но насколько высока вероятность коллизии? 9300 объектов – это не такое уж и большое количество, а 1% – это весьма высокая вероятность коллизии.