Fonction de hachage 1-à-1 aléatoire

Question

Je suis tombé sur un problème intéressant aujourd'hui, et j'ai parcouru internet à la recherche d'une solution mais je n'en ai trouvé aucune. Le problème est le suivant:

Un utilisateur crée un compte et reçoit un numéro d'identification unique, disons 123, pour représenter son compte. Quand un autre utilisateur crée un compte, je peux simplement ajouter 1 au numéro d'identification le plus récemment créé et lui assigner, 124. Cependant, cela ne rend pas complètement anonyme tout le monde comme il sait maintenant que l'utilisateur 123 s'est enregistré avant lui. Un très petit problème à avoir, mais dans certaines situations concevables cela pourrait causer des problèmes beaucoup plus importants.

Une meilleure solution serait d'avoir des ID aléatoires mais uniques afin que personne ne puisse dire qui est venu en premier.

Pour résoudre ce problème, vous pouvez utiliser une fonction de hachage standard ou un générateur de nombres aléatoires pour créer un ID unique pour chaque personne, mais vous risquez alors de rencontrer des collisions. Cela peut être évité en vérifiant les collisions et en recommençant à fonctionner, mais disons pour cet exemple que cela va trop ralentir le système. Ou il se peut que le générateur fonctionne sur des informations incomplètes et ne puisse pas vérifier s'il y a des collisions.

Une idée différente que je suis venu avec est d'avoir essentiellement un jeu de cartes mélangé que vous stockez et en prendre un au large à chaque fois que vous avez besoin d'un nouvel ID. Quand vous n'avez plus de cartes dans le paquet, vous prenez un nouveau deck en continuant à la plus haute carte de votre dernier deck et vous mélangez celui-ci. Inconvénients à cela sont que vous devez stocker ce jeu de cartes et si vous perdez accidentellement le jeu, vous rencontrez de nombreux problèmes en essayant de le recréer ou de continuer sans.

Une solution très similaire à celle-ci consiste à recréer à chaque fois cette planche mélangée à partir d'une graine fixe, et à prendre la nième carte du pont au lieu de la première. Le problème que cela a, c'est qu'il peut être coûteux de mélanger ce jeu chaque fois que vous avez besoin d'une nouvelle carte.

D'autres modèles mathématiques que j'ai essayé de trouver tous ont le problème du nombre prévisible de la séquence (chaque nombre est une quantité fixe en dehors de la précédente). Beaucoup d'entre eux ont aussi des problèmes de collisions. Donc ma question est: Y at-il un modèle mathématique que je peux brancher des numéros pour obtenir des identifiants uniques qui ne nécessitent pas l'utilisation d'un "deck" (read: array) stocké en mémoire ou recalculé à chaque appel de fonction.

Par exemple

randomID(number, seed, range) 
randomID(1,123,1000) = 284 
randomID(2,123,1000) = 739 
randomId(3,123,1000) = 088 
randomId(3,888,1000) = 912 

J'ai regardé https://code.google.com/p/smhasher/wiki/MurmurHash3 qui semble être prometteuse, mais je ne pense pas qu'il applique sur une plage arbitraire de nombres, et seulement sur 32bits ou 64bits.

Answer 1

Vous pouvez sélectionner un générateur de nombres pseudo-aléatoires avec une période supérieure au nombre maximum d'utilisateurs que vous auriez besoin de prendre en charge, il vous suffit alors de graver le PRNG avec la dernière valeur utilisée pour générer le suivant. Si vous perdez en quelque sorte la trace de la dernière valeur utilisée, vous pouvez utiliser la graine initiale et générer d'autres valeurs en fonction du nombre d'utilisateurs déjà enregistrés. Vous voudrez probablement éviter PRNG avec des valeurs excessivement grandes (par exemple, peut-être trouver une période de 16 bits un 2^16 si vous aurez moins de 65536 utilisateurs), donc les chiffres sont pratiques à retenir.

Answer 2

Vous ne savez pas exactement comment vous stockez cela, mais vous pouvez créer un grand tableau assez grand pour gérer tous les utilisateurs qui utiliseraient votre site. Ensuite, vous pouvez créer un nombre aléatoire qui commence à un nième indice aléatoire et itère un nombre aléatoire de fois. Lorsque vous tombez sur un index vide, vous mettez une valeur (telle que 1 ou autre) dans cet index et l'utilisateur obtient l'identifiant de l'index. Si cet index a déjà une valeur, répétez le processus jusqu'à ce que le nombre aléatoire tombe sur un index. La bonne chose à ce sujet serait que vous n'auriez même pas à itérer parce que vous pourriez simplement ajouter le nombre aléatoire à l'index actuel. La seule logique serait une sorte de fonction mod pour gérer les cas où vous atteignez la fin du tableau. J'espère que cela t'aides.

Answer 3

Voici approche souple et efficace: -

1. Tenir à jour une table de hachage.
2. Sélectionnez un nombre M proportionnel à la taille de la table de hachage que vous devez utiliser.
3. Générer M nombres aléatoires pour les premiers identifiants M et éviter les collisions par table de hachage.
4. À la fin de M générations, ajoutez toutes les valeurs id + 1 de M identifiants précédents si elles ne sont pas utilisées dans un tableau de taille M + 1.
5. Ajoutez l'ID 0 s'il n'est pas utilisé plus tôt.
6. Pour chaque génération d'ID suivante, sélectionnez un ID dans le tableau au hasard.
7. Ajoutez id + 1 s'il ne se trouve pas dans la table de hachage.

Avantages: -

1. Vous pouvez régler le caractère aléatoire et stockage utilisé à l'aide M. supérieur M plus aléatoires sont vos identifiants. Vous pourriez trouver un compromis entre l'espace utilisé et le hasard.
2. vous pouvez facilement utiliser la base de données en mémoire comme redis pour table de hachage et tableau.
3. La complexité du temps pour la génération d'identifiant unique est O (1)

Answer 4

Vous pouvez utiliser un block cipher pour y parvenir. Lorsque vous cryptez un bloc (un nombre fixe de bits), le chiffrement le mappe à un bloc différent avec le même nombre de bits. L'étape de déchiffrement annule ceci. Deux blocs différents ne sont jamais associés au même bloc. Prenez votre identifiant utilisateur, disons 64 bits, et cryptez-le avec un chiffrement par bloc de 64 bits et une clé secrète, et vous avez votre identifiant utilisateur aléatoire. Pour récupérer l'ID utilisateur d'origine, il suffit de le déchiffrer avec la même clé.

Si vous utilisez un algorithme connu comme Blowfish ou AES, les résultats seront cryptographiquement aussi sûrs que vous pouvez l'obtenir.