Différentes structures de données pour l'implémentation d'index inversé

Question

J'essaie de créer un programme qui analyse un dossier de fichiers texte, sépare chaque mot et les ajoute à une liste de tableaux. L'utilisateur peut rechercher des mots simples et le programme affichera dans quel document le mot existe. Je cherche initialement à utiliser HashMap mais je me demande s'il existe d'autres structures de données qui sont meilleures ou tout aussi bonnes.

• Quel est l'avantage d'utiliser la carte de hachage pour ce programme particulier?
• Quelles autres structures de données peuvent être utilisées pour ce problème?

Answer 1

Pour cette tâche, je recommanderais un HashMap<word, Set<text-file>, en abusant de la syntaxe générique Java. Où mot en tant que clé et un ensemble de fichiers de texte relatif en tant que valeur

Pourquoi une HashMap?

HashMap ou Map propose une recherche et un ajout de temps de O(1).

Pourquoi un ensemble dans la carte?

Le même mot peut exister dans plusieurs fichiers de texte. En outre, si le même mot dans un document a été enregistré, Définir la structure de données ne stocke pas la valeur en double et la méthode .contains et .add est O(1)

En utilisant HashMap, lorsque vous avez essayé de le faire chaque aspect clé en vous coûtera O(1) (en supposant que votre table de hachage fonctionne correctement) où autre mise en œuvre sera probablement vous coûter au moins O(log n)

Si vous avez l'intention de faire cette tâche en même temps ConcurrentHashMap sera votre ami

Answer 2

HashMap est une façon meilleure solution si il vient s pour rechercher des performances.

Vous pouvez également utiliser Google Guava Multimap lorsque plusieurs valeurs sont associées à une seule touche. Tout comme une carte de <Key, List<Value>>. Mais le code semble beaucoup plus propre avec Multimap. Vous pouvez également utiliser SetMultimap. Un SetMultimap ne peut pas contenir de paires clé-valeur en double. L'ajout d'une paire clé-valeur déjà dans le multimap n'aura aucun effet.