Вероятность коллизии при использовании наиболее значимых битов UUID в Java

235

Если я использую, Long uuid = UUID.randomUUID().getMostSignificantBits()насколько вероятно получить столкновение. Он отрезает наименее значимые биты, так что есть вероятность, что вы столкнетесь с столкновением, верно?

dlinsin
источник

Ответы:

213

Согласно документации , статический метод UUID.randomUUID()генерирует UUID типа 4.

Это означает, что шесть битов используются для некоторой информации о типе, а оставшиеся 122 бита назначаются случайным образом.

Шесть неслучайных битов распределяются с четырьмя в наиболее значимой половине UUID и двумя в наименее значимой половине. Таким образом, самая значительная половина вашего UUID содержит 60 бит случайности, что означает, что вам в среднем нужно сгенерировать 2 ^ 30 UUID для получения коллизии (по сравнению с 2 ^ 61 для полного UUID).

Поэтому я бы сказал, что вы в безопасности. Обратите внимание, однако, что это совершенно не так для других типов UUID, как упоминает Карл Селеборг.

Кстати, вам было бы немного лучше, если бы вы использовали наименее значимую половину UUID (или просто генерировали случайный длинный с использованием SecureRandom).

Расмус Фабер
источник
3
Я не уверен, что это совершенно правильно - если посмотреть на реализацию, становится ясно, что информация о версии / варианте хранится не в старших разрядах, а где-то посередине.
Том
2
@RasmusFaber Комментарий Тома верен: здесь неправильный ответ о шести наиболее значимых битах, являющихся информацией о типе. Действительно, существует шесть битов неслучайных данных, но четыре бита идентифицируют версию 4, а два других бита зарезервированы. Четыре и два бита расположены в разных положениях около середины 128-битного значения. Смотрите статью в Википедии .
Василий Бурк
56

У Раймонда Чена есть действительно превосходное сообщение в блоге об этом:

GUID являются глобально уникальными, но подстроки GUID не являются

Карл Селеборг
источник
1
Ссылка больше не мертва.
Давид Вешеловский
3
Ссылка снова мертва. Вот ссылка на версию веб-архива .
Куба Спатный
10

Вам лучше просто генерировать случайное длинное значение, тогда все биты являются случайными. В Java 6 новый Random () использует System.nanoTime () плюс счетчик в качестве начального числа.

Существуют разные уровни уникальности.

Если вам нужна уникальность на многих машинах, у вас может быть центральная таблица базы данных для распределения уникальных идентификаторов или даже пакетов уникальных идентификаторов.

Если вам просто нужно иметь уникальность в одном приложении, вы можете просто иметь счетчик (или счетчик, который начинается с currentTimeMillis () * 1000 или nanoTime () в зависимости от ваших требований)

Питер Лори
источник
7

Используйте время YYYYDDDD(год + день года) в качестве префикса. Это уменьшает фрагментацию базы данных в таблицах и индексах. Этот метод возвращает byte[40]. Я использовал его в гибридной среде, где SID Active Directory ( varbinary(85)) является ключом для пользователей LDAP, а автоматически созданный идентификатор приложения используется для пользователей, не являющихся LDAP. Также большое количество транзакций в день в таблицах транзакций (Банковская индустрия) не может использовать стандартные Intтипы ключей

private static final DecimalFormat timeFormat4 = new DecimalFormat("0000;0000");

public static byte[] getSidWithCalendar() {
    Calendar cal = Calendar.getInstance();
    String val = String.valueOf(cal.get(Calendar.YEAR));
    val += timeFormat4.format(cal.get(Calendar.DAY_OF_YEAR));
    val += UUID.randomUUID().toString().replaceAll("-", "");
    return val.getBytes();
}
Доктор боб
источник
3
Почему бы не использовать вместо этого стандартный UUID V1?
ShadowChaser