Meilleure structure de données que HashTable pour garder une trace des enregistrements traités?

Question

Je traite un grand nombre d'enregistrements de base de données, chacun avec une clé unique.

En raison de la nature de ma base de données, ma méthode de traitement peut rencontrer la même clé deux fois, car il s'agit d'une base de données relationnelle et un enregistrement peut avoir plusieurs enregistrements «parents».

C'est une perte de temps, de puissance de traitement, de mémoire et de taille de fichier pour traiter des enregistrements plusieurs fois. J'ai donc besoin d'un moyen de garder une trace des identifiants que j'ai déjà traités.

J'ai regardé HashTable, puisque c'est O (1) pour obtenir et mettre des fonctions et ce sont les seules fonctions dont j'ai besoin. Cependant, il semble que ce soit un gaspillage de mémoire d'avoir essentiellement un bloc de mémoire (1000+)/Load Factor stockant essentiellement des valeurs booléennes. De plus, je ne connais pas ma capacité désirée et je devrais supporter beaucoup de remaniements ou allouer beaucoup plus de mémoire que nécessaire.

Je recherche une structure de données dans laquelle vous pouvez ajouter une valeur et lui donner une erreur si l'ID existe déjà dans la collection, comme retourner false à partir de la méthode put(T value).

Answer 1

Tout d'abord, il semble que vous voulez un jeu, pas une table. Deuxièmement, si vous voulez O (1), votre seule option est un HashSet, avec le surcoût de mémoire. Si vous êtes prêt à aller avec O (log (n)), alors un TreeSet fonctionnera très bien, sans surcharge. Troisièmement, l'ajout de set (T t) retournera false si l'élément est déjà présent. On dirait que vous vraiment voulez un ensemble au lieu d'une table.

O (log (n)) est toujours assez rapide. Ce n'est certainement pas O (1), mais ce n'est pas trop moche. Vous avez juste besoin de décider (peut-être après quelques tests) qui vous convient le mieux.

Answer 2

Je pense que HashSet est ce que vous cherchez: http://download.oracle.com/javase/6/docs/api/java/util/HashSet.html

Answer 3

Hey, puisque vous travaillez avec une base de données, ne pourriez-vous pas simplement stocker ces informations dans une table de base de données secondaire ou avec les enregistrements? Aussi, si vous avez une structure arborescente (puisque vous parlez de parents), pourquoi ne pas utiliser un algorithme de déplacement d'arbre, qui marque les nœuds traités. Checkout ces Breadth First Search/Depth First Search Animations et ceux-ci à Wikipeadia Entrées sur BFS et DFS.

En général, je m'assurerais de suivre le drapeau de traitement avec l'objet/ligne. Au lieu d'une structure de données séparée.

Answer 4

Vous pouvez utiliser Bloom filter, au lieu du hashmap.It est un problème de données probabiliste avec filtre structure Bloom est qu'il donnera de faux + ve's.Check cette implementation of bloom filter .Ce serait la mémoire efficace et plus rapide solution qu'une hashmap.

Plus d'info sur le filtre Bloom:

• What problems have you solved using bloom filters?[SO Question]
• Bloom Filter : Variants & Applications[Blog]
• Using a bloom filter to optimize a SQL query

Answer 5

Si le resultset est commandé correctement, pourriez-vous garder juste le "dernier traitement" id en mémoire? De cette façon, il vous suffit de cocher "l'identifiant actuel" par rapport à "l'identifiant final". Si elles sont différentes, éliminez-les, sinon passez à l'enregistrement suivant.