Какие цифры UUID реже всего будут конфликтовать, если генератор (например, версия UUID на Java) неизвестен?

Question

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

Существует ли набор из 8 или более цифр (не обязательно смежных, хотя в идеале да), которые с меньшей или большей вероятностью сталкиваются?

ДляНапример, я видел, как функция uuid() в MySQL, когда она используется дважды в одном и том же выражении, генерирует 2 одинаковых UUID, кроме цифр с 5 по 8:

0dec7a69-ded8-11e8-813e-42010a80044f
0decc891-ded8-11e8-813e-42010a80044f
    ^^^^

Каков общий ответ?

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

Answer 1

Предложение: первые 8 цифр

1c59f6a6-21e6-481d-80ee-af3c54ac400a
^^^^^^^^

Для всех реализаций генератора требуется использовать одинаковые алгоритмы для данной версии, поэтому беспокойтесь о последней, а не о первой.

UUID версия 1 & версия 2 , как правило, располагаются от наибольшей к наименьшей энтропии для данного источника.Таким образом, первые 8 цифр, вероятно, имеют наименьшую вероятность столкновения.

UUID версия 4 и версия 3 и 5 предназначены для обеспечения однородной энтропии, за исключениемзарезервированные цифры для версии и варианта .Таким образом, первые 8 цифр так же хороши, как и все остальные.

Answer 2

Существует один метод, который будет работать независимо от предостережений спецификации UUID.Поскольку UUID сам по себе предназначен для того, чтобы быть глобально уникальным, защищенный хэш, созданный из него с использованием правильного алгоритма, по крайней мере, с тем же битовым размером, будет иметь те же свойства.За исключением того, что безопасный хеш будет иметь энтропию через хеш-значение вместо определенных местоположений.

Например, вы можете сделать:

MessageDigest digest = MessageDigest.getInstance("SHA-256");
byte[] hash = digest.digest(uuid.toString().getBytes(StandardCharsets.UTF_8));

И затем вы берете столько бит изхеш, как вам нужно, и преобразовать их обратно в строку.

Хотя это односторонняя функция;чтобы быстро и эффективно отобразить его обратно в UUID, вам необходимо вести таблицу сопоставления.(Конечно, вы можете проверить, соответствует ли UUID более короткому коду, выполнив однонаправленный хэш для UUID снова)

Однако, если вы хотите извлечь несмежную часть из UUID, вы быесть такая же проблема.