Génération d'ID unique PHP de courte durée utilisant auto_increment?

StackOverflow https://stackoverflow.com/questions/1650185

Question

Je souhaite générer un identifiant court et unique sans avoir à vérifier les collisions.

Je fais actuellement quelque chose comme ça, mais l'ID que je génère actuellement est aléatoire et la recherche de collisions dans une boucle est ennuyeuse et coûtera cher si le nombre d'enregistrements augmente de manière significative.

Normalement, le souci des collisions n’est pas un problème, mais l’ID unique que je veux générer est une chaîne unique de 5 à 8 caractères alphanumériques, comme le fait tinyurl.

EDIT: Je voudrais commencer avec 5 caractères et si je frappe 60 millions d'entrées, passez à 6 .. etc. etc.

À cette fin, je pensais pouvoir utiliser une valeur auto_increment masquée pour les utilisateurs et leur présenter à la place une MD5 méthode ou une autre méthode permettant de générer une chaîne unique à partir de celle-ci.

Les chaînes générées ne doivent pas sembler linéaires, aussi la simple conversion de l'ID auto_incremented en base 36 [0-9A-Z] est un peu trop simpliste, mais une fonction comme celle-là est la voie à suivre.

EDIT: La sécurité n’est pas un problème car elle ne sera pas utilisée pour sécuriser des informations. C'est simplement un raccourci vers une chaîne plus longue. Merci.

Merci pour vos suggestions et désolé pour le retard. Dentiste ..

Était-ce utile?

La solution

Vous aurez besoin de quelque chose de correct par construction, c’est-à-dire une fonction de permutation: il s’agit d’une fonction qui mappe de manière réversible un entier (votre compteur séquentiel) sur un autre. Quelques exemples (toute combinaison de ceux-ci devrait également fonctionner):

  • inversion de certains bits (par exemple, en utilisant un XOR, ^ en PHP)
  • échange les emplacements de bits (($ i & amp; 0xc) > > 2 | ($ i & amp; 0x3) < < ; 2) ou simplement inverser l’ordre de tous les bits
  • ajouter une valeur constante modulo votre plage maximale (doit être un facteur de deux, si vous combinez cela avec ceux ci-dessus)

Exemple: cette fonction convertira 0, 1, 2, 3, 5, .. en 13, 4, 12, 7, 15, .. pour les nombres inférieurs à 15: 

$i=($input+97) & 0xf;
$result=((($i&0x1) << 3) + (($i&0xe) >> 1)) ^ 0x5;

MODIFIER

Une méthode plus simple consisterait à utiliser un générateur de congruence linéaire (LCG, généralement utilisé pour générer des nombres aléatoires), défini par une formule de la forme suivante: 

X_n+1 = (a * X_n + c) mod m

Pour les valeurs correctes de a, c et m, la séquence de X_0, X_1. X_m-1 contiendra tous les nombres entre 0 et m-1 exactement une fois. Vous pouvez maintenant commencer à partir d’un index croissant linéairement et utiliser la valeur next de la séquence LCG comme & "Secret &"; clé.

EDIT2

Mise en oeuvre: Vous pouvez définir vos propres paramètres LCG , mais si vous vous trompez, cela ne couvrira pas la gamme complète (et donc des doublons), je vais donc utiliser ici un ensemble de paramètres publiés et testés à partir de cet article : 

a = 16807, c = 0, m = 2147483647

Cela vous donne une plage de 2 ** 31. Avec pack (), vous pouvez obtenir l'entier résultant sous forme de chaîne. Base64_encode () en fait une chaîne lisible (comprenant jusqu'à 6 caractères significatifs, 6 bits par octet). Il pourrait donc s'agir de votre fonction: 

substr(base64_encode(pack("l", (16807 * $index) % 2147483647)), 0, 6)

Autres conseils

Vous pouvez probablement générer un hachage MD5 du nombre date / heure actuel et le tronquer à la longueur souhaitée (5 à 8 caractères) et le stocker en tant que champ id.

