Probabilité de collision en utilisant les bits les plus significatifs d'un UUID en Java

235

Si j'utilise Long uuid = UUID.randomUUID().getMostSignificantBits() la probabilité de collision. Il coupe les bits les moins significatifs, il y a donc une possibilité que vous rencontriez une collision, non?

dlinsin
la source

Réponses:

213

Selon la documentation , la méthode statique UUID.randomUUID()génère un UUID de type 4.

Cela signifie que six bits sont utilisés pour certaines informations de type et les 122 bits restants sont attribués de manière aléatoire.

Les six bits non aléatoires sont répartis avec quatre dans la moitié la plus significative de l'UUID et deux dans la moitié la moins significative. Ainsi, la moitié la plus importante de votre UUID contient 60 bits de caractère aléatoire, ce qui signifie que vous devez en moyenne générer 2 ^ 30 UUID pour obtenir une collision (contre 2 ^ 61 pour l'UUID complet).

Je dirais donc que vous êtes plutôt en sécurité. Notez, cependant, que ce n'est absolument pas vrai pour d'autres types d'UUID, comme le mentionne Carl Seleborg.

Soit dit en passant, vous seriez un peu mieux en utilisant la moitié la moins significative de l'UUID (ou en générant simplement un long aléatoire à l'aide de SecureRandom).

Rasmus Faber
la source
3
Je ne suis pas sûr que ce soit tout à fait correct - en regardant l'implémentation, il est clair que les informations de version / variante ne sont pas stockées dans les bits les plus significatifs, mais plutôt quelque part au milieu.
Tom
2
@RasmusFaber Le commentaire de Tom est correct: la réponse ici est incorrecte au sujet des six bits les plus significatifs étant des informations de type. Il y a en effet six bits de données non aléatoires mais quatre bits identifient la version 4 et deux autres bits sont réservés. Les quatre et deux bits sont situés dans des positions différentes près du milieu de la valeur de 128 bits. Voir l'article Wikipedia .
Basil Bourque
10

Il vaut mieux simplement générer une valeur longue aléatoire, alors tous les bits sont aléatoires. Dans Java 6, le nouveau Random () utilise le System.nanoTime () plus un compteur comme graine.

Il existe différents niveaux d'unicité.

Si vous avez besoin d'unicité sur de nombreuses machines, vous pouvez disposer d'une table de base de données centrale pour allouer des ID uniques, voire des lots d'ID uniques.

Si vous avez juste besoin d'unicité dans une application, vous pouvez simplement avoir un compteur (ou un compteur qui commence à partir de currentTimeMillis () * 1000 ou nanoTime () selon vos besoins)

Peter Lawrey
la source
7

Utiliser le temps YYYYDDDD (Year + Day of Year) comme préfixe. Cela réduit la fragmentation de la base de données dans les tables et les index. Cette méthode revient byte[40]. Je l'ai utilisé dans un environnement hybride où l'Active Directory SID ( varbinary(85)) est la clé pour les utilisateurs LDAP et un ID généré automatiquement par l'application est utilisé pour les utilisateurs non LDAP. De plus, le grand nombre de transactions par jour dans les tables transactionnelles (secteur bancaire) ne peut pas utiliser les Inttypes standard pour les clés

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();
}
Dr Bob
la source
3
Pourquoi ne pas utiliser un UUID V1 standard à la place?
ShadowChaser