Насколько хороший UUID.randomUUID Java?

Есть ли у кого-нибудь опыт, которым можно поделиться?

Существует 2 ^ 122 возможных значений для UUID типа 4. (В спецификации указано, что вы теряете 2 бита для типа и еще 4 бита для номера версии.)

Предполагая, что вы должны были генерировать 1 миллион случайных UUID в секунду, вероятность появления дубликата в течение вашей жизни будет быть исчезающе маленьким. А чтобы обнаружить дубликат, вам нужно будет решить проблему сравнения 1 миллиона новых UUID в секунду с всеми UUID, которые вы сгенерировали ранее ¹ !

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

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

Однако, если вы использовали JVM со «сломанным» генератором криптослучайных чисел, все ставки отключены. (И это может включать в себя некоторые обходные пути для проблем «нехватки энтропии» в некоторых системах. Или возможность того, что кто-то повозился с вашей JRE, либо в вашей системе, либо в исходной.)

^{1 - Предполагая, что вы использовали «какое-то двоичное btree», предложенное анонимным комментатором, каждому UUID потребуется O (NlogN) бит оперативной памяти для представления N различных UUID, предполагающих низкую плотность и случайное распределение битов. Теперь умножьте это на 1 000 000 и количество секунд, в течение которых вы собираетесь проводить эксперимент. Я не думаю, что это практично в течение времени, необходимого для проверки на столкновения высококачественного ГСЧ. Даже с (гипотетическими) умными представлениями.}

Я не эксперт, но предполагаю, что достаточно умные люди смотрели на генератор случайных чисел Java на протяжении многих лет. Следовательно, я бы также предположил, что случайные UUID - это хорошо. Таким образом, у вас действительно должна быть теоретическая вероятность столкновения (которая составляет примерно 1: 3 × 10 ^ 38 для всех возможных UUID. Кто-нибудь знает, как это изменяется только для случайных UUID? Это 1 / ( 16 * 4) из вышеперечисленного?)

Судя по моему практическому опыту, я пока не видел никаких столкновений. Я, наверное, отрасту удивительно длинную бороду в тот день, когда получу свою первую;)

UUID использует java.security.SecureRandom , который предполагается быть «криптографически стойким». Хотя фактическая реализация не указана и может варьироваться в зависимости от JVM (что означает, что любые сделанные конкретные утверждения действительны только для одной конкретной JVM), она требует, чтобы выходные данные прошли проверку генератора статистических случайных чисел.

Реализация всегда может содержать тонкие ошибки, которые разрушают все это (см. Ошибка генерации ключей OpenSSH), но я не думаю, что есть какая-то конкретная причина для беспокойства по поводу случайности Java UUID.

В Википедии есть очень хороший ответ http://en.wikipedia.org/wiki/Universally_unique_identifier#Collisions

количество случайных UUID версии 4, которые необходимо сгенерировать, чтобы иметь 50% вероятность хотя бы одного столкновения, составляет 2,71 квинтиллиона, вычисляется следующим образом:

...

Это число эквивалентно генерации 1 миллиарда UUID в секунду в течение примерно 85 лет, и файл, содержащий такое количество UUID, по 16 байтов на UUID, будет составлять около 45 экзабайт, много раз больше, чем самые большие базы данных, существующие в настоящее время, которые составляют порядка сотен петабайт.

...

Таким образом, чтобы вероятность дублирования была один к миллиарду, необходимо сгенерировать 103 триллиона UUID версии 4.