construire un numéro unique pour une chaîne en java

Question

Nous avons une exigence de lecture / écriture de chaînes plus de 10 millions dans un fichier. En outre, nous ne voulons pas de doublons dans le fichier. Étant donné que les chaînes seraient vidées dans un fichier dès qu'ils sont lus, nous ne conservons en mémoire.

Nous ne pouvons pas utiliser hashcode en raison de collisions dans le code de hachage en raison de laquelle nous pourrions manquer une chaîne en double. Deux autres approches que je trouve dans mon googling:

1.Utiliser un message algorithme de hachage comme MD5 -. Mais il pourrait être trop coûteux pour calculer et stocker

2.Utilisez un algorithme de contrôle. [Je ne sais pas si cela produit une clé unique pour une personne string- peut-il confirmer s'il vous plaît]

Y at-il d'autres avaiable d'approche. Merci.

Answer 1

Si vous êtes d'accord avec un risque de collision microscopique, vous pouvez utiliser une fonction de hachage telle que MD5 comme vous le suggérez, et compter sur les hash.

Une autre alternative, peut-être avec une empreinte mémoire plus grande, est de stocker les, chaînes déjà rencontrées, dans un Trie (un type particulier d'arbre).

---

Mise à jour: Une autre variante encore, serait d'utiliser un filtre Bloom . Cependant, cela repose toujours sur le hachage, mais peut être ajusté pour avoir une probabilité arbitrairement faible de collisions.

Answer 2

Stockage 10 millions de chaînes en mémoire est en effet beaucoup, donc je comprends la raison de l'écrire dans le fichier immédiatement au lieu de stocker par exemple, dans TreeSet<String> d'abord, mais où voulez-vous enregistrer les touches numériques uniques 10 millions que vous voulez comparer avec? Lorsque vous voulez garder uniques et numérique (qui a beaucoup de base / radix Littler que les lettres), vous ne pouvez pas la clé plus courte que lui-même est déjà chaîne, de sorte que vous ne sauverez pas de mémoire. Ou peut-être au plus haut avec la compression de données comme GZIP, mais cela ajouterait que beaucoup de frais généraux. MD5 est également inappropriée puisque deux chaînes différentes peut produire le même hachage.

Je ne vois vraiment pas de meilleure solution pour ce que d'utiliser un SGBDR décent (base de données SQL) dans laquelle vous définissez la colonne comme UNIQUE et de gérer la violation de contrainte en conséquence. Un SGBDR est optimisé pour ce genre de tâches.

Si vous ne pouvez vraiment pas envisager une base de données, vous devez relire le fichier pour une entrée existante avant d'écriture / de chasse. Peut-être pas très rapide, mais certainement efficace de la mémoire.

Answer 3

Il n'y a pas moyen de faire une fonction qui produirait une clé unique pour une chaîne, qui est plus courte que cette chaîne.
Il existe des structures de données qui peuvent résoudre votre tâche. B-tree pourrait adapter si vos données sont assez grandes. En fonction de la nature de votre entrée, il pourrait y avoir des moyens plus efficaces.

Answer 4

Fiable la suppression des doublons est à peu près aussi difficile que le tri du fichier. Comme une autre réponse indique, il n'y a aucun moyen garanti de détecter avec précision les doublons sans garder une copie complète de chaque chaîne en mémoire, ce qui semble être exactement ce que vous essayez d'éviter.

Vous pourriez garder un indice de hashcodes, et les utiliser pour récupérer des chaînes réelles de stockage de fichiers pour la comparaison, mais cela essentiellement en double en mémoire ou sur disque ce qu'une base de données serait en mesure de le faire pour vous.

Une autre solution consiste à post-traiter le fichier une fois qu'il est terminé. La commande de tri UNIX est assez bon dans les grands fichiers ( Comment ? pourrait la commande de tri UNIX sorte un fichier très volumineux ), donc j'attendre l'approche de ligne de commande UNIX standard au travail raisonnable:

    sort my-file-of-strings.txt | uniq > my-filtered-file-of-strings.txt

(Notez que les fichiers doivent être triés d'abord avant de passer à Uniq pour supprimer les doublons).

Si vous n'avez pas ces outils (ou équivalents) est disponible, vous pouvez toujours essayer la mise en œuvre d'une variante d'une fusion externe vous sorte.

Answer 5

Si les chaînes sont d'une piscine fixe de chaînes possibles (N), alors vous pouvez utiliser le hachage minimal parfait pour créer un tableau 0 ... N-1. Un zéro dans la fente déterminée par les moyens de fonction de hachage parfaite chaîne n'a pas été vu jusqu'à présent.

Dans le cas contraire, le seul moyen efficace de corriger en dehors de beaucoup de la mémoire et les solutions proposées jusqu'à présent est de relire le fichier avant de décider d'écrire la chaîne à lui.

Vous pouvez le faire aussi efficacement que possible par des portions de mappage de mémoire du fichier.

Answer 6

Je pense vraiment la meilleure solution est - comme quelqu'un d'autre a déjà suggéré - d'utiliser une base de données.

Si pour une raison quelconque, vous ne pouvez pas utiliser une base de données, vous pouvez toujours utiliser un hashcode. Bien sûr, il y aura des collisions. Il suffit d'ajouter un code de sorte que lorsque vous détectez un double hashcode, votre programme vérifie le fichier pour déterminer si elle est un véritable double ou d'une collision.