Si vous utilisez le stockage de ces informations dans une base de données, vous n'avez pas besoin d'utiliser une boucle for pour effectuer la vérification des collisions, vous pouvez simplement effectuer une instruction select, comme par exemple

. 
SELECT count(1) c FROM Table WHERE id = :id

où: id serait l'id nouvellement généré. Si c est supérieur à 0, vous savez qu'il existe déjà.

MODIFIER

Cela peut ne pas être la meilleure façon de s'y prendre. Mais je vais essayer. Je suppose que vous avez donc besoin de convertir un nombre en une chaîne courte unique et non consécutive.

Comme vous l'avez dit, le codage base64 effectue déjà la conversion de nombre en chaînes courtes. Pour éviter le problème de séquence, vous pouvez créer un mappage entre vos identifiants générés automatiquement et certains & "Random &"; valeur (mappage unique). Ensuite, vous pouvez encoder cette valeur unique en base64.

Vous pouvez générer ce mappage comme suit. Avoir une table de stockage temporaire des valeurs de 1 à 10 000 000. Triez-le dans un ordre aléatoire et stockez-le dans votre table de mappage. 

INSERT INTO MappingTable (mappedId) SELECT values FROM TemporaryTable ORDER BY RAND()

Où MappingTable aurait les 2 champs id (votre identifiant généré automatiquement le comparerait) et mappedId (pour lequel vous généreriez le codage base64).

Au fur et à mesure que vous approchez de 10 000 000, vous pouvez réexécuter le code ci-dessus et modifier les valeurs de la table temporaire avec 10 000 001 à 20 000 000 ou quelque chose du genre.

vous pouvez utiliser un XOR au niveau du bit pour brouiller certains des bits: 

select thefield ^ 377 from thetable;

+-----+---------+
| a   | a ^ 377 |
+-----+---------+
| 154 |     483 |
| 152 |     481 |
|  69 |     316 |
|  35 |     346 |
|  72 |     305 |
| 139 |     498 |
|  96 |     281 |
|  31 |     358 |
|  11 |     370 |
| 127 |     262 |
+-----+---------+

Je pense que cela ne sera jamais vraiment sécurisé, car il vous suffit de trouver la méthode de cryptage derrière la chaîne unique et courte pour détourner un identifiant. La recherche de collisions dans une boucle est-elle vraiment problématique dans votre contexte?

  

Un MD5 d'un nombre incrémentant   devrait bien se passer, mais je crains que si   vous tronquez votre MD5 (qui est   normalement 128 bits) jusqu'à 5-8   personnages, vous aurez presque certainement   être dommageable sa capacité d'agir en tant que   une signature unique ...

Complètement vrai. Surtout si vous atteignez votre chance de collision de 80%, un MD5 tronqué sera aussi bon que n'importe quel nombre aléatoire pour garantir l'unicité, c'est-à-dire sans valeur.

Mais puisque vous utilisez quand même une base de données, pourquoi ne pas simplement utiliser un INDEX UNIQUE? De cette façon, la vérification de l'unicité est effectuée (d'une manière beaucoup plus efficace que d'utiliser une boucle) par MySQL elle-même. Essayez simplement de faire l'INSERT avec votre clé générée par MD5, et si cela échoue, essayez à nouveau ...

Si vous ne pouvez pas utiliser de champ à incrémentation automatique et souhaitez une valeur unique absolue , utilisez UUID . Si vous décidez d'utiliser autre chose (en plus de l'incrémentation automatique), il serait ridicule de NE PAS vérifier les collisions.

Cet article de blog a quelque chose de proche de ce que vous recherchez.

http://kevin.vanzonneveld.net/techblog_article a>

Un MD5 avec un nombre incrémenté devrait suffire, mais je crains que si vous tronquez votre MD5 (qui est normalement de 128 bits) en 5 à 8 caractères, vous risquez certainement de l'endommager. signature unique ...

Non affilié à StackOverflow
scroll top