Парадокс дня рождения в базе данных (рассчитать вероятность столкновения)
В соответствии с Birthday paradox:
Если я применил его к базе данных (пожалуйста, исправьте меня, если я ошибаюсь): если нам нужно сохранить UNIQUE хэшируйте данные в базе данных, и у нас есть хеш-алгоритм, который может генерировать 365 уникальных хеш-значений, существует 50% вероятность того, что коллизия данных произойдет после первых 23 записей данных, и 99,9%(!) вероятность коллизии после первых 75 записей базы данных.
Количество уникальных хэшей, которые может сгенерировать наш алгоритм, и количество записей данных может расти экспоненциально, но вероятность столкновения останется неизменной. Если это правильно?
У меня есть огромная таблица с транзакциями (для электронной коммерции), и поле 'квитанция' установлено как уникальное. И фактические номера квитанций - вот что беспокоит меня.
Пример номера квитанции: BHF2Z47E только заглавные буквы AZ/0-9 длиной 8 символов.
ОБНОВИТЬ:
1 ответ
Парадокс дня рождения просто утверждает, что если вы случайно генерируете значения в пространстве nпри хранении происходит быстрый фазовый переход от отсутствия столкновений к столкновениям sqrt(n) значения - вот где вероятность возрастает до более чем 50%.
В вашем примере у вас есть алфавит из 26 + 10 символов и 8 цифр; так вот 36^8 или около 2,8 триллиона возможных ключей; вы можете ожидать более 50% вероятности столкновения после примерно 1,6 миллиона записей; это не очень хорошо Приличная вероятность столкновения даже при небольшом количестве этого.
Для сравнения предположим, что вы генерировали 160-битный случайный ключ для каждого чека (2^160 возможные значения); тогда вам нужно будет генерировать около 2^80 квитанции (около 10^24) достичь такой же вероятности столкновения. Вы можете продать свой продукт как очень крупную компанию за всю свою жизнь и, вероятно, до сих пор не увидеть ни одного. С другой стороны, ваш жесткий диск или компьютер выйдет из строя до того, как вы столкнетесь с коллизией.
Таблица в этой статье дает некоторые конкретные цифры для вас. Например, с 256-битным значением хеша и 10^31 значения, вы получите вероятность столкновения 10^-15, Согласно этой статье, это примерно необратимая частота ошибок вашего жесткого диска. Это, вероятно, величина того, к чему вы должны стремиться с помощью своих чеков, чтобы избежать их перезаписи. Это не трудно сделать значения немного больше.
Конечно, это зависит от того, правильно ли вы засеяли свой PRNG случайными данными; в противном случае вы можете получить тот же ключ легко:)