Que dites-vous de couper UUID de type 4 de cette manière

Question

Cochez cette

    List<String> list = new ArrayList<String>();
    for (int i = 0; i < 10000; i++) {
        String value = (""+UUID.randomUUID().getLeastSignificantBits()).substring(3, 20);
        assertFalse(list.contains(value));
        assertTrue(value.length() < 18);
        list.add(value);
    }

Cette méthode passe comme un charme. Et je suis dans l'impression qu'il est un peu mieux prendre bits les moins significatifs, plutôt que les plus importants. Parce que dans les bits que vous avez les plus importants 6 bits fixes pour quelques informations, et le moins significatif ne est pas le cas. Par conséquent, nous avons besoin en moyenne pour générer 2 ^ 29 UUID pour obtenir une collision avec bits les plus significatifs, mais 2 ^ 32 avec de nombreux bits les moins significatifs. Ref: SO Enfiler. Ai-je raison de supposer que?

Maintenant, ici je coupais 2 chiffres plus les plus significatifs des bits les moins significatifs que j'ai obtenu de la méthode. J'utilise à cette sous-chaîne. Remarquez que je suis coupais 2 chiffres et un bit de signe au large. Est-ce que ne signifie pas que maintenant, en moyenne, nous devons générer 2 ^ 31 UUID pour obtenir une collision?

Justement, je suis en train de générer un identifiant unique qui ne doit pas dépasser une longueur de 17 chiffres. Et il doit être un entier, et non pas dans un sens de type Java. Quelle est la fiabilité de mon approche?

Informations Meta:

En fait, nous intégrons avec un système d'héritage, et nous devons fournir un numéro unique pas plus de 17 chiffres. Ils éprouvent comme une base de données clé unique, je suppose. On peut également utiliser la séquence dans ce cas, et je propose que, en premier lieu. Mais on m'a dit que son bien si je peux venir avec un nombre aléatoire au lieu, si le consommateur ne peut pas deviner.

Pour autant que je sais en ce qui concerne la mise en œuvre de type 4 de UUID en Java, nous devons générer 2 ^ 61 UUID en moyenne pour obtenir une collision. Est-ce que cela signifie pas que nous devons générer 2 ^ 32 pour obtenir la collision sur bits les moins significatifs, et 2 ^ 29 pour obtenir la collision sur la plupart des bits significatifs? Si oui, il est donc inexact de supposer que nous devons générer en moyenne 2 ^ 31 pour obtenir la collision sur bits les moins significatifs après hachage de 2 à gauche la plupart des chiffres?

J'ai essayé d'utiliser SecureRandom aussi, mais qui est aussi me donne la valeur à long 19 chiffres. Par conséquent, je finis par couper premier à chiffres aussi. Voici le code pour cela.

    List<String> list = new ArrayList();
    Random random = new SecureRandom();
    for (int i = 0; i < 10000; i++) {
        String value = ""+random.nextLong().substring(2, 19);
        assertFalse(list.contains(value));
        assertTrue(value.length() < 18);
        list.add(value);
    }

L'autre option que je peux penser est d'utiliser la date dans un format "yyMMddHHmmssSSS + 2-seq chiffres". Mais ce serait tout à fait processeur à charge, et devinables, je suppose. Parce que je ne suis pas tout à fait certain que je suis un changement de milliseconde après 99 tours. Peut-être que je veux, mais cela dépend de la vitesse du processeur. 99 requêtes simultanées sont très peu probable cependant.

Answer 1

Je suggère que vous utilisez soit aléatoire ou SecureRandom pour générer des bits aléatoires et transformer ces en nombre. Cela devrait être plus facile à transporter.

Je ne comprends pas votre point sur les chiffres de hachage. En supposant que vous êtes la génération d'un long cycle de 17 (en décimal) Numéro de chiffres de suffisamment de bits vous PRNG devrait avoir une chance de 1 à 10 ** 17 d'une collision pour tout couple généré de chiffres donnée. Si la source est bonne, et que vous utilisez assez de bits alors il est indifférent que vous « cannibalisation » ...

Il est clair pour moi que 1 10**17 est assez bon. Cela dépend du nombre de numéros vont exister (dans votre magasin persistant) à un moment donné. Par exemple, si vous avez 44 millions de numéros existant, la possibilité d'une collision entre au moins une paire sera d'environ 1%.

Essayez de brancher quelques chiffres dans un anniversaire Paradox Calculator .

EDIT: Je pense que ce que vous avez besoin est un générateur qui vous donne 64 bits des nombres pseudo-aléatoires avec une longue durée de cycle et une garantie absolue de pas de répétitions pour plus de chiffres que vous pourriez jamais peut générer. Il doit également être possible de conserver l'état du générateur et de la reprendre. Ensuite, pour obtenir un 17 chiffre décimal nombre « aléatoire », obtenir la valeur suivante du générateur et tester si elle est dans la gamme 0 ... 10**17 - 1. Le cas échéant, l'utiliser, sinon répéter.

Si vous gérez correctement le générateur, vous ne avez jamais une répétition pour la durée de vie du système, et donc il est nul risque d'une collision. Mais il est important que vous utilisez un PRNG (pas un vrai RNG) et que vous choisissez un PRNG qui a les propriétés requises.

D'après ce que je peux dire, la classe aléatoire offre une PRNG avec une longueur de cycle de 2**48; dire que vous devriez obtenir des numéros de 2**48 (par exemple en utilisant la méthode getLong()) avant que les chiffres commencent à répéter. OTOH, SecureRandom donne soit vraiment aléatoire nombre ou pseudo-aléatoire avec un cycle très long ... mais avec une petite chance de non-zéro de répéter un numéro sur chaque appel.

Answer 2

OK, plusieurs questions, je ferai de mon mieux

1. Si vous avez collusion dans les bits inférieurs mais pas dans les bits supérieurs, vous avez encore ids uique. Idem pour le cas contraire. Vous devez donc 2 ^ 61 chiffres pour obtenir une collusion.
2. Avec une probabilité de 0,5, vous hachez 3 chiffres, le signe + est pas écrit. Par conséquent, vous avez total de 2 ^ 41 nombres possibles, de sorte que la taille de l'échantillon de collusion est 2 ^ 21. (10 ^ 18 = ~ 2 ^ 41)
3. Voyons comment vous obtenez vos résultats: Random.getLong () est appelée deux fois, puis vous retirer certains des bits (bits aléatoires PRNG créée). Je ne vois pas comment il est plus fiable que d'appeler Random.getLong () ou getInt ().

Si vous avez besoin d'un numéro de 17 chiffres, pourquoi ne pas faire ce qui suit:

String id = String.valueOf(random.nextLong) % 1000000000000000000L);

Notez qu'il ne donnera pas la distribution symétrique - puisque MAX_LONG est 9223372036854775807L les nombres dans la gamme [0,23372036854775807] sera légèrement meilleure chance d'apparaître

.

En outre, à la fois que vous méthode et celui-ci ne garantissent pas id unique.

Answer 3

L'algorithme UUID est mise en œuvre spécifique.

Hacher le guid en plus petits nombres ne va avoir la même diffusion unique ou une garantie de. Sont les bits que vous enregistrez vraiment important?