Supposons que vous souhaitiez avoir un ensemble de nombres hexadécimaux de 1 à 2 chiffres, donc 256 nombres. Utiliser simplement un petit ensemble pour résoudre le problème, mais cela fonctionnerait avec n'importe quelle chaîne de taille.
Vous avez donc un potentiel N ou 256 nombres dans ce cas. Vous allez «générer» un nouvel identifiant pour chaque nouvel enregistrement de données qui se présente à vous. Donc, il commence et vous donne au hasard af , puis 1d , puis 8a , etc.
La façon simple et naïve de faire cela est simplement de générer tous les nombres dans l'ordre, puis de les mélanger et de sortir de l'ensemble. Cela fonctionne bien lorsque vous n'avez que 256 numéros. Mais si vous avez des millions ou des milliards de numéros, ce n'est pas pratique car vous pourriez avoir beaucoup d'identifiants générés par taille qui ne sont pas utilisés pendant de longues périodes. J'aimerais éviter cela.
Ma question est donc de savoir quel est le moyen le plus rapide ou le moyen le plus rapide de créer une chaîne de clé unique comme celle-ci, sans les générer toutes à l'avance, et sans aller dans l'ordre en incrémentant simplement de 1 ou autre. Autrement dit, la clé doit être apparemment aléatoire.
Une façon que je peux imaginer est d'utiliser un trie pour stocker les valeurs déjà utilisées / générées. Ensuite, lorsque vous devez obtenir une nouvelle valeur, vous en générez une au hasard, puis vérifiez le trie pour voir s'il est déjà utilisé. Je ne sais pas comment dire à quel point cela est efficace, mais il semble que ce serait très mauvais une fois que vous commencerez à manquer d'identifiants et que vous serez aux derniers de l'ensemble. Vous généreriez beaucoup d'identifiants déjà générés et parcourriez le trie pour chacun, donc ce serait lent.
Je me demande s'il existe un moyen plus efficace de faire cela, sans les générer tous à l'avance. De plus, les enregistrements de données ne seront pas utilisés pour déterminer l'ID, car les enregistrements peuvent être extrêmement volumineux et complexes.
Il existe peut-être un moyen de parcourir (et de générer) un trie de manière aléatoire à la fois, et de générer ainsi l'ID puisque vous vous retrouvez à un endroit aléatoire unique dans le trie. Quelque chose de ce genre peut-être, je ne sais pas.
De plus, je ne suis pas sophistiqué avec le hachage, donc je ne sais pas s'il y aurait de bonnes méthodes avec ça.
5 Réponses :
Je pense qu'une fonction de mixage est ce que vous voulez. Il déplacera des bits dans votre entrée pour produire une sortie de même longueur. Il est réversible donc chaque entrée correspond à une sortie unique.
Puisque vous voulez que les données d'entrée ne participent pas à la génération d'id, vous aurez besoin d'un identifiant de substitution. Vous pouvez attribuer un identifiant incrémentiel à chaque enregistrement et utiliser la fonction de mixage pour brouiller l'identifiant.
Vous obtiendrez quelque chose comme:
id == 1 => id mixte == 0x7ed55d16 id == 2 => id mixte == 0xc761c23c Voir ici pour une inspiration:
OP a déclaré dans les commentaires: Les données d'entrée ne seraient pas utilisées pour générer l'ID, car elles pourraient être des objets extrêmement volumineux et compliqués
Cette question est une cible mouvante! J'ai un peu changé la réponse pour répondre à cette exigence.
Vous vous demandez si vous pourriez recommander une implémentation, tout cela semble assez compliqué et je ne sais pas vraiment comment les évaluer pour l'utilisation.
Dans mon exemple, j'ai utilisé des valeurs hexadécimales de 2 longueurs telles que 8a , mais vous avez des valeurs 0x7ed55d16 très grandes. Il semble que les fonctions de mixage liées produisent toutes de très grandes valeurs, c'est donc incorrect: / Les valeurs doivent être la taille de l'entrée, donc 256 ou moins.
@LancePollard bien lequel est-ce? Vous dites que vous voulez gérer "des millions ou des milliards de nombres". Veuillez préciser ce que vous voulez avant de passer plus de temps là-dessus.
Je veux qu'il soit proportionnel à la taille de l'échantillon. Donc, s'il y a 256 valeurs possibles, alors en hexadécimal, il ne devrait y avoir que 2 caractères maximum, mais si c'est 1 million de valeurs, alors un entier de 32 bits ou une valeur hexadécimale conviendrait.
Une fonction de mixage peut être créée pour toute longueur de bit souhaitée. C'est juste un algorithme qui déplace les bits de manière réversible. Je ne sais pas pourquoi j'ai obtenu ce vote négatif alors que cela est clairement utile.
Je pense qu'il devrait y avoir un compromis entre vitesse, flexibilité et efficacité.
Sur l'un d'entre eux, les générateurs pseudo aléatoires vous donneront une distribution uniforme de clés et seront raisonnablement rapides à générer. Cependant, la vérification d'un identifiant existant serait lente. Vous pouvez utiliser des filtres bloom (économiser de la mémoire) ou essayer, mais comme vous l'avez dit à un moment donné, vous devriez augmenter l'espace.
Une autre option consiste à utiliser le code Gray qui produira chaque clé (mais pas au hasard ordre). Vous devez garder une trace du dernier code émis.
let obj = {}
function generateRandomId(){
let id = Math.abs( 0.5 - Math.random()) * 1000
if(obj[id]){
generateRandomId()
} else {
obj[id] = true
}
return id
}
console.log(generateRandomId())
console.log(generateRandomId())
console.log(generateRandomId())
console.log(generateRandomId())
Mais si vous êtes d'accord avec l'utilisation d'un module, je trouve que celui-ci est le plus utile
uuid cela génère des UUIDS RFC4122.
99,99% sécurisé. 100% si inclus Date.now (); pour éviter les identifiants en double
J'envisage quelque chose comme ceci:
var trie = buildTrie()
var id1 = genId(trie)
var id2 = genId(trie)
console.log(id1,id2)
function buildTrie() {
var trie = buildNode(0)
return trie
function buildNode(level) {
if (level == 7) { // 8 bits
var node = {
available: true,
leaf: true
}
return node
} else {
var a = buildNode(level + 1)
var b = buildNode(level + 1)
var node = {
availableLeft: true,
availableRight: true,
left: a,
right: b
}
a.parent = node
b.parent = node
return node
}
}
}
function genId(node) {
var bytes = []
step(node, bytes)
var id = parseInt(bytes.join(''), 2).toString(16)
return id
function step(node, bytes) {
if (node.leaf) {
node.available = false
var c = node
var p = c.parent
while (p) {
if (p.left == c) {
p.availableLeft = false
} else if (p.right == c) {
p.availableRight = false
}
if (!p.availableLeft && !p.availableRight) {
c = p
p = p.parent
} else {
p = false
}
}
}
var randomDirection = Math.random() >= 0.5
if (randomDirection) {
if (node.availableLeft) {
bytes.push(0)
step(node.left, bytes)
} else if (node.availableRight) {
bytes.push(1)
step(node.right, bytes)
}
} else {
if (node.availableRight) {
bytes.push(1)
step(node.right, bytes)
} else if (node.availableLeft) {
bytes.push(0)
step(node.left, bytes)
}
}
}
}
Il existe peut-être un meilleur moyen.
Il s'agit d'un arbre binaire, donc vous avez 2 ^ {nbLevels + 1} - 1 nœuds contenant quelques champs. Chaque nœud est également construit en amont dans buildTrie () . Cela utilisera rapidement beaucoup de mémoire pour "des millions ou des milliards de nombres".
@bernie se demandant si vous pouviez recommander quelque chose de plus efficace en termes d'espace ( stackoverflow.com/questions/245878/... ).
Je ne vois rien dans votre question qui exige que les identifiants soient vraiment attribués au hasard. Est-ce une exigence ou voulez-vous simplement un identifiant non évident pour chaque enregistrement de données? Si le vrai hasard n'est pas requis, il ne devient pas plus compact que ma réponse qui stocke un seul nombre par enregistrement. Sinon, les identifiants aléatoires utilisés doivent être stockés quelque part (table de hachage, trie, tableau, etc.)
Merci qui a du sens. Non, je ne veux tout simplement pas d'identifiants incrémentés.
Je suppose que vous pouvez générer des identifiants séquentiels; c'est-à-dire que vous disposez d'un moyen fiable de savoir exactement combien d'identifiants ont été générés à ce jour. Ensuite, il suffit de chiffrer ce décompte avec un algorithme de chiffrement raisonnablement rapide.
Le chiffrement serait fait sur le décompte sous forme de nombre binaire, et le résultat chiffré avec la plupart des algorithmes serait de la même taille, également binaire. Si vous le souhaitez, vous pouvez encoder le résultat en base 64 ou hexadécimal pour le rendre plus facile à utiliser comme chaîne de caractères.
Puisque le chiffrement doit être une bijection (c'est-à-dire un mappage un à un) pour que le déchiffrement soit possible, il est garanti que cela produira un résultat différent à chaque fois jusqu'à ce que le nombre total d'ID déborde. Si c'est une fonction de chiffrement raisonnable, alors le résultat apparaîtra aléatoire (sinon le chiffrement serait vulnérable).
C'est exactement le même processus que j'ai décrit dans ma réponse la veille, mais en utilisant le "cryptage" comme fonction de mixage ... stackoverflow.com/a / 54549632/1030527
@bernie: Je suppose que c'est vrai; Je n'ai pas vraiment lu votre réponse d'aussi près. Ces choses arrivent; J'ai souvent eu mes réponses répétées, parfois des années plus tard. Je suppose que l'avantage de suggérer l'utilisation du cryptage est que la plupart des programmeurs sauront comment trouver une bibliothèque pour le faire, alors que la "fonction de mixage" sonne comme quelque chose qui devrait être recherché et implémenté. Apparemment, aucune des deux réponses n'était ce qu'OP recherchait, donc je suppose qu'il y a une autre contrainte non spécifiée.
Si chaque donnée d'entrée est unique, vous pouvez utiliser une fonction de hachage sur l'entrée et la transformer en nombre. Je me demande s'il existe une fonction mathématique pas trop compliquée qui peut générer quelque chose d'unique de 0 à N à chaque appel de
fn (0),fn (1), etc.Les données d'entrée ne seraient pas utilisées pour générer l'ID, car il pourrait s'agir d'objets extrêmement volumineux et complexes.
Veuillez supprimer les termes subjectifs tels que "moyen le plus rapide" . Souciez-vous de résoudre votre problème avant de le rendre plus rapide
Je sais comment résoudre le problème de manière lente comme déjà décrit, donc le moyen le plus rapide.
@ user633183 Eh bien, il a un moyen de résoudre le problème actuellement, il devient vraiment très lent à mesure qu'il se rapproche du plafond.
Envisageriez-vous d'utiliser un horodatage ayant été converti en hexadécimal comme une option viable? Je veux dire que c'est simple et fonctionnerait dans une certaine mesure pour dire le moins.
Non, pas d'horodatage, je souhaite avoir un contrôle total sur la structure de l'ID.
@ JO3-W3B-D3V avec un horodatage n'est pas recommandé
@LancePollard D'accord, dans ce cas, j'ai un certain nombre d'idées potentielles.
Et si vous n'utilisiez vraiment qu'un simple compteur, comme
1,2,3, etc., mais que vous hachiez ensuite le résultat en tant qu'ID? De cette façon, les identifiants seront uniques et générés uniquement à la demande, mais ils n'auront aucune signification ou ordre apparents en dehors du script (je suppose que les hachages peuvent être transformés en un nombre si vous avez besoin d'un nombre plutôt qu'une chaîne )Je pense que vous devriez utiliser une table de hachage avec
Adressage ouvert. Prenez juste le début de vos données, cela n'assurera aucune collision de hachage.