#probability #uuid #guid #uniqueidentifier
#вероятность #uuid #guid #uniqueidentifier
Вопрос:
Допустим, у меня есть UUID a9318171-2276-498c-a0d6-9d6d0dec0e84 .
Затем я удаляю все буквы и тире, чтобы получить 9318171227649806960084 .
Какова вероятность того, что это уникально, учитывая набор идентификаторов, которые генерируются таким же образом? Как это соотносится с обычным набором UUID?
Комментарии:
1. Я полагаю, вы имеете в виду, что все они имеют одинаковую вероятность генерации. Под «таким же образом» вы подразумеваете «одинаковые буквы в одних и тех же местах»?
2. @xavier Я имею в виду, учитывая набор
nUUID, у которых были удалены буквы и тире, какова вероятность того, что все они уникальны (точных совпадений нет).3. Но почему вы удаляете буквы? У двух разных UUID могут быть буквы в разных местах…
4. @JavascriptLoser мой ответ имел смысл?
Ответ №1:
UUID представлены в виде 32 шестнадцатеричных (с базовым значением 16) цифр, отображаемых в 5 группах, разделенных дефисами. Проблема с вашим вопросом заключается в том, что для любого сгенерированного UUID мы могли бы получить любое допустимое шестнадцатеричное число из набора [ 0-9, A-F] включительно.
Это ставит нас перед дилеммой, поскольку мы заранее не знаем, сколько шестнадцатеричных цифр, сгенерированных для каждого UUID, будет альфа-символом: [A-F] . Единственное, в чем мы можем быть уверены, это то, что каждый сгенерированный символ UUID имеет 5/16 шансов быть альфа-символом: [A-F] . Знание этого делает невозможным точный ответ на этот вопрос, поскольку удаление дефисов и буквенных символов оставляет нас с UUID переменной длины для каждого сгенерированного UUID…
С учетом сказанного, чтобы дать вам пищу для размышлений, мы знаем, что каждый UUID имеет длину 36 символов, включая дефисы. Итак, если мы упростим и скажем, что у нас нет дефисов, теперь каждый UUID может иметь длину всего 32 символа. Основываясь на этом, если мы еще больше упростим и скажем, что каждый из 32 символов может быть только числовым символом: [0-9] теперь мы могли бы дать точную вероятность уникальности каждого сгенерированного упрощенного UUID (в соответствии с нашими вышеупомянутыми упрощениями):
Предполагая, что UUID представлен 32 символами, где каждый символ является числовым символом из набора [0-9]. Мы знаем, что нам нужно сгенерировать 32 числа, чтобы создать допустимый упрощенный UUID. Теперь вероятность выбора любого заданного числа: [0-9] равна 1/10. Другой способ подумать об этом заключается в следующем: каждое число имеет равные возможности для генерации, и поскольку существует 10 чисел: каждое число имеет 10%-ную вероятность генерации.
Кроме того, когда генерируется число, оно генерируется независимо от ранее сгенерированных чисел, т.Е. Каждое сгенерированное число не зависит от результата предыдущего сгенерированного числа. Следовательно, для каждого из 32 сгенерированных цифровых символов: каждое число не зависит друг от друга, и поскольку результатом любого выбранного числа является число и только число из [0-9], мы можем сказать, что каждое выбранное число взаимно исключительно друг для друга.
Зная эти факты, мы можем воспользоваться правилом произведения, которое гласит, что вероятность возникновения двух независимых событий равна произведению их индивидуальных вероятностей. Например, вероятность выпадения двух орлов при двух подбрасываниях монеты составляет 0,5 х 0,5 или 0,25. Следовательно, генерация двух идентичных UUID будет:
1/10 * 1/10 * 1/10 * .... * 1/10 where the number of 1/10s would be 32.
Упрощение до 1/(10^32) или в целом: to 1/(10^n) where n is the length of your UUID. Итак, учитывая все сказанное, возможность генерации двух уникальных UUID, учитывая наши предположения, бесконечно мала.
Надеюсь, это поможет!
Комментарии:
1. Отличный ответ, спасибо! Вы четко изложили, что невозможно было ответить на мой вопрос в его первоначальной форме, и дали мне жизнеспособную альтернативу